classSolution: deftwoSum(self, nums: List[int], target: int) -> List[int]: n = len(nums) for i inrange(n): for j inrange(i+1, n): if nums[i] + nums[j] == target: return [i, j] return []
哈希表
时间复杂度$O(N)$，空间复杂度$O(N)$，为哈希表的开销
1 2 3 4 5 6 7 8
classSolution: deftwoSum(self, nums: List[int], target: int) -> List[int]: hashtable = dict() for i, num inenumerate(nums): if target - num in hashtable: return [hashtable[target - num], i] hashtable[nums[i]] = i return []
for num in nums_set: if (num - 1) notin nums_set: len = 1
while (num + len) in nums_set: len += 1 maxlen = max(maxlen, len) return maxlen
双指针
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
请注意 ，必须在不复制数组的情况下原地对数组进行操作
示例 1:
1 2
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2:
1 2
输入: nums = [0] 输出: [0]
不复制数组只能是直接交换，末尾都是0，头部都是非0值
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部[快慢指针]
右指针走的更快，以其为循环结束标志
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: defmoveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ 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
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
classSolution: defmaxArea(self, height: List[int]) -> int: area, ans = 0, 0 left, right = 0, len(height) - 1 while left < right: area = min(height[left], height[right]) * (right - left) ans = max(ans, area) if height[left] <= height[right]: left += 1 else: right -= 1
return ans
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
classSolution: defthreeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() ans = list() n = len(nums)
for c inrange(n - 2): if c > 0and nums[c] == nums[c - 1]: continue # 最小和>0，直接结束 if nums[c] + nums[c + 1] + nums[c + 2] > 0: break # 最大和<0，直接右移 if nums[c] + nums[-1] + nums[-2] < 0: continue l, r = c + 1, n - 1 while l < r: sum = nums[c] + nums[l] + nums[r] ifsum == 0: ans.append([nums[c], nums[l], nums[r]]) l += 1 r -= 1 while l < r and nums[l] == nums[l - 1]: l += 1 while l < r and nums[r] == nums[r + 1]: r -= 1 elifsum < 0: l += 1 else: r -= 1 return ans
classSolution: deflengthOfLongestSubstring(self, s: str) -> int: seen = set() left = 0 max_len = 0 for right inrange(len(s)): while s[right] in seen: seen.remove(s[left]) # 删除直到无s[right] left += 1 seen.add(s[right]) max_len = max(max_len, right - left + 1) return max_len
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
if prefix_sum - k in mp: ans += mp[prefix_sum - k]
mp[prefix_sum] = mp.get(prefix_sum, 0) + 1
return ans
枚举
起始指针不断向右移动，取起始指针往左计算和，如果累积和匹配则计数+1
但这种方法的复杂度在O(n^2)
1 2 3 4 5 6 7 8 9 10
classSolution: defsubarraySum(self, nums: List[int], k: int) -> int: ans = 0 for start inrange(len(nums)): sum = 0 for end inrange(start, -1, -1): sum += nums[end] ifsum == k: ans += 1 return ans
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
classSolution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k){ deque<int> dq; int n = nums.size(); // 获取第一个窗口内最大值的索引 for (int i = 0; i < k; i++) { // 没有优先队列的自动排序需要比较后进值与尾端值 while (!dq.empty() && nums[i] >= nums[dq.back()]) { dq.pop_back(); } dq.push_back(i); } vector<int> ans = {nums[dq.front()]}; for (int i = k; i < n; i++) { while (!dq.empty() && nums[i] >= nums[dq.back()]) { dq.pop_back(); } // 保存当前值的索引到队列尾端 dq.push_back(i); // 移出队列头部直到索引在窗口内 while (dq.front() <= i - k) { dq.pop_front(); } ans.push_back(nums[dq.front()]); } return ans; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution: defmaxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) dq = deque() for i inrange(k): while dq and nums[i] >= nums[dq[-1]]: dq.pop() dq.append(i)
ans = [nums[dq[0]]]
for i inrange(k, n): while dq and nums[i] >= nums[dq[-1]]: dq.pop() dq.append(i) while dq[0] <= i - k: dq.popleft() ans.append(nums[dq[0]]) return ans
最小覆盖子串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符(包括重复字符)。如果没有这样的子串，返回空字符串 ""
示例 1：
1 2 3
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
1 2 3
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
1 2 3 4
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
classSolution: defsetZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ m, n = len(matrix), len(matrix[0]) row, col = [False] * m, [False] * n
for i inrange(m): for j inrange(n): if matrix[i][j] == 0: row[i] = col[j] = True for i inrange(m): for j inrange(n): if row[i] or col[j]: matrix[i][j] = 0
classSolution: defspiralOrder(self, matrix: List[List[int]]) -> List[int]: left, right = 0, len(matrix[0]) - 1 top, bottom = 0, len(matrix) - 1 ans = [] while left <= right and top <= bottom: # 从左往右 for j inrange(left, right + 1): ans.append(matrix[top][j]) top += 1 # 从上往下 for i inrange(top, bottom + 1): ans.append(matrix[i][right]) right -= 1 # 必须满足才能继续输出 if top > bottom or left > right: break
# 从右往左 for j inrange(right, left - 1, -1): ans.append(matrix[bottom][j]) bottom -= 1 # 从下往上 for i inrange(bottom, top - 1, -1): ans.append(matrix[i][left]) left += 1 return ans
classSolution: defsearchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) i, j = 0, n - 1 while i < m and j >= 0: cur = matrix[i][j]
if cur < target: i += 1 elif cur > target: j -= 1 else: returnTrue
returnFalse
时间复杂度O(m+n)，空间复杂度O(1)
二分法
这里由于上下行并没有完全的大小关系，每一行都是递增，所以只能逐行二分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution: defsearchMatrix(self, matrix: List[List[int]], target: int) -> bool: for row in matrix: idx = self.lower_bound(row, target) if idx < len(row) and row[idx] == target: returnTrue
returnFalse
deflower_bound(self, nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid
return left
也可以用python的bisect.库函数
函数
含义
bisect_left
第一个 ≥ target
bisect_right
第一个 > target
1 2 3 4 5 6 7
classSolution: defsearchMatrix(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: returnTrue returnFalse
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defmiddleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow
快指针或者快指针的next为空说明到尾了，此时慢指针一定在中间位置
环形链表
给你一个链表的头节点 head ，判断链表中是否有环
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None
classSolution: defdetectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: seen = set() while head: if head in seen: return head seen.add(head) head = head.next returnNone
这种方法时间复杂度为O(n)，空间复杂度也为O(n)
方法二：快慢指针
a = 头到入口距离
b = 入口到相遇点距离
c = 环长
相遇时：慢指针走了 a + b，快指针走了 a + b + k·c
因为 fast 速度是 slow 的 2 倍：2(a + b) = a + b + k·c
整理得到： $$ a + b = k·c\qquad a = k·c − b \qquad a = (c − b) + (k−1)c $$ 这意味着：从头走 a 步等价于从相遇点在环上走 c − b 步(再加若干整圈)
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defreverseBetween( self, head: Optional[ListNode], left: int, right: int ) -> Optional[ListNode]: dummy = ListNode(next=head) p0 = dummy for _ inrange(left - 1): p0 = p0.next# 找到反转区间前一个节点
pre = None cur = p0.next
for _ inrange(right - left + 1): nxt = cur.next cur.next = pre pre = cur cur = nxt # 把两边重新接上 p0.next.next = cur # 反转后的尾连上right的后一个节点 p0.next = pre # 接上反转后的头 return dummy.next
1 2 3
dummy -> 1 -> 2 -> 3 -> 4 -> 5 ↑ p0
回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defisPalindrome(self, head: Optional[ListNode]) -> bool: arr = [] cur = head while cur: arr.append(cur.val) cur = cur.next
left, right = 0, len(arr) - 1 while left < right: if arr[left] != arr[right]: returnFalse left += 1 right -= 1
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defremoveNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) fast = slow = dummy # fast 先走 n 步 for _ inrange(n): fast = fast.next
while fast.next: fast = fast.next slow = slow.next
slow.next = slow.next.next
return dummy.next
时间复杂度O(n)，空间复杂度O(1)，且只扫描链表一次，快慢指针是最优雅的做法
删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次，返回已排序的链表
示例
1 2
输入：head = [1,1,2,3,3] 输出：[1,2,3]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defdeleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: if head isNone: return head cur = head while cur.next: # 注意这里是看cur.next if cur.next.val == cur.val: cur.next = cur.next.next else: cur = cur.next return head
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defreverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: n = 0 cur = head while cur: n += 1# 获取链表长度 cur = cur.next
dummy = ListNode(next=head) p0 = dummy # p0代表反转链表的前一个node pre = None cur = p0.next
while n >= k: # 判断反转是否结束 n -= k for _ inrange(k): # k个反转 nxt = cur.next cur.next = pre pre = cur cur = nxt nxt = p0.next# p0的next成为新的p0 p0.next.next = cur # 将下一段的头接到反转头的next p0.next = pre # 将反转尾接到p0的next p0 = nxt # 更新p0 return dummy.next
这种思路比官方解法更直观一些
随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝，深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值
新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y，返回复制链表的头节点
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
""" # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """
classSolution: defcopyRandomList(self, head: "Optional[Node]") -> "Optional[Node]": if head isNone: returnNone
node_map = {} cur = head # 第一遍：建立原节点 -> 新节点映射 while cur: node_map[cur] = Node(cur.val) cur = cur.next
# 第二遍：连接 next 和 random cur = head while cur: # 用get主要是处理None的情况，能正常返回None # node_map[cur.next]碰到None会报错 node_map[cur].next = node_map.get(cur.next) node_map[cur].random = node_map.get(cur.random) cur = cur.next
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defsortList(self, head: Optional[ListNode]) -> Optional[ListNode]: ifnot head ornot head.next: return head # 1. 计算链表长度 length = 0 cur = head while cur: cur = cur.next length += 1
dummy = ListNode(next=head) step = 1
# 2. 每轮步长翻倍 while step < length: prev = dummy cur = dummy.next
while cur: left = cur right = self.split(left, step) # 断开第一段，返回第二段head cur = self.split(right, step) # 断开第二段，返回下一段head # 合并 merge_head, merge_tail = self.merge(left, right) # 拼接 prev.next = merge_head prev = merge_tail step *= 2
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: definorderTraversal(self, root: Optional[TreeNode]) -> List[int]: result = []
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: definorderTraversal(self, root: Optional[TreeNode]) -> List[int]: result = [] stack = [] cur = root
while cur or stack: while cur: stack.append(cur) cur = cur.left # 左子树处理完，回退 cur = stack.pop() result.append(cur.val)
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defisValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool: if root isNone: returnTrue x = root.val return ( left < x < right andself.isValidBST(root.left, left, x) andself.isValidBST(root.right, x, right) )
中序遍历递归
如果是二叉搜索树，那么中序遍历应该是严格递增的序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: pre = float("-inf") defisValidBST(self, root: Optional[TreeNode]) -> bool: if root isNone: returnTrue ifnotself.isValidBST(root.left): returnFalse if root.val <= self.pre: returnFalse self.pre = root.val returnself.isValidBST(root.right)
二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
1 2
输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
1 2
输入：root = [1,null,2] 输出：2
方法一：递归，自底向上
空节点深度 = 0
当前节点深度 = max(左子树深度, 右子树深度) + 1
左子树和右子树的最大深度又可以以同样的方式进行计算，可以先递归计算出其左子树和右子树的最大深度
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defmaxDepth(self, root: Optional[TreeNode]) -> int: if root isNone: return0 l_depth = self.maxDepth(root.left) r_depth = self.maxDepth(root.right)
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defmaxDepth(self, root: Optional[TreeNode]) -> int: ans = 0
deff(node, cnt): nonlocal ans if node isNone: return cnt += 1 ans = max(ans, cnt) f(node.left, cnt) f(node.right, cnt)
f(root, 0) return ans
时间复杂度和空间复杂度均为O(n)
翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点
示例 1
1 2
输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
1 2
输入：root = [] 输出：[]
递归
递归翻转左子树
递归翻转右子树
最后在当前节点交换左右
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: definvertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root isNone: returnNone l = self.invertTree(root.left) r = self.invertTree(root.right) root.left, root.right = r, l return root
时间复杂度为O(n)，空间复杂度O(h)
相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的
示例 1：
1 2
输入：p = [1,2,3], q = [1,2,3] 输出：true
递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defisSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if p isNoneor q isNone: return p is q # 只有均为None时True return ( p.val == q.val andself.isSameTree(p.left, q.left) andself.isSameTree(p.right, q.right) )
对称二叉树
给你一个二叉树的根节点 root ，检查它是否轴对称
示例 1：
1 2
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
1 2
输入：root = [1,2,2,null,3,null,3] 输出：false
**进阶：**你可以运用递归和迭代两种方法解决这个问题吗？
方法一：递归
可以借鉴相同的树定义一个新函数，来判断左右两边是否对称相等
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defisSymmetric(self, root: Optional[TreeNode]) -> bool: defisMirror(p, q): if p isNoneor q isNone: return p is q return ( p.val == q.val and isMirror(p.left, q.right) and isMirror(p.right, q.left) ) return isMirror(root.left, root.right)
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defisBalanced(self, root: Optional[TreeNode]) -> bool: defget_height(node): if node isNone: return0
left = get_height(node.left) if left == -1: return -1 right = get_height(node.right) if right == -1orabs(left - right) > 1: return -1 returnmax(left, right) + 1
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defrightSideView(self, root: Optional[TreeNode]) -> List[int]: ans = []
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: deflevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root isNone: return [] ans = [] cur = [root] while cur: nxt = [] vals = [] for node in cur: vals.append(node.val) if node.left: nxt.append(node.left) if node.right: nxt.append(node.right) cur = nxt ans.append(vals)
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: deflevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root isNone: return [] ans = [] dq = deque([root]) while dq: vals = [] for _ inrange(len(dq)): node = dq.popleft() vals.append(node.val) if node.left: dq.append(node.left) if node.right: dq.append(node.right) ans.append(vals) return ans
找树左下角的值
给定一个二叉树的 根节点root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点
示例:
1 2
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
可以采用层序遍历，然后输出最左的值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: deffindBottomLeftValue(self, root: Optional[TreeNode]) -> int: dq = deque([root]) ans = root.val while dq: ans = dq[0].val for _ inrange(len(dq)): node = dq.popleft() if node.left: dq.append(node.left) if node.right: dq.append(node.right) return ans
或者从右往左读，这样最后一个读的节点就是左下角的点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: deffindBottomLeftValue(self, root: Optional[TreeNode]) -> int: dq = deque([root]) while dq: node = dq.popleft() if node.right: dq.append(node.right) if node.left: dq.append(node.left) return node.val
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defsortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: defbuild(left, right): if left > right: returnNone
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defpathSum(self, root: Optional[TreeNode], targetSum: int) -> int: defrootSum(root, targetSum): if root isNone: return0 ret = 0
if root.val == targetSum: ret +=1 ret += rootSum(root.left, targetSum-root.val) ret +=rootSum(root.right,targetSum-root.val) return ret if root isNone: return0 ret = rootSum(root, targetSum) # 重点，如果不加就会变为固定起点了 ret+= self.pathSum(root.left, targetSum) ret += self.pathSum(root.right, targetSum)
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None classSolution: deflowestCommonAncestor( self, root: "TreeNode", p: "TreeNode", q: "TreeNode" ) -> "TreeNode": if root isNoneor root is p or root is q: return root
left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root if left: return left return right
classSolution: defletterCombinations(self, digits: str) -> List[str]: n = len(digits) if n == 0: return [] ans = [] path = [""] * n defdfs(i): if i == n: ans.append("".join(path)) # 走到尽头就加入答案 return for c in MAPPING[int(digits[i])]: path[i] = c dfs(i + 1) dfs(0) return ans
二分查找
如果左闭右开
1 2 3 4 5 6 7 8 9 10 11
deflower_bound(nums: List[int], target: int) -> int: left = 0 right = len(nums) # 左闭右开区间[left, right) while left < right: # 区间不为空 mid = (left + right) // 2 if nums[mid] < target: left = mid + 1# [mid+1, right) else: right = mid # [left, mid)
classSolution: defsearchInsert(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left
classSolution: defsearchMatrix(self, matrix: List[List[int]], target: int) -> bool: m = len(matrix) n = len(matrix[0])
left = 0 right = m * n while left < right: mid = left + (right - left) // 2 row = mid // n col = mid % n val = matrix[row][col] if val < target: left = mid + 1 elif val > target: right = mid else: returnTrue
.webp)
