leetcode的十道题目和参考答案

码力金矿

845人浏览 · 2025-04-20 10:13:03

码力金矿 · 2025-04-20 10:13:03 发布

leetcode的十道题目和参考答案

两数之和（哈希表优化）

题目‌：给定整数数组 nums 和目标值 target，返回数组中两个数的索引，使它们的和等于目标值。
输入样例‌：

nums = [2,7,11,15], target = 9

输出样例‌：

[0,1]

代码与解析‌：

def twoSum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hashmap:
return [hashmap[complement], i]
hashmap[num] = i
return []
print(twoSum([2,7,11,15], 9))

解析‌：

遍历数组时用哈希表记录每个数字的索引。
检查当前数的补数（target - num）是否在哈希表中，找到即返回。
时间复杂度 O(n)‌，空间复杂度 O(n)。
2. 最长无重复字符子串（滑动窗口）

题目‌：给定字符串 s，找到不含重复字符的最长子串长度。
输入样例‌：

s = “abcabcbb”

输出样例‌：

代码与解析‌：

def lengthOfLongestSubstring(s):
left = max_len = 0
char_map = {}
for right in range(len(s)):
if s[right] in char_map and char_map[s[right]] >= left:
left = char_map[s[right]] + 1
char_map[s[right]] = right
max_len = max(max_len, right - left + 1)
return max_len
print(lengthOfLongestSubstring(“abcabcbb”))

解析‌：

滑动窗口 [left, right] 维护当前无重复区间。
用字典记录字符最后出现的位置，若重复则移动左指针。
时间复杂度 O(n)‌，空间复杂度 O(字符集大小)。
3. 合并两个有序链表（迭代法）

题目‌：将两个升序链表合并为一个新的升序链表。
输入样例‌：

list1 = [1,2,4], list2 = [1,3,4]

输出样例‌：

[1,1,2,3,4,4]

代码与解析‌：

python
Copy Code
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next

def mergeTwoLists(l1, l2):
dummy = ListNode()
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next

测试代码需要构造链表，此处省略构造过程

解析‌：

使用哑节点简化头节点处理。
比较两链表当前节点，依次连接较小值。
时间复杂度 O(m+n)‌，空间复杂度 O(1)。
4. 有效的括号（栈应用）

题目‌：判断只包含 (){}[] 的字符串是否有效。
输入样例‌：

s = “()[]{}”

输出样例‌：

True

代码与解析‌：

def isValid(s):
stack = []
mapping = {‘)’:‘(’, ‘]’:‘[’, ‘}’:‘{’}
for char in s:
if char in mapping:
top = stack.pop() if stack else ‘#’
if top != mapping[char]:
return False
else:
stack.append(char)
return not stack
print(isValid(“()[]{}”))

解析‌：

遇到左括号入栈，右括号则检查栈顶是否匹配。
栈为空或栈顶不匹配直接返回 False。
时间复杂度 O(n)‌，空间复杂度 O(n)。
5. 爬楼梯（动态规划）

题目‌：每次可爬1或2阶台阶，求爬到n阶的方法总数。
输入样例‌：

n = 3

输出样例‌：

代码与解析‌：

def climbStairs(n):
if n <= 2: return n
a, b = 1, 2
for _ in range(3, n+1):
a, b = b, a + b
return b
print(climbStairs(3))

解析‌：

状态转移方程：dp[i] = dp[i-1] + dp[i-2]。
用滚动变量优化空间复杂度至 O(1)。
时间复杂度 O(n)‌。
6. 二叉树的中序遍历（迭代法）

题目‌：给定二叉树根节点，返回中序遍历结果。
输入样例‌：

root = [1,null,2,3]

输出样例‌：

[1,3,2]

代码与解析‌：

class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def inorderTraversal(root):
res = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res

测试代码构造树：root = TreeNode(1, None, TreeNode(2, TreeNode(3)))

解析‌：

用栈模拟递归过程，先压左子树到尽头，再处理根节点，最后转向右子树。
时间复杂度 O(n)‌，空间复杂度 O(n)。
7. 最大子序和（动态规划）

题目‌：求整数数组中和最大的连续子数组的和。
输入样例‌：

nums = [-2,1,-3,4,-1,2,1,-5,4]

输出样例‌：

代码与解析‌：

def maxSubArray(nums):
max_sum = curr_sum = nums[0]
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

解析‌：

定义 curr_sum 表示以当前元素结尾的最大子序和。
若当前元素单独成子数组更大，则重置 curr_sum。
时间复杂度 O(n)‌，空间复杂度 O(1)。
8. 反转链表（迭代法）

题目‌：反转单链表，返回新链表的头节点。
输入样例‌：

head = [1,2,3,4,5]

输出样例‌：

[5,4,3,2,1]

代码与解析‌：

def reverseList(head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev

测试代码构造链表：1->2->3->4->5

解析‌：

用三个指针 prev, curr, next_temp 逐个反转节点指向。
时间复杂度 O(n)‌，空间复杂度 O(1)。
9. 盛最多水的容器（双指针）

题目‌：给定非负整数数组表示容器高度，求两线段与x轴组成的容器能容纳的最大水量。
输入样例‌：

height = [1,8,6,2,5,4,8,3,7]

输出样例‌：

代码与解析‌：

def maxArea(height):
left, right = 0, len(height)-1
max_area = 0
while left < right:
area = (right - left) * min(height[left], height[right])
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
print(maxArea([1,8,6,2,5,4,8,3,7]))

解析‌：

双指针从两端向中间移动，每次移动较矮的一侧以寻找更大面积。
时间复杂度 O(n)‌，空间复杂度 O(1)。
10. 三数之和（排序+双指针）

题目‌：找出数组中所有和为0的三元组，且不重复。
输入样例‌：

nums = [-1,0,1,2,-1,-4]

输出样例‌：

[[-1,-1,2], [-1,0,1]]

代码与解析‌：

def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i+1, len(nums)-1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s < 0:
left += 1
elif s > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
return res
print(threeSum([-1,0,1,2,-1,-4]))