hot100
1. 两数之和
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for i, num in enumerate(nums):
if target - num in d:
return [i, d[target- num]]
d[num] = i
49. 字母异位词分组
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = {}
for str in strs:
str_ = "".join(sorted(str))
if str_ not in d:
d[str_] = [str]
else:
d[str_].append(str)
return list(d.values())
128. 最长连续序列✨
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
max_len = 0
for i in s:
if i - 1 not in s: # 只需要从开头开始枚举
j = i
len_ = 0
while (j in s):
j += 1
len_ += 1
max_len = max(max_len, len_)
return max_len
283. 移动零
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
ln = len(nums)
for i in range(ln):
if nums[i] == 0:
j = i
while j + 1 < ln and nums[j] == 0:
j += 1
print(i, j)
nums[i], nums[j] = nums[j], nums[i]
## 官方
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
left = right = 0
while right < n:
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
11. 成水最多的容器
class Solution:
def maxArea(self, h: List[int]) -> int:
l, r = 0, len(h) - 1
res = 0
while l < r:
area = min(h[l], h[r]) * (r - l)
res = max(res, area)
if h[l] <= h[r]:
l += 1
else:
r -= 1
return res
15.三数之和
推荐题解：https://leetcode.cn/problems/3sum/solutions/11525/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
ln = len(nums)
if ln < 3:
return res
for a in range(ln - 2):
if nums[a] > 0:
return res
if a > 0 and nums[a] == nums[a - 1]:
continue
b, c = a + 1, ln - 1
while b < c:
s = nums[a] + nums[b] + nums[c]
if s < 0:
b += 1
while b < c and nums[b] == nums[b - 1]: b += 1
elif s > 0:
c -= 1
while b < c and nums[c] == nums[c + 1]: c -= 1
else:
res.append([nums[a], nums[b], nums[c]])
b += 1
c -= 1
while b < c and nums[b] == nums[b - 1]: b += 1
while b < c and nums[c] == nums[c + 1]: c -= 1
return res
42. 接雨水
class Solution:
def trap(self, h: List[int]) -> int:
res = 0
stack = []
for i in range(len(h)):
while stack and h[stack[-1]] < h[i]:
cur = stack.pop()
if not stack: #前面也没有高的柱子，不可能接到雨水
break
height = min(h[i], h[stack[-1]]) - h[cur] #当前能接到的雨水高度
res += (i - stack[-1] - 1) * height
stack.append(i)
return res
3. 无重复字符的最长子串
def lengthOfLongestSubstring(self, s: str) -> int:
s_ = set()
res = 0
l, r = 0, 0
while r < len(s):
while r < len(s) and s[r] not in s_:
s_.add(s[r])
r += 1
res = max(res, r - l)
while l < r and r < len(s) and s[l] != s[r]:
s_.remove(s[l])
l += 1
l += 1
r += 1
return res
比较简略的c++写法：
int lengthOfLongestSubstring(string s) {
int len = 0;
int n = s.size();
unordered_set<char> set;
for (int i = 0, j = 0; j < n; j++) {
while (set.count(s[j]))
set.erase(s[i++]);
set.insert(s[j]);
len = max(len, j - i + 1);
}
return len;
}
438. 找到字符串中所有字母异位词
固定滑动窗口
def findAnagrams(self, s: str, p: str) -> List[int]:
slen , plen = len(s), len(p)
if slen < plen:
return []
ans = []
s_ = [0] * 26
p_ = [0] * 26
for i in range(plen):
s_[ord(s[i]) - 97] += 1
p_[ord(p[i]) - 97] += 1
if s_ == p_:
ans.append(0)
for i in range(slen - plen):
s_[ord(s[i]) - 97] -= 1
s_[ord(s[i + plen]) - 97] += 1
if s_ == p_:
ans.append(i + 1)
return ans
560. 和为 K 的子数组
前缀和 + hash（cnt保存当前以0为左边界所有前缀和出现的次数）
def subarraySum(self, nums: List[int], k: int) -> int:
ans = s = 0
cnt = defaultdict(int)
for x in nums:
cnt[s] += 1
s += x
ans += cnt[s - k] ##之间为k
return ans
239. 滑动窗口最大值
简单做法：堆保存数据，右移时判断堆顶元素是否在窗口内
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
q = [(-nums[i], i) for i in range(k)]
heapq.heapify(q)
ans = [-q[0][0]]
for i in range(k, n):
heapq.heappush(q, (-nums[i], i))
while (q[0][1] < i - k + 1):
heapq.heappop(q)
ans.append(-q[0][0])
return ans
优化：单调队列（不需要维护所有元素，只需要维护一个单调递减的队列元素，左侧的小元素相比于右侧大元素永远不可能成为答案）
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans = [0] * (len(nums) - k + 1)
q = deque()
for i, x in enumerate(nums):
while q and nums[q[-1]] <= x:
q.pop()
q.append(i)
left = i - k + 1
if q[0] < left:
q.popleft()
if left >= 0:
ans[left] = nums[q[0]]
return ans
76. 最小覆盖子串
简单做法：
def minWindow(self, s: str, t: str) -> str:
cnt_s = Counter()
cnt_t = Counter(t)
res_l, res_r = -1, len(s) - 1
l = 0
for r, c in enumerate(s):
cnt_s[c] += 1
while cnt_s >= cnt_t:
if res_r - res_l > r - l:
res_r = r
res_l = l
cnt_s[s[l]] -= 1
l += 1
if res_l >= 0:
return s[res_l:res_r + 1]
else:
return ""
用一个变量维护字符满足数量要求的个数，就不用每次都比较字典：
def minWindow(self, s: str, t: str) -> str:
cnt = defaultdict(int)
for c in t:
cnt[c] += 1
ln = len(cnt)
res_l, res_r = -1, len(s) - 1
l = 0
for r, c in enumerate(s):
cnt[c] -= 1
if cnt[c] == 0:
ln -= 1
while ln == 0:
if res_r - res_l > r - l:
res_r = r
res_l = l
if cnt[s[l]] == 0: # 需要改变ln长度]
ln += 1
cnt[s[l]] += 1
l += 1
if res_l >= 0:
return s[res_l:res_r + 1]
else:
return ""
53. 最大子数组和
前缀和做法
def maxSubArray(self, nums: List[int]) -> int:
ans = -inf
min_sum = cur_sum = 0
for x in nums:
cur_sum += x
ans = max(ans, cur_sum - min_sum)
min_sum = min(min_sum, cur_sum)
return ans
动态规划也有做法，这个留作专题练习
56. 合并区间
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
ans = []
for x in intervals:
if ans and x[0] <= ans[-1][1]:
ans[-1][1] = max(ans[-1][1], x[1])
else:
ans.append(x)
return ans
189. 轮转数组
最简单的做法，需要o(n)的连续内存
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
tmp = []
for i in range(len(nums) - k, 2 * len(nums) - k):
tmp.append(nums[i % len(nums)])
for i in range(len(nums)):
nums[i] = tmp[i]
负负得正，旋转数组法：
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
n = len(nums)
k %= n
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
238. 除自身以外数组的乘积
不能用除法，除法需要特判0，同时有0的时候其他位置的元素也需要特殊考虑。获取前缀积与后缀积即可求出当前位置的乘积
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
pre = [1] * n
for i in range(1, n):
pre[i] = pre[i - 1] * nums[i - 1]
suf = [1] * n
for i in range(n - 2, -1, -1):
suf[i] = suf[i + 1] * nums[i + 1]
return [p * s for p, s in zip(pre, suf)]
41.缺失的第一个正数
空间复杂度为O(n)的方法
def firstMissingPositive(self, nums: List[int]) -> int:
s = set()
for x in nums:
if x >=0:
s.add(x)
res = 1
while res in s:
res += 1
return res
答案只会在[1, len(nums) + 1]的范围内 空间复杂度为O(1)的方法是将原数组作为一个hash表，不另外申请空间，即nums[i]表达i + 1是否存在
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i, x in enumerate(nums):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1https://leetcode.cn/problems/set-matrix-zeroes/
73.矩阵置零
最朴素的想法是遍历矩阵，为0的话在行列置0，但是这样是错误的，会把后面的0也会统计进去：
- 使用 O(mn) 的额外空间：统计每个元素是否需要置零
- 使用 O(m + n)的额外空间：统计每行每列是否需要制0：
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m = len(matrix)
n = len(matrix[0])
row = [False] * m
col = [False] * n
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = True
col[j] = True
for i in range(m):
if row[i]:
for j in range(n):
matrix[i][j] = 0
for j in range(n):
if col[j]:
for i in range(m):
matrix[i][j] = 0
常数额外空间做法看：链接
54. 螺旋矩阵
设置方向矩阵表示当前方向很关键
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
DIR = (0, 1), (1, 0), (0, -1), (-1, 0)
m, n = len(matrix), len(matrix[0])
ans = []
i = j = di = 0
for _ in range(m * n):
ans.append(matrix[i][j])
matrix[i][j] = None
x, y = i + DIR[di][0], j + DIR[di][1] #下一步zuobiao
if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] is None:
di = (di + 1) % 4
i += DIR[di][0]
j += DIR[di][1]
return ans
48. 旋转图像
顺时针旋转相当于把矩阵按照主对角线翻转 + 把每一行翻转，详情见链接
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n):
for j in range(i):#自动过滤0, 0
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(n):
matrix[i].reverse()
240. 搜索二维矩阵 II
这个做法不是最优，更优见链接
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
idx = bisect.bisect_left(row, target)
if idx < len(row) and row[idx] == target:
return True
return False
160. 相交链表https://leetcode.cn/problems/spiral-matrix/
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p, q = headA, headB
while p is not q:
p = p.next if p is not None else headB
q = q.next if q is not None else headA
return p
206. 反转链表
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
p = head
res = None
while p:
q = ListNode(p.val, res)
res = q
p = p.next
return res
234. 回文链表
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# 中间节点
mid = head
p = head
while p and p.next:
mid = mid.next
p = p.next.next
# 反转链表
p = mid
pre = None
while p:
nt = p.next
p.next = pre
pre = p
p = nt
# 开始判断
while pre:
if pre.val != head.val:
return False
head = head.next
pre = pre.next
return True
141. 环形链表
快慢指针方法
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast is slow:
return True
return False
或者Hash方法：
def hasCycle(self, head: ListNode) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
21. 合并两个有序链表
使用一个哨兵节点指向头节点能省略很多if判断情况（头节点为空的时候的插入）
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode()
while list1 and list2:
if list1.val < list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 or list2 # 插入剩下不为空
return dummy.next
2. 两数相加
### 递归做法
class Solution:
# l1 和 l2 为当前遍历的节点，carry 为进位
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
if l1 is None and l2 is None and carry == 0: # 递归边界
return None
s = carry
if l1:
s += l1.val # 累加进位与节点值
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
# s 除以 10 的余数为当前节点值，商为进位
return ListNode(s % 10, self.addTwoNumbers(l1, l2, s // 10))
### 迭代做法，使用哨兵保存头节点 + carry累计
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode() # 哨兵节点
carry = 0 # 进位
while l1 or l2 or carry: # 有一个不是空节点，或者还有进位，就继续迭代
if l1:
carry += l1.val # 节点值和进位加在一起
l1 = l1.next # 下一个节点
if l2:
carry += l2.val # 节点值和进位加在一起
l2 = l2.next # 下一个节点
cur.next = ListNode(carry % 10) # 每个节点保存一个数位
carry //= 10 # 新的进位
cur = cur.next # 下一个节点
return dummy.next # 哨兵节点的下一个节点就是头节点
19. 删除链表的倒数第 N 个结点
快指针应该到最后一个节点，慢指针指向删除前一个节点，对于删除第一个节点的情况，需要有哨兵节点。
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
slow = fast = dummy = ListNode(next=head)
for i in range(n):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
24. 两两交换链表中的节点
换值
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
left = right = head
if right is None or right.next is None:
return head
right = right.next
while left and right:
tmp = left.val
left.val = right.val
right.val = tmp
if left.next and left.next.next:
left = left.next.next
else:
left = None
if right.next and right.next.next:
right = right.next.next
else:
right = None
return head
使用哨兵节点，交换节点
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
node0 = dummy = ListNode(next=head) # 用哨兵节点简化代码逻辑
node1 = head
while node1 and node1.next: # 至少有两个节点
node2 = node1.next
node3 = node2.next
node0.next = node2 # 0 -> 2
node2.next = node1 # 2 -> 1
node1.next = node3 # 1 -> 3
node0 = node1 # 下一轮交换，0 是 1
node1 = node3 # 下一轮交换，1 是 3
return dummy.next # 返回新链表的头节点
138. 随机链表的复制
顺序复制无法拷贝random，使用hash表建立原节点与新节点的映射，通过源节点random构建新节点
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return
cur = head
dic = {}
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
dic[cur].next = dic.get(cur.next)#
dic[cur].random = dic.get(cur.random) # 可能为null
cur = cur.next
return dic[head]
K 个一组翻转链表
def reverse(self, head: Optional[ListNode], tail: Optional[ListNode]):
stop = tail.next
pre = stop
cur = head
while cur != stop: # 尾部链接 非原地反转
nextcur = cur.next
cur.next = pre
pre = cur
cur = nextcur
# 原地反转
# nxt = cur.next
# cur.next = pre # 每次循环只修改一个 next，方便大家理解
# pre = cur
# cur = nxt
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
h = l = r = ListNode(next=head) # dummy head
while True:
for _ in range(k):
r = r.next
if not r:
return h.next
nextl = l.next
self.reverse(nextl, r)
l.next = r # dummy head 连接
l = r = nextl # 下一组的前一个元素作为新的dummy head
148. 排序链表
归并排序链表版本
class Solution:
def midNode(self, head):
s = f = head
while f and f.next:
pre = s #记录s前一个节点，断开
s = s.next
f = f.next.next
pre.next = None
return s
def mergeList(self, head, head2):
cur = dummy = ListNode()
while head and head2:
if head.val < head2.val:
cur.next = head
head = head.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
cur.next = head if head else head2
return dummy.next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
head2 = self.midNode(head)
head = self.sortList(head)
head2 = self.sortList(head2)
return self.mergeList(head, head2)
23. 合并 K 个升序链表
方法1：可能插入的节点只有可能是头节点，使用最小堆保存所有头节点
ListNode.__lt__ = lambda a, b: a.val < b.val
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
cur = dummy = ListNode()
h = [head for head in lists if head]
heapify(h)
while h:
node = heappop(h)
if node.next:
heappush(h, node.next)
cur.next = node
cur = cur.next
return dummy.next
方法2：将数组分为两个子数组，归并排序
class Solution:
def mergeTwoLists(self, head, head2):
cur = dummy = ListNode()
while head and head2:
if head.val < head2.val:
cur.next = head
head = head.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
cur.next = head if head else head2
return dummy.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
n = len(lists)
if n == 0:
return None
if n == 1:
return lists[0]
left = self.mergeKLists(lists[:n//2])
right = self.mergeKLists(lists[n//2:])
return self.mergeTwoLists(left, right)
146. LRU 缓存
dict + 双向链表
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dummy = Node()
self.dummy.prev = self.dummy
self.dummy.next = self.dummy
self.key_to_node = dict()
def remove(self, x):
x.prev.next = x.next
x.next.prev = x.prev
def push_front(self, x):
x.prev = self.dummy
x.next = self.dummy.next
self.dummy.next = x
x.next.prev = x
def get_node(self, k):
if k not in self.key_to_node:
return None
node = self.key_to_node[k]
self.remove(node)
self.push_front(node)
return node
def get(self, key: int) -> int:
node = self.get_node(key)
return node.val if node else -1
def put(self, key: int, val: int) -> None:
node = self.get_node(key)
if node:
node.val = val
return
self.key_to_node[key] = node = Node(key, val)
self.push_front(node)
if len(self.key_to_node) > self.capacity:
last_node = self.dummy.prev
del self.key_to_node[last_node.key]
self.remove(last_node)
114. 二叉树展开为链表
class Solution:
head = None
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return
self.flatten(root.right)
self.flatten(root.left)
root.left = None
root.right = self.head
self.head = root
94.二叉树的中序遍历
递归做法
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
非递归做法：自己维护栈
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
st = []
res = []
while (root or len(st)):
while (root):
st.append(root)
root = root.left
root = st[-1]
st.pop()
res.append(root.val)
root = root.right
return res
104. 二叉树的最大深度
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
226. 翻转二叉树
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return
tmp = root.right
root.right = self.invertTree(root.left)
root.left = self.invertTree(tmp)
return root
101. 对称二叉树
class Solution:
def isSameTree(self, p, q):
if p is None or q is None:
return p is q
return p.val == q.val and self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.isSameTree(root.left, root.right)
543. 二叉树的直径
注意最长直径并不一定经过root
class Solution:
ans = 0
def maxDepth(self, root):
if root is None:
return 0
l = self.maxDepth(root.left)
r = self.maxDepth(root.right)
self.ans = max(self.ans, l + r)
return 1 + max(l , r)
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.maxDepth(root)
return self.ans
102.二叉树的层序遍历
注意返回数组中一层是在一个数组中，因此需要一层一层出队列，而不是逐个元素出队列
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
ans = []
q = [root]
while q:
vals = []
for _ in range(len(q)):
cur = q.pop(0)
vals.append(cur.val)
if cur.left: q.append(cur.left)
if cur.right: q.append(cur.right)
ans.append(vals)
return ans
108. 将有序数组转换为二叉搜索树
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if len(nums) == 0:
return None
m = len(nums) // 2
left = self.sortedArrayToBST(nums[:m])
right = self.sortedArrayToBST(nums[m + 1:])
return TreeNode(nums[m], left, right)
98. 验证二叉搜索树
前序
def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
if root is None:
return True
x = root.val
return left < x < right and \
self.isValidBST(root.left, left, x) and \
self.isValidBST(root.right, x, right)
230. 二叉搜索树中第 K 小的元素
我的做法，比较麻烦，没有想到中序遍历
class Solution:
def num_node(self, root):
num = 0
if not root:
return 0
q = [root]
while len(q):
t = q.pop(0)
num += 1
if t.left: q.append(t.left)
if t.right: q.append(t.right)
return num
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
cur = root
before = 0
while cur:
numl = self.num_node(cur.left)
numr = self.num_node(cur.right) + before + 1 + numl
numl += before
print(cur.val, numl, numr)
if 0 < k <= numl:
cur = cur.left
elif k == numl + 1:
return cur.val
elif numl + 1 < k <= numr:
cur = cur.right
before = numl + 1
更好的做法：中序遍历，出栈时k-=1
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
199. 二叉树的右视图
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = [root]
res = []
while len(q):
num = len(q)
res.append(q[-1].val)
for _ in range(num):
t = q.pop(0)
if t.left: q.append(t.left)
if t.right: q.append(t.right)
return res
105. 从前序与中序遍历序列构造二叉树
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder: # 空节点
return None
left_size = inorder.index(preorder[0]) # 左子树的大小
left = self.buildTree(preorder[1: 1 + left_size], inorder[:left_size])
right = self.buildTree(preorder[1 + left_size:], inorder[1 + left_size:])
return TreeNode(preorder[0], left, right)
可优化的点：预处理值与下标、函数传数组下标而不是数组
46. 全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
path = [0] * n
st = [False] * n
def dfs(i):
if i == n:
ans.append(path.copy())
return
for j, s in enumerate(st):
if not s:
path[i] = nums[j]
st[j] = True
dfs(i + 1)
st[j] = False
dfs(0)
return ans
78. 子集
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
path = []
def dfs(i):
ans.append(path.copy())
for j in range(i, n):
path.append(nums[j])
dfs(j + 1) # 非全排列，表示i -> j - 1都不选
path.pop()
dfs(0)
return ans
17. 电话号码的字母组合
全排列变形
class Solution:
MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
def letterCombinations(self, digits: str) -> List[str]:
n = len(digits)
if n == 0:
return []
ans = []
path = [''] * n
def dfs(i):
if i == n:
ans.append(''.join(path))
return
for c in self.MAPPING[int(digits[i])]:
path[i] = c
dfs(i + 1)
dfs(0)
return ans
39. 组合总和
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
def dfs(nums, sum, target, cur, prev):
nonlocal ans
if sum == target:
ans.append(cur)
for n in nums:
if sum + n <= target and n >= prev:
dfs(nums, sum + n, target, cur + [n], n)
dfs(candidates, 0, target, [], -inf)
return ans
22. 括号生成
def generateParenthesis(self, n: int) -> List[str]:
ans = []
path = [''] * (n * 2)
def dfs(l, r) -> None:
if r == n:
ans.append(''.join(path))
return
if l < n:
path[l + r] = '('
dfs(l + 1, r)
if r < l:
path[l + r] = ')'
dfs(l, r + 1)
dfs(0, 0)
return ans
79. 单词搜索
def exist(self, board: List[List[str]], word: str) -> bool:
cnt = Counter(c for row in board for c in row)
if not cnt >= Counter(word): # 优化一
return False
if cnt[word[-1]] < cnt[word[0]]: # 优化二
word = word[::-1]
m, n = len(board), len(board[0])
def dfs(i, j, k) -> bool:
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
board[i][j] = ''
for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):
return True
board[i][j] = word[k]
return False
return any(dfs(i, j, 0) for i in range(m) for j in range(n))
35. 搜索插入位置
def searchInsert(self, nums: List[int], target: int) -> int:
def check(v):
return v >= target
l, r = -1, len(nums)
while l + 1 < r:
mid = (l + r) // 2
if check(nums[mid]):
r = mid
else:
l = mid
return r
74. 搜索二维矩阵
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
arr = []
for m in matrix:
arr += m
def check(x):
return x >= target
l, r = -1, len(arr)
while l + 1 < r:
mid = (l + r) // 2
if (check(arr[mid])): r = mid
else: l = mid
return r < len(arr) and arr[r] == target
20. 有效的括号
class Solution:
def isValid(self, s: str) -> bool:
st = []
left = ['[', '{', '(']
right = [']', '}', ')']
if len(s) % 2 != 0:
return False
for c in s:
if c in left:
st.append(c)
elif c in right:
if len(st) == 0:
return False
if c == '}' and st[-1] != '{':
return False
if c == ')' and st[-1] != '(':
return False
if c == ']' and st[-1] != '[':
return False
st.pop()
return len(st) == 0