从零到一：LeetCode Hot 100（少走弯路版）

Ne0inhk

23 Mar 2026 — 64 min read

初学者刷题遇到的问题

发现自己做 LeetCode 时没有思路？做完一遍后下次仍然不会？

原因一：LeetCode 题是循序渐进的，某些知识点可能会依赖另一个的知识点。如果前置知识不足，那么解题时肯定会晕头转向，依赖关系如下

解决方法：依照此图，从上往下依次刷题。

原因二：做题囫囵吞枣（仅仅只是抄答案，甚至是复制粘贴），不思考，不总结。

解决方法：

去思考。拿出纸笔，动手去写（输入是什么？输出是什么？题目的 Feature（特征）是什么，根据特征，选择哪种数据结构和算法 ）。

LeetCode 题可以锻炼我们的建模能力（用 20% 的关键信息，解决 80% 的现实问题的作弊器）

特征就是这 20% 的关键信息，然后根据特征选择数据结构和算法，去解决问题

去总结。总结常见的解题技巧和它的模板（例如：哈希，双指针，二分查找，回溯、贪心等）。总结的目的是将其当作解题的工具，这样的话，下次解题时可以想到去使用它并快速写出相关代码。 如何总结？通过问 Why it work？（为什么题目这样写起作用？）下文有相关的例子供大家参考。

原因三：选用的编程语言的语法繁琐。

解决方法：推荐使用 Python，可以将注意力集中在解题思路上，而不是编程语言的语法。

原因四：没有复习做过的题

解决方法：去复习，Review 很重要

哈希表

Why it work?

常见的三种哈希结构，用哪个？：

1. 数组（长度受限，用于类似字母这种长度确定的，键的规则就是

，值就是加 1 ）

2. set（只能存放一个key，自动去重）

3. dict（可以保存两个值：<key, value>）

使用场景：

想清楚键和值用什么表示

快速判断一个元素是否出现在集合里

1. 两数之和

暴力枚举

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range (i + 1, len(nums)): if nums[i] + nums[j] == target: return i, j

需要查找某个元素是否存在，并且用到下标和值，所以用 dict 结构

通过一次遍历，利用哈希表记录已访问过的数字及其索引，从而能以 O(1) 的速度瞬间找回使当前数凑成目标值的那个“补数”

class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: # {} 等同于 dict() hashmap = {} # enumerate:在遍历列表的同时，给你下表和值 # 如果减的值在哈希表中，那么就找到了这两个数 for index, value in enumerate(nums): if target - value in hashmap: return [index, hashmap[target - value]] else: hashmap[value] = index

字母异位词分组

数组结构

利用“字符出现的频率”作为哈希表的唯一键来对字母异位词进行分组

class Solution: # 使用数组结构，自定义键的算法 def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # 创建一个“键不存在时自动初始化成空列表”的字典 mp = collections.defaultdict(list) for str in strs: counts = [0] * 26 for ch in str: counts[ord(ch) - ord("a")] += 1 # 哈希表的键要求不可变，而列表counts可以变，tuple不可变 mp[tuple(counts)].append(str) return list(mp.values())

最长连续序列

set 结构

利用哈希表实现 O(1) 查找，并采用“只从序列车头（即 num-1 不存在时）开始往后数”的剪枝策略，确保每个数字只被遍历常数次，从而将 O(n^2) 的搜索优化为 O(n) 的线性处理

class Solution: def longestConsecutive(self, nums: List[int]) -> int: hashset = set(nums) maxLength = 0 for num in hashset: # 去掉无效操作（如果它前面还有值，一定不是最长的） if num - 1 not in hashset: curLength = 1 while num + 1 in hashset: curLength += 1 num += 1 maxLength = max(curLength, maxLength) return maxLength

242. 有效的字母异位词

自己创建哈希表（固定长度数组模拟哈希表）和哈希函数（字符偏移量映射索引），通过哈希表中最后的值（加减抵消的逻辑）来判断两个组的词相不相同

class Solution: # 手动用数组实现了一个哈希表 def isAnagram(self, s: str, t: str) -> bool: hashmap = [0] * 26 for i in s: # ord 获取 ASCII 码 hashmap[ord(i) - ord('a')] += 1 for i in t: hashmap[ord(i) - ord('a')] -= 1 for i in hashmap: if i != 0: return False return True

349. 两个数组的交集

set 结构

class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: # 转化为集合，自动去重 set1 = set(nums1) set2 = set(nums2) res = set1.intersection(set2) return list(res)

字符串

344. 反转字符串

双指针，python 中字符列表 List[str] 可以直接替换两个字符的位置

class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ left = 0 right = len(s) - 1 while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1

151. 翻转字符串里的单词

利用快慢指针删除多的空格，再配合“先整体翻转、后单词局部翻转”的策略实现单词顺序的倒置。不能一蹴而就，一步一步地达成目标

class Solution: def reverseRange(self, s, start, end): # 辅助函数，翻转指定区间的元素（单词） while start < end: s[start], s[end] = s[end], s[start] start += 1 end -= 1 def reverseWords(self, s: str) -> str: s_list = list(s) slow = 0 fast = 0 n = len(s) while fast < n: # 如果快指针找到了不为空的元素 if s_list[fast] != ' ': # 如果不是第一个元素，就要加空格 if slow != 0: s_list[slow] = ' ' slow += 1 # fast < n 是边界条件 while fast < n and s_list[fast] != ' ': s_list[slow] = s_list[fast] slow += 1 fast += 1 fast += 1 # 慢指针之前的就是删除空格之后的字符串 s_list = s_list[:slow] s_list.reverse() # 将空格之前的单词进行反转 left = 0 for right in range(len(s_list)): if s_list[right] == ' ': self.reverseRange(s_list, left, right - 1) left = right + 1 # 边界情况特殊处理 elif right == len(s_list) - 1: self.reverseRange(s_list, left, right) return "".join(s_list)

双指针

Why it work

使用场景：利用数据结构的有序性或特定逻辑（ 两个影响题目答案的限制条件 ），用两个变量（指针）同时遍历，从而把 O(n^2) 的暴力复杂度降到 O(n)

指针的移动是有目的的（ 为了求出最后的答案而移动，不是乱移动），两个for循环嵌套也就是双指针，只不过指针的移动是固定的

快慢指针：

快指针一直移动，直到最后一个元素，每次移动代表着根据题意处理接下来的一个元素
慢指针在快指针进行判断且满足题意时移动，每次移动代表着慢指针之前的元素就是要的答案

左右指针：两个指针分别位于首尾，并向中间靠拢的技巧

使用场景：需要用到左右指针的关系，比如：左指针小于右指针，或者需要左右指针之间的距离。
根据题意来决定如何移动左右指针
模板：while left < right

移动零

快慢指针

class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) slow = 0 fast = 0 while fast < n: if nums[fast] != 0: nums[fast], nums[slow] = nums[slow], nums[fast] slow += 1 fast += 1

盛水最多的容器

左右指针

class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) left = 0 right = n - 1 maxVol = 0 while left < right: vol = (right - left) * min(height[left], height[right]) maxVol = max(vol, maxVol) if height[left] < height[right]: left += 1 else: right -= 1 return maxVol

15. 三数之和（三元组不重复）

左右指针

先排序以方便去重和左右指针的方向感，再固定一个数，利用左右指针从两端向中间“夹逼”寻找另外两个数。

用三个数之和来决定左指针动还是右指针动

class Solution: # 双指针 def threeSum(self, nums: List[int]) -> List[List[int]]: # 排序，方便用左右指针 nums.sort() result = [] # 固定一个数 for i in range(len(nums)): if nums[i] > 0: return result # 跳过首个相同的元素 # 用 i > 0 and nums[i] == nums[i - 1]而不是 nums[i] == nums[i + 1]，防止出界 if i > 0 and nums[i] == nums[i - 1]: continue # 左右指针 left = i + 1 right = len(nums) - 1 while left < right: sum = nums[i] + nums[left] + nums[right] if sum < 0: left += 1 elif sum > 0: right -= 1 else: result.append([nums[i],nums[left],nums[right]]) # 跳过 left, right 相同的元素,left < 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 result

二分查找

Why it work?

使用条件：数组是有序的

使用场景：寻找特定值

时间复杂度：O(log n)

本质：将搜索范围一分为二，缩小搜索区域（用双指针来控制）

循环条件是小于等于号（left <= right）：因为当最后只剩两个相邻值时，例如：left = 1 和 right = 2 时，mid =（left + right）// 2 = 1，查找的 mid 就是 left，如果 left 不是要查找的值，就需要再次循环去看 right，left 必须要可以等于 mid + 1，而 mid + 1 就等于 right

模板：

class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1

搜索插入的位置

class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left , right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return left

搜索二维矩阵

class Solution: # 将二维索引展开，看成一维 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: mid = (left + right) // 2 row = mid // n col = mid % n if matrix[row][col] == target: return True elif matrix[row][col] < target: left = mid + 1 else: right = mid - 1 return False

第一个和最后一个位置

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 使用两次二分查找，查两个位置 def findFirst(nums, target): left, right = 0, len(nums) - 1 first = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: first = mid right = mid - 1 # 继续查找左侧 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return first def findLast(nums, target): left, right = 0, len(nums) - 1 last = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: last = mid left = mid + 1 # 继续查找右侧 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return last first = findFirst(nums, target) last = findLast(nums, target) if first == -1 or last == -1: return [-1, -1] return [first, last]

搜索旋转排序数组

class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # 左半部分有序 # <= 为了正确判断哪一部分是有序的，即使只有一个元素 if nums[left] <= nums[mid]: # target 包含在左边 if nums[left] <= target < nums[mid]: right = mid - 1 # target 在右边 else: left = mid + 1 # 右半部分有序 else: # target 包含在右边 if nums[mid] < target <= nums[right]: left = mid + 1 # target 在左边 else: right = mid - 1 return -1

寻找排序数组中最小值

class Solution: # 用中间的和右边的比：看最小值在哪边（缩小范围） def findMin(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 # 此题有 <= 会死循环 while left < right: mid = (left + right) // 2 if nums[mid] > nums[right]: left = mid + 1 else: right = mid return nums[left]

滑动窗口

Why it work

本质：用双指针（类似快慢指针）来表示一个可以移动的大小可变区间，调节子序列的起始位置和终止位置

优点：始终处理连续的子串或子数组，避免了重复计算

模板：left = 0（指向左边界），右指针用 for 循环来表示，for 循环内部的左指针根据题意移动。指针移动时增减哈希表里的元素（用哈希表来知道窗口内部是个什么情况）

无重复字符的最长子串

利用“滑动窗口”机制，通过 right 指针向右扩张寻找新字符，一旦撞上重复字符，就移动 left 指针像“挤牙膏”一样将其剔除，从而动态维护窗口内始终是不重复的子串

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: left = 0 hashset = set() maxLength = 0 for right in range(len(s)): while s[right] in hashset: hashset.remove(s[left]) left += 1 hashset.add(s[right]) curLength = right - left + 1 maxLength = max(maxLength, curLength) return maxLength

找字符串中所有异位词

维护一个长度恒等于 p 的“定长滑动窗口”，通过 Counter 实时对比窗口内外的字符频率分布，当两者完全匹配时，即锁定了异位词的起始位置。

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: # 自带计数器和排序功能的智能管家 # 例: Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}) pHahsMap = Counter(p) sHashMap = Counter() n = len(s) res = [] left = 0 for right in range(n): sHashMap[s[right]] += 1 # p 的长度决定了窗口长度 if right - left + 1 > len(p): sHashMap[s[left]] -= 1 left += 1 if sHashMap == pHahsMap: res.append(left) return res

链表

Why it work

学会去运用节点的指向来完成想要的操作

模板：

1. dummy_head = ListNode() 用来表示头节点

作用：避免多写步骤去处理头节点

注意：此时 dummy_head 并没有和题目给出的链表相连接（也就是没有指向链表的头节点），想要连接可以这样初始化，dummy_head = ListNode(0, head)

2. current = dummy_head，用来遍历的节点

作用：不改变 head

移动链表的节点：

current = current.next

3. 修改节点指向时，需要保存中间节点

160. 相交链表

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: # 使用哈希集合 visited = set() # 遍历链表的模板 currentA = headA # currentA 是用来遍历的节点 while currentA: visited.add(currentA) currentA = currentA.next currentB = headB while currentB: if currentB in visited: return currentB currentB = currentB.next return None

消除长度差来实现同步。走过你的路，我们终会相遇（数学方法）

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: if not headA or not headB: return None pA = headA pB = headB while pA != pB: if pA: pA = pA.next else: pA = headB # 简写 pB = pB.next if pB else headA return pA

206. 反转链表

解题思路：想清楚怎么连接链表 + 保存中间节点（不然就丢失了后续的指向）

快慢指针法：

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = None fast = head while fast: temp = fast.next fast.next = slow slow = fast fast = temp return slow

递归法：根据双指针改来的

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: return self.reverse(head, None) def reverse(self, cur: ListNode, pre:ListNode): if cur == None: return pre temp = cur.next cur.next = pre return self.reverse(temp, cur)

回文链表

class Solution: # 将链表复制到数组中，然后使用双指针 def isPalindrome(self, head: Optional[ListNode]) -> bool: vals = [] current_node = head while current_node is not None: vals.append(current_node.val) current_node = current_node.next left, right = 0, len(vals) - 1 while left < right: if vals[left] != vals[right]: return False left += 1 right -= 1 return True

141. 环形链表

class Solution: # 使用哈希集合 def hasCycle(self, head: Optional[ListNode]) -> bool: seen = set() while head: if head in seen: return True seen.add(head) head = head.next return False

快慢指针，弗洛伊德循环查找算法（数学方法）

慢指针（slow）：每次只走一步
快指针（fast）：每次走两步

如果链表没有环，快指针会率先到达终点（指向 None）。如果链表有环，快指针最终一定会“套圈”慢指针，两人会在环内的某个位置相遇

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = head fast = head # 必须保证 fast 和 fast.next 都不为空，这样才能安全地执行 fast.next.next while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False

21. 合并两个有序链表

想清楚链表怎么连接

用一个新链表来保存结果

class Solution: # 类似于双指针，只不过指针的移动是靠链表节点向后移动完成的 def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy_head = ListNode(-1) current = dummy_head while list1 and list2: if list1.val <= list2.val: current.next = list1 list1 = list1.next else: current.next = list2 list2 = list2.next current = current.next current.next = list1 if list1 is not None else list2 return dummy_head.next

两数之和

class Solution: # 注意进位 def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: carry = 0 dummy_head = ListNode() current = dummy_head while l1 or l2 or carry: val1 = l1.val if l1 else 0 val2 = l2.val if l2 else 0 sum = val1 + val2 + carry carry = sum // 10 # 进位 current.next = ListNode(sum % 10) current = current.next if l1: l1 = l1.next if l2: l2 = l2.next return dummy_head.next

19. 删除链表的倒数第N个节点

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: def getLength(head: ListNode) -> int: length = 0 while head: length += 1 head = head.next return length dummy_head = ListNode(0, head) cur = dummy_head length = getLength(head) for i in range(0, length - n): cur = cur.next cur.next = cur.next.next return dummy_head.next

用双指针找到要删除节点的前一个节点：因为快指针先走了 n + 1 步，然后快指针和慢指针一起走，直到快指针走完全部节点，此时，慢指针就是倒数第 n + 1 个数

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy_head = ListNode(0, head) fast, slow = dummy_head, dummy_head for i in range(n + 1): fast = fast.next while fast: fast = fast.next slow = slow.next slow.next = slow.next.next return dummy_head.next

24. 两两交换链表中的节点

模拟行为：

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: # 分为步骤一二三 dummy_head = ListNode(0,head) cur = dummy_head while cur.next and cur.next.next: temp = cur.next temp1 = cur.next.next.next cur.next = cur.next.next cur.next.next = temp temp.next = temp1 cur = cur.next.next return dummy_head.next

递归：

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: # 递归 def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: # base case if not head or not head.next: return head # 基操 newHead = head.next # 自己调用自己（大问题变子问题） head.next = self.swapPairs(newHead.next) # 基操 newHead.next = head # return return newHead

排序链表

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: # 归并算法，本质是分治，分（递归） def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: # base case if not head or not head.next: return head # 找中间点，使用快慢指针，一般来说 fast = head 即可，但是此题要用 # fast = head.next 来避免死循环，例如：1 -> 2 -> None , 会分不开，导致一直递归 slow, fast = head, head.next while fast and fast.next: # 慢指针一次一步，快指针一次两步 slow = slow.next fast = fast.next.next # 将链表从中间切开 mid = slow.next slow.next = None # 自己调用自己 left = self.sortList(head) right = self.sortList(mid) # 调用合并函数 return self.mergeTwoLists(left, right) # 治（合并） def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode: dummy_head = ListNode() current = dummy_head while l1 and l2: if l1.val < l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next # 如果某个链表没取完 if l1: current.next = l1 if l2: current.next = l2 return dummy_head.next

203. 移除链表元素

虚拟头节点法，以空间换简洁，如果没有虚拟头节点，在操作链表（尤其是删除和插入）时，通常需要写两套逻辑：一套处理普通节点，一套处理头节点。

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummy_head = ListNode(0, head) current = dummy_head while current.next: if current.next.val == val: current.next = current.next.next else: current = current.next return dummy_head.next

707. 设计链表

虚拟头节点，取点，加点，删点（这三个操作，借助 current 的移动来完成）

class ListNode: def __init__(self, val = 0, next = None): self.val = val self.next = next class MyLinkedList: def __init__(self): self.dummy_head = ListNode() self.size = 0 def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 current = self.dummy_head for i in range(index): current = current.next return current.next.val def addAtHead(self, val: int) -> None: # 先保存原来的头节点 mid = self.dummy_head.next # 将新节点和原来的头节点连起来 self.dummy_head.next = ListNode(val, mid) self.size += 1 def addAtTail(self, val: int) -> None: current = self.dummy_head while current.next: current = current.next current.next = ListNode(val) self.size += 1 def addAtIndex(self, index: int, val: int) -> None: if index < 0 or index > self.size: return current = self.dummy_head for i in range(index): current = current.next mid = current.next current.next = ListNode(val, mid) self.size += 1 def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return current = self.dummy_head for i in range(index): current = current.next current.next = current.next.next self.size -= 1 # Your MyLinkedList object will be instantiated and called as such: # obj = MyLinkedList() # param_1 = obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index)

数组

Why it work

可以直接取出或使用某个 index 位置的元素

方法：

二分法，双指针（快慢，左右），滑动窗口，模拟行为，前缀和

最大子数组和

暴力递归（枚举所有子数组）

class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) max_sum = float('-inf') for i in range(n): for j in range(i, n): cur_sum = sum(nums[i : j + 1]) max_sum = max(cur_sum, max_sum) return max_sum

动态规划

class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) dp = [float('-inf')] * n dp[0] = nums[0] max_sum = nums[0] for i in range(1, n): dp[i] = max(dp[i - 1] + nums[i], nums[i]) max_sum = max(max_sum, dp[i]) return max_sum

合并区间

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: # 把一个由区间组成的列表 intervals 按区间的左端点升序排序 intervals.sort(key = lambda x : x[0]) merge = [] for interval in intervals: # -1 表示倒数第一个元素 if not merge or merge[-1][1] < interval[0]: merge.append(interval) else: merge[-1][1] = max(merge[-1][1], interval[1]) return merge

轮转数组

class Solution: def rotate(self, nums: List[int], k: int) -> None: length = len(nums) # # python 的数组不会自动初始化，Java 会默认初始化为 0 ans = [0] * length for i in range (length): ans[(i + k) % length] = nums[i] # 这道题需要返回原数组 # nums[:] = ans，换内容：把 ans 里的元素拷贝进原来那块内存（保留 nums 的原内存） # nums = ans，换标签：将 nums 指向 ans 指向的那块内存 nums[:] = ans

除自身以外数组的乘积

class Solution: # 构造两个新的数组（前缀积和后缀积数组） def productExceptSelf(self, nums: List[int]) -> List[int]: pre, post, answer = [0] * len(nums), [0] * len(nums), [0] * len(nums) pre[0] = 1 for i in range (1, len(nums)): # 上一个数的前缀和乘上上一个数等于这个数的前缀和 pre[i] = pre[i - 1] * nums[i - 1] post[len(nums) - 1] = 1 for i in reversed(range(len(nums) - 1)): post[i] = post[i + 1] * nums[i + 1] for i in range(len(nums)): answer[i] = pre[i] * post[i] return answer

27. 移除元素

暴力解法

class Solution: # 本质：向前覆盖 def removeElement(self, nums: List[int], val: int) -> int: i,l =0, len(nums) - 1 while i < l: if nums[i] == val: for j in range(i, l): nums[j] = nums[j + 1] l -= 1 i -= 1 i += 1 return l

最优解：双指针，需要的留在前面，不需要的放在后面

class Solution: # 双指针 def removeElement(self, nums: List[int], val: int) -> int: slow = 0 fast = 0 for fast in range(len(nums)): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 return slow

977. 有序数组的平方和

双指针 - 左右指针，每次可以找到一个最大的值出来

class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) left = 0 right = n - 1 result = [0] * n while left <= right: if nums[left] * nums[left] < nums[right] * nums[right]: square = nums[right] * nums[right] result[n - 1] = square right -= 1 # n 也随着循环来变，用来找到放在数组的哪个位置 n -= 1 else: square = nums[left] * nums[left] result[n - 1] = square left += 1 n -= 1 return result

209. 长度最小的子数组

滑动窗口，如果大于了目标值，窗口前端就缩小

class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) left = 0 right = 0 cur_sum = 0 res = float('inf') # 滑动窗口的右指针用 for 循环，内部嵌套一个 while 循环作为慢指针 for right in range(n): cur_sum += nums[right] while cur_sum >= target: res = min(res, right -left + 1) cur_sum -= nums[left] left += 1 # 如果所有相加都小于target return res if res != float('inf') else 0

59. 螺旋矩阵Ⅱ

模拟行为：根据边界，循环填值

class Solution: def generateMatrix(self, n: int) -> List[List[int]]: if n <= 0: return [] matrix = [[0] * n for _ in range(n)] top, bottom, left, right = 0, n - 1, 0, n - 1 num = 1 while top <= bottom and left <= right: # 上边界 for i in range(left, right + 1): matrix[top][i] = num num += 1 top += 1 for i in range(top, bottom + 1): matrix[i][right] = num num += 1 right -= 1 for i in range(right, left - 1): matrix[bottom][i] = num num += 1 bottom -= 1 for i in range(bottom, top - 1): matrix[i][left] = num num += 1 left += 1 return matrix

代码随想录：区间和

前缀和，ACM 写法（需要自己处理原始的字符流，还要打印结果）

import sys input = sys.stdin.read def main(): data = input().split() index = 0 n = int(data[index]) index += 1 vec = n * [0] for i in range(n): vec[i] = int(data[index]) index += 1 # 计算前缀和 p = [0] * n pre_sum = 0 for i in range(n): pre_sum += vec[i] p[i] = pre_sum results = [] while index < len(data): a = int(data[index]) b = int(data[index + 1]) index += 2 if a == 0: sum_value = p[b] else: sum_value = p[b] - p[a - 1] results.append(sum_value) for result in results: print(result) if __name__ == "__main__": main()

栈

Why it work?

使用场景：匹配问题（利用栈（Stack）的“后进先出”特性，实时对比当前字符与栈顶元素）

用于嵌套的题型（一个代码块中包含另一个代码块），子操作很像但又不完全相同

利用栈的先入后出（ 题目数据符合的一种顺序，进入栈的都被存储下来了，取出的时候顺序是反的）

注意栈里放的是什么，获得的启发：用数据结构里的数据表示更多与解题有关的信息 ，不同算法使得相同的数据结构（但是里面的数据不一样）可以解决不同的题

模板：在某些条件下（对题意抽象）入栈和出栈

20. 有效的括号

class Solution: def isValid(self, s: str) -> bool: if len(s) % 2 == 1: return False pairs = { ")":"(", "}":"{", "]":"[" } # 栈 stack = list() # 根据题意写入栈出栈操作 for x in s: if x not in pairs: stack.append(x) else: if not stack or stack[-1] != pairs[x]: return False stack.pop() return not stack

仅使用栈，用于对称匹配

class Solution: def isValid(self, s: str) -> bool: stack = [] for item in s: if item == '(': stack.append(')') elif item == '[': stack.append(']') elif item == '{': stack.append('}') elif not stack or stack[-1] != item: return False else: stack.pop() return True

最小栈

# 自定义一个最小栈，方法都是为了服务这个最小栈 class MinStack: def __init__(self): self.stack = [] self.min_stack = [math.inf] def push(self, val: int) -> None: self.stack.append(val) self.min_stack.append(min(val, self.min_stack[-1])) def pop(self) -> None: self.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()

字符串解码

class Solution: # 左括号和右括号抽象成条件，遇到时进行入栈和出栈操作 def decodeString(self, s: str) -> str: count_stack = [] string_stack = [] current_num = 0 for char in s: if char.isdigit(): # 如果是多位数，需要 current_num * 10，因为一次读一个数字 current_num = current_num * 10 + int(char) # 左括号说明开始了一个新的字符串（抽象） elif char == "[": count_stack.append(current_num) string_stack.append(current_string) current_num = 0 elif char == "]": repeat_times = count_stack.pop() last_string = string_stack.pop() current_string = last_string + current_string * repeat_times else: current_string += char return current_string

每日温度

class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) answer = [0] * n stack = [] for i in range(n): cur = temperatures[i] while stack and cur > temperatures[stack[-1]]: index = stack.pop() wait_days = i - index answer[index] = wait_days stack.append(i) return answer

232. 用栈实现队列

利用两个栈，将入第一个栈的元素放到第二个栈里，第二个栈出来的时候就是先入先出了

class MyQueue: def __init__(self): self.stack_in = [] self.stack_out = [] def push(self, x: int) -> None: self.stack_in.append(x) def pop(self) -> int: for i in range(len(self.stack_in)): stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) -> int: for i in range(len(self.stack_in)): self.stack_out.append(self.stack_in.pop()) temp = self.stack_out.pop() self.stack_out.append(temp) return temp def empty(self) -> bool: return not self.stack_out

225. 用队列实现栈

利用两个队列，想要实现先入后出，通过将队列前 n-1 个元素迁移到辅助队列来孤立并获取原本位于队尾的最新元素

class MyStack: def __init__(self): self.queue_in = deque() self.queue_out = deque() def push(self, x: int) -> None: self.queue_in.append(x) def pop(self) -> int: for i in range(len(self.queue_in) - 1): self.queue_out.append(self.queue_in.popleft()) self.queue_in, self.queue_out = self.queue_out, self.queue_in return self.queue_out.popleft() def top(self) -> int: for i in range(len(self.queue_in) - 1): self.queue_out.append(self.queue_in.popleft()) self.queue_in, self.queue_out = self.queue_out, self.queue_in temp = self.queue_out.popleft() self.queue_out.append(temp) return temp def empty(self) -> bool: # queue_in 是主仓库，out 是辅助仓库 return not self.queue_in

1047. 删除字符中的所有相邻重复项

匹配问题，利用栈（Stack）的“后进先出”特性，通过实时对比当前字符与栈顶元素，实现相邻重复项的成对抵消

class Solution: def removeDuplicates(self, s: str) -> str: res = list() for item in s: if res and res[-1] == item: res.pop() else: res.append(item) return "".join(res)

二叉树

Why it work?

适合用递归、栈，因为二叉树可以分为多个子二叉树，子问题操作步骤相同，子二叉树都满足条件的话，二叉树也就满足条件

递归：用于大问题可以拆分为许多操作步骤一样的子问题

新定义一个递归函数的时机：原函数的参数不够或返回值不方便直接递归的时候就

特点自己调用自己（大问题 -> 类似的子问题，模板：调用自己时传入的参数会变 ）根据如何拆成子问题的思路，来写子问题的基本操作和 returnbase case （最小子问题的出递归条件）

递归三部曲

0. 理解递归的作用是什么确定递归函数的参数和返回值确定终止条件（base case，出递归的条件）确定单层递归的逻辑（前中后序的哪一种？）

遍历树的时候进行操作：

1. 深度优先搜索（ 递归法和迭代法 ），判断使用前中后哪个序的递归逻辑，然后用递归三部曲

2. 广度优先搜索（迭代法：借助队列）

# 广度优先搜索 def levelOrder(root): result = [] if not root: return result queue = deque([root]) while queue: level_size = len(queue) # 当前层的节点个数 level_nodes = [] # 遍历当前层的所有节点 for _ in range(level_size): node = queue.popleft() # 语法：从队首移除并返回一个元素，pop 是从队尾 level_nodes.append(node.val) # 将该节点的值添加到当前层的列表中 # 如果该节点有左子节点，入队 if node.left: queue.append(node.left) # 如果该节点有右子节点，入队 if node.right: queue.append(node.right) result.append(level_nodes) return result

求深度（高度）的变形？

104. 二叉树的最大深度

深度：二叉树中任意一个节点到根节点的距离。自顶向下：使用前序遍历

高度：二叉树中任意一个节点到叶子节点的距离。自底向上：使用后序遍历，将左右的处理过程返回给中节点

此题，根节点的高度就是二叉树的最大深度，所以用后续遍历

递归的作用是求高度

class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 return self.getHeight(root) def getHeight(self, root:TreeNode) -> int: if not root: return 0 leftHeight = self.getHeight(root.left) rightHeight = self.getHeight(root.right) maxHeight = max(leftHeight, rightHeight) + 1 return maxHeight

class TreeNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right class Solution: def maxDepth(self, root:TreeNode) -> int: # base case if not root: return 0 # 单层递归的逻辑，最大深度即根节点的高度，所以使用后序 leftHeight = self.maxDepth(root.left) rightHeight = self.maxDepth(root.right) maxHeight = max(leftHeight, rightHeight) + 1 return maxHeight

层序遍历

class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return [] depth = 0 queue = deque([root]) while queue: n = len(queue) for i in range(n): # 拿出来一个，再把拿出来的左右节点加到队列里去 node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth += 1 return depth

111. 二叉树的最小深度

根节点的最小高度就是最小深度，所以也是用的后序

class Solution: # 深度，递归，后序 def minDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 return self.getHeight(root) def getHeight(self, root:TreeNode) -> int: if not root: return 0 leftHeight = self.getHeight(root.left) rightHeight = self.getHeight(root.right) # 左子树为空或右子树为空的特殊情况 if root.left == None and root.right != None: return 1 + rightHeight if root.left != None and root.right == None: return 1 + leftHeight minHeight = min(leftHeight,rightHeight) + 1 return minHeight

226. 翻转二叉树

利用前序遍历的递归法，改单层递归逻辑

每次将中间节点的左节点和右节点交换位置

class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return None # 单层递归逻辑 # 中逻辑 root.left, root.right = root.right, root.left # 左逻辑 self.invertTree(root.left) # 右逻辑 self.invertTree(root.right) return root

101. 对称二叉树

class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True return self.isMirror(root.left, root.right) # 递归 def isMirror(self, left: TreeNode, right: TreeNode) -> bool: # base case if not left and not right: return True if not left or not right: return False return (left.val == right.val) and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

因为要比较左节点的左右节点和右节点的左右节点是否对称，所以递归中需要传入两个节点。

处理了左右节点后才知道中节点，所以使用后序递归（收集孩子的信息向上一步返回的题目时候用后序列）

class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True return self.compare(root.left,root.right) # 递归函数的参数是左右节点 def compare(self, left: TreeNode, right: TreeNode) -> bool: # base case if left == None and right != None: return False elif left != None and right == None: return False elif left == None and right == None: return True elif left.val != right.val: return False outside = self.compare(left.left,right.right) inside = self.compare(left.right, right.left) return outside and inside

110. 平衡二叉树

处理递归时，决定是“只用一个函数”还是“多加一个辅助函数”：取决于你从子节点需要获取的信息，是否就是最终要求的答案

左右子树高度差的绝对值要小于一，利用递归后序 + 找高度

class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: if not root: return True if self.getHeight(root) == -1: return False else: return True def getHeight(self, root:TreeNode) -> int: if not root: return 0 # 需要检查左子树，如果左边已经坏了，直接把 -1 返回，算是 base case leftHeight = self.getHeight(root.left) if leftHeight == -1: return -1 rightHeight = self.getHeight(root.right) if rightHeight == -1: return -1 if abs(leftHeight - rightHeight) > 1: return -1 else: return 1 + max(leftHeight, rightHeight)

222. 完全二叉树的节点个数

完全二叉树的情况下，左深度和右深度相同的话，就是满二叉树，满二叉树的节点个数是2的深度次方 - 1，利用递归后序（普通二叉树在这里就可以直接算出来）再在base case 里加上判断是否是完全二叉树的操作

class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if not root: return 0 # 判断是否是满二叉树，左子树深度是否等于右子树深度，这算是 base case # 因为是完全二叉树，所以只需要 left.left 和 right.right 的深度一致就可以了，里面是满的 left.right 的高度和 left.left 的高度一致 left = root.left right = root.right leftDepth = 0 rightDepth = 0 while left: left = left.left leftDepth += 1 while right: right = right.right rightDepth += 1 if leftDepth == rightDepth: return (2 << leftDepth) - 1 # 单层递归循环 return 1 + self.countNodes(root.left) + self.countNodes(root.right)

二叉树的直径

利用计算高度来计算直径，所以需要一个新的函数（计算高度的函数

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def diameterOfBinaryTree(self, root:TreeNode) -> int: ans = 0 def depth(node:TreeNode): # 作用：这个 ans 不是我新定义的，是外面那一层的 nonlocal ans if not node: return 0 leftHigh = depth(node.left) rightHigh = depth(node.right) # 真正要求的直径 ans = max(ans, (leftHigh + rightHigh)) maxHeight = max(leftHigh, rightHigh) + 1 return maxHeight depth(root) return ans

）

class Solution: # 递归：大问题变小问题：左子树高 + 右子树高度 def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.ans = 0 def dfs(node:TreeNode) -> int: if not node: return 0 left_h = dfs(node.left) right_h = dfs(node.right) self.ans = max(self.ans, left_h + right_h) return max(left_h, right_h) + 1 dfs(root) return self.ans

102. 二叉树的层序遍历

弹出的时候把这个节点的左右节点加进队列

弹出的个数取决于当前队列中元素的个数

class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] res = [] # deque() 的括号里期待的是一个“一串东西”（可迭代对象） queue = deque([root]) while queue: level = [] for i in range(len(queue)): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res

108. 有序数组转二叉搜索树

二叉搜索树的中序遍历就是从小到大的有序数组

分治策略，通过递归地将当前有序数组的中心元素作为子树根节点，从而确保构建出的二叉搜索树（BST）是高度平衡的

class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: if not nums: return left = 0 right = len(nums) - 1 mid = (left + right) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid+1:]) return root

98. 验证二叉搜索树

单层递归逻辑：前序

因为不仅节点的左孩子要比它小、右孩子要比它大，而且整个左子树的所有节点都要小于当前节点，整个右子树的所有节点都要大于当前节点。所以需要 low 和 high

class TreeNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right class Solution: def isValidBST(self, root:TreeNode) -> bool: def reverse(node, low = -float('inf'), high = float('inf')) -> bool: if not node: return True if not (low < node.val < high): return False return (reverse(node.left, low, node.val) and reverse(node.right, node.val, high)) return reverse(root)

由于二叉搜索树的性质，中序遍历的出来的数组应是递增的，所以可以借助判断元素是不是单调递增的来判断是否是二叉搜索树

class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: vec = [] # 内部辅助函数，不需要 self, 因为可以查到外部的变量，包括self # self 的作用是区别对象 def dfs(root): if not root: return dfs(root.left) vec.append(root.val) dfs(root.right) return vec dfs(root) # 如果用len(vec),比较 i 和 i + 1的大小的话，会出现索引出界的问题 for i in range(1, len(vec)): if vec[i] <= vec[i -1]: return False return True

二叉搜索树中第 k 小元素

class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: vec = [] def dfs(root): if not root: return dfs(root.left) vec.append(root.val) dfs(root.right) dfs(root) return vec[k - 1]

class Solution: # 中序遍历使用栈 def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: stack = [] current = root while stack or current: while current: stack.append(current) current = current.left current = stack.pop() k -= 1 if k == 0: return current.val current = current.right

199. 二叉树的右视图

方法一：

class Solution: # 广度优先的变形 def rightSideView(self, root: Optional[TreeNode]) -> List[int]: result = [] if not root: return result queue = deque([root]) while queue: k = -1 level_size = len(queue) for _ in range(level_size): node = queue.popleft() k += 1 if k == level_size - 1: result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result

方法二：

class Solution: # 广度优先变形 def rightSideView(self, root: Optional[TreeNode]) -> List[int]: result = [] if not root: return result queue = deque([root]) while queue: level_size = len(queue) leve_nodes = [] for _ in range(level_size): node = queue.popleft() leve_nodes.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(leve_nodes[-1]) return result

层序遍历的变形，将每一层的最后一个值拿出来就是右视图的值

class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] queue = deque([root]) while queue: n = len(queue) for i in range(len(queue)): node = queue.popleft() # 如果这里用 i == len(queue) 会发生错误，因为上面一行node的弹出让queue的长度变了 # 所以长度最好还是先用n表示出来，避免后面操作导致长度变了，但忘记了，导致逻辑错误 if i == n - 1: res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res

二叉树展开为链表

# 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 class Solution: # 前序遍历 + 修改 right,left 的连接 def flatten(self, root: Optional[TreeNode]) -> None: arr = [] def dfs(node:TreeNode): if not node: return # 这里传入的是树节点,所以后面才可以用 arr[i].left or .right 这个属性 arr.append(node) dfs(node.left) dfs(node.right) dfs(root) for i in range(len(arr)): arr[i].left = None if i + 1 < len(arr): arr[i].right = arr[i + 1]

144. 94 145 二叉树的前中后序遍历

递归法

写的时候思考递归三部曲。前中后序的递归，仅仅差别在 res.append(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 class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] def dfs(node): if node is None: return # 单层递归的逻辑 # 中 res.append(node.val) # 左 dfs(node.left) # 右 dfs(node.right) dfs(root) return res

迭代法

利用栈，一点一点得到结果，让栈里出的顺序满足遍历的顺序。栈的作用：在递归遍历中，计算机底层会自动利用系统栈来保存每一层函数的局部变量和返回地址。当改用迭代法时，这套自动化的“保存机制”没了，所以必须手动维护一个栈来记录那些“已经路过但尚未处理完”的节点

前序遍历，利用栈的“后进先出”（LIFO）特性，通过先压入右子节点再压入左子节点的顺序，手动模拟递归调用栈，从而实现“根→左→右”的前序遍历顺序

class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] stack = [root] res = [] while stack: # 弹出的节点是上一轮压入的子节点，对于以这个节点为根的子树来说，它就是中节点 node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res

后续遍历，将前序代码改成变成中右左，再反转数组 res，变成左右中

class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] stack = [root] while stack: node = stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return res[::-1]

中序遍历，不能用修改前序遍历的代码来达成，因为访问顺序和处理顺序不一样，所以需要使用一个指针来控制访问顺序和处理顺序一致

class Solution: # 使用栈 def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] stack = [] cur = root while cur or stack: # 有左就往栈加左（先左）上一个左就是这个树的中，else 里cur = cur.right，到这里就成了加右 if cur: stack.append(cur) cur = cur.left # 弹出的就是左，没左，弹出的就是中，再去寻找右 else: cur = stack.pop() res.append(cur.val) cur = cur.right return res

106. 从中序与后序遍历序列构造二叉树

用后序找中间节点，利用其去中序中切割左右区间，再利用左区间的长度去切割后序

递归三部曲，单层递归逻辑就是解题的逻辑，而不是前中后序

想明白递归的作用是什么，此题就是把数组分成左边和右边，对应左子树和右子树

class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: if not postorder: return None # 后序遍历的最后一个节点作为根节点 root_val = postorder[-1] root = TreeNode(root_val) # 利用后序的最后节点，找到中序的切割点进行切割 separator_index = inorder.index(root_val) inorder_left = inorder[:separator_index] inorder_right = inorder[separator_index + 1:] # 用中序切割的左右来切割后序，且有中序数组大小等于后序数组大小 postorder_left = postorder[: len(inorder_left)] postorder_right = postorder[len(inorder_left) : -1] root.left = self.buildTree(inorder_left, postorder_left) root.right = self.buildTree(inorder_right, postorder_right) return root

105. 从前序与中序遍历序列构造二叉树

本质和 106 一样

# 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 class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: if not preorder: return None # 前序遍历第一个节点作为根节点 rootVal = preorder[0] root = TreeNode(rootVal) # 利用前序遍历找到的根节点，找到中序的切割点进行切割 separatorIndex = inorder.index(rootVal) inorderLeft = inorder[:separatorIndex] inorderRight = inorder[separatorIndex + 1:] # 用中序切割得到的长度回到前序再去切割 preorderLeft = preorder[1: 1 + len(inorderLeft)] preorderRight = preorder[1 + len(inorderLeft):] root.left = self.buildTree(preorderLeft, inorderLeft) root.right = self.buildTree(preorderRight, inorderRight) return root

617. 合并二叉树

前序递归

class Solution: def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]: if not root1: return root2 if not root2: return root1 root = TreeNode() root.val = root1.val + root2.val root.left = self.mergeTrees(root1.left, root2.left) root.right = self.mergeTrees(root1.right, root2.right) return root

700. 二叉搜索树中的搜索

递归三部曲 + 单层递归逻辑时用上搜索二叉树的性质

class Solution: def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: if (root == None or root.val == val): return root if (root.val < val): return self.searchBST(root.right, val) if (root.val > val): return self.searchBST(root.left, val)

236. 二叉树的最近公共祖先

后序遍历自底向上回溯，当某个节点发现其左、右子树各包含一个目标节点（p 或 q）时，该节点即为最近公共祖先

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if root == p or root == q or root == None: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left is not None and right is not None: return root if left is None and right is not None: return right elif left is not None and right is None: return left else: return None

图论

Why it work

邻接表：用一个列表来存储每个节点的相邻节点

入度：指向该节点边的数量

深度优先搜索（递归）

广度优先搜索（队列）

拓扑排序：对有向无环图的顶点进行排序，使得对于每个有向边 u→v，顶点 u 都在顶点 v 之前

岛屿数量

class Solution: # 深度优先 def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 def dfs(x, y): # base case:超出网格边界，或者单元格是水 if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == '0': return grid[x][y] = "0" dfs(x + 1, y) dfs(x - 1, y) dfs(x, y + 1) dfs(x, y - 1) island_count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': dfs(i, j) island_count += 1 return island_count

课程表

class Solution: # 基于 BFS 的拓扑排序算法(有向无环图) def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 邻接表 graph = defaultdict(list) # 入度 int_degree = [0] * numCourses # 构建邻接表和入度 for course, prereq in prerequisites: graph[prereq].append(course) int_degree[course] += 1 # 将入度为 0 的课程加入队列，表示它没有先修课程 queue = deque([i for i in range(numCourses) if int_degree[i] == 0]) # 已经完成的课程数量 complete_courses = 0 while queue: course = queue.pop() complete_courses += 1 # 遍历依赖于当前课程的课程 for next_course in graph[course]: int_degree[next_course] -= 1 # 入度为 0 ，再加进队列中。队列中只保留入度为 0 的 if int_degree[next_course] == 0: queue.append(next_course) return complete_courses == numCourses

堆

Why it work

定义：一种特殊（最大堆或最小堆）的完全二叉树

最小堆：任意一个节点的值 <= 它的子节点的值。根节点是堆中最小的值。

用下列方法进行堆的操作：

插入：heapq.heappush( heap, item )：把新元素放在数组末尾，然后“上浮”到合适位置
取出最小：heapq.heappop( heap )：把堆顶元素删除，用最后一个元素补到堆顶，然后“下沉”
查看最小：heap[0]

数组中的第 K 个最大元素

# 快速选择算法，和快排的区别在于只递归处理包含目标元素的子数组 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def quickSelect(left, right, k_smallest): if left == right: return nums[left] # 正着数第 k 个就是要找的 k real_index_k = len(nums) - k # 随机选择基准值，交换到数组末尾 pivot_index = random.randint(left, right) nums[right], nums[pivot_index] = nums[pivot_index], nums[right] # 分区 pivot = nums[right] i = left - 1 # 左指针 for j in range(left, right): # 右指针，遍历数组 if nums[j] <= pivot: # i 指向的是小于等于pivot的位置 i += 1 nums[i], nums[j] = nums[j], nums[i] # 把 pivot 放到正确的位置 i + 1 上, 因为pivot的最终位置应该是大于等于 pivot 和小于等于 pivot 的区域之间 nums[i + 1], nums[right] = nums[right], nums[i + 1] pivot_index = i + 1 # 根据 pivot_index 和 real_index_k 决定递归方向 if pivot_index == real_index_k: return nums[pivot_index] elif pivot_index < real_index_k: return quickSelect(pivot_index + 1, right, real_index_k) else: return quickSelect(left, pivot_index - 1, real_index_k) return quickSelect(0, len(nums) - 1, k)

前 K 个高频元素

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: # Counter 将数组变成 {数字：出现次数} 的字典 freq = Counter(nums) min_heap = [] # .items() 将字典转化成元组 for num, count in freq.items(): # 这里将频率和数字这个 list 放入堆中，且频率在前, python 默认为小根堆 heapq.heappush(min_heap, (count, num)) if len(min_heap) > k: heapq.heappop(min_heap) return [num for count, num in min_heap]

贪心算法

Why it work

每一步执行当前看起来最好的决定。通过更新，得到目前看来最好的结果

全局最优可以由局部最优推导而来

模板：每一次 for 循环得到局部最优（ 1. 用 max 或 min 找到最好的决定 2. 根据题目想要的结果写代码），执行完 for 循环得到全局最优

买股票的最佳时机

class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices or len(prices) < 2: return 0 # 记录买股票的最小值 min_price = prices[0] max_profit = 0 for price in prices[1:]: max_profit = max(max_profit, price - min_price) # 如果当前价格更低，更新最小值 min_price = min(price, min_price) return max_profit

跳跃游戏

class Solution: def canJump(self, nums: List[int]) -> bool: n = len(nums) if n <= 1: return True max_reach = 0 for i in range(n): if max_reach < i: return False max_reach = max(max_reach, i + nums[i]) if max_reach >= n - 1: return True

跳跃游戏Ⅱ

class Solution: def jump(self, nums: List[int]) -> int: n = len(nums) if n <= 1: return 0 max_reach = 0 jumps = 0 # 当前这一轮能跳到的最远位置 current_end = 0 # 最后一个位置不需要跳出去，所以是 n - 1 for i in range(n - 1): max_reach = max(max_reach, i + nums[i]) # 如果当前能跳的最远距离都没到终点，那就要继续跳 if i == current_end: # 需要继续跳 jumps += 1 # 更新能到达的最大距离 current_end = max_reach return jumps

划分字母区间

class Solution: def partitionLabels(self, s: str) -> List[int]: n = len(s) last_pos = {} # enumerate:把一个可迭代对象（比如列表、字符串等）变成一个带索引的迭代器，每次迭代返回两个值：(索引, 元素) for idx, ch in enumerate(s): last_pos[ch] = idx res = [] start = 0 end = 0 for i, ch in enumerate(s): end = max(end, last_pos[ch]) if i == end: length = i - start + 1 res.append(length) start = i + 1 return res

回溯法

Why it work

递归（ 探索所有可能的解 ） + 回溯（ 找到一个解或确定当前路径不可行时（剪枝的思想））

回溯：撤销递归的基本操作

回溯法模板：

void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }

路径是递归的参数（选择下一个节点进行操作），选择列表是当前存储的结果

处理节点基本就是选择节点然后加到当前的结果集"选择列表"里，回溯就是将“选择列表”里的节点拿出来

回溯三部曲函数的参数和返回值（返回值一般为 void ）确定终止条件（到达了叶子节点）单层搜索的逻辑

为什么回溯法要在递归外面套一个 for 循环？

将搜索过程想象成一棵树（决策树），for 循环代表“横向”遍历，递归代表“纵向”遍历

46.全排列

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] path = [] used = [False] * len(nums) def backtrack(): if len(path) == len(nums): # path 是可变对象，传入的是引用而不是拷贝，加上[:]才是拷贝 res.append(path[:]) return for i in range(len(nums)): if used[i]: continue path.append(nums[i]) used[i] = True backtrack() path.pop() used[i] = False backtrack() return res

Python 支持闭包，内部函数可以直接访问外部函数作用域里的变量

用 used 数组标记使用过哪些元素

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] used = [False] * len(nums) self.backtracking(nums, used, [], res) return res def backtracking(self, nums, used, path, res): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) self.backtracking(nums, used, path, res) used[i] = False path.pop()

78. 子集

利用 startIndex 保证不重复

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] self.backtracking(nums, 0, [], res) return res def backtracking(self, nums, startIndex, path, res): # 每一层都要存放结果 res.append(path[:]) if startIndex >= len(nums): return for i in range(startIndex, len(nums)): path.append(nums[i]) self.backtracking(nums, i + 1, path, res) path.pop()

90. 子集Ⅱ

去重问题，类似组合总和Ⅱ

class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: res = [] used = [False] * len(nums) nums.sort() self.backtracking(nums, 0, used, [], res) return res def backtracking(self, nums, startIndex, used, path, res): res.append(path[:]) if startIndex >= len(nums): return for i in range(startIndex, len(nums)): if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False: continue path.append(nums[i]) used[i] = True self.backtracking(nums, i + 1, used, path, res) used[i] = False path.pop()

17. 电话号码的字母组合

选下一个数字对应的字母时，用 index + 1

class Solution: def letterCombinations(self, digits: str) -> List[str]: res = [] self.backtracking(digits, 0, [], res) return res def backtracking(self, digits, index, path, res): phone_map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz', } if len(digits) == len(path): res.append(''.join(path)) return possibleLetters = phone_map[digits[index]] for i in possibleLetters: path.append(i) self.backtracking(digits, index + 1, path, res) path.pop()

22. 括号生成

class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] self.backtracking(n, 0, 0, [], res) return res def backtracking(self, n, left, right, path, res): if left == n and right == n: # 将一个列表（或字符序列）拼成一个完整的字符串，然后把这个字符串存入结果列表中 res.append(''.join(path)) return if left < n: path.append('(') self.backtracking(n, left + 1, right, path, res) path.pop() # 防止 )( 出现的关键 if right < left: path.append(')') self.backtracking(n, left, right + 1, path, res) path.pop()

77. 组合

利用递归不断向下探测可能的数字组合，并在返回时通过 pop() 撤销当前选择（回溯），从而系统地穷举出所有符合条件的路径

class Solution: def combine(self, n: int, k: int) -> List[List[int]]: res = [] self.backtracking(n, k, 1, [], res) return res def backtracking(self, n, k, startIndex, path, result): if len(path) == k: result.append(path[:]) return for i in range(startIndex, n + 1): path.append(i) self.backtracking(n, k, i + 1, path, result) path.pop()

39. 组合总和

回溯模板

结果不能重复用 startIndex，可以重复取的话，传入 i，不能重复取，传入 i + 1

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] self.backtracking(candidates, target, 0, 0, [], res) return res def backtracking(self, candidates, target, sum, startIndex, path, res): if sum > target: return if sum == target: res.append(path[:]) return n = len(candidates) # startIndex 的作用是避免组合重复，组合是不在乎顺序的 for i in range(startIndex, n): path.append(candidates[i]) sum += candidates[i] self.backtracking(candidates, target, sum, i, path, res) sum -= candidates[i] path.pop()

40. 组合总和Ⅱ

用 used 数组去重

class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: used = [False] * len(candidates) res = [] # 排序后才能去重 candidates.sort() self.backtracking(candidates, target, 0, 0, used, [],res) return res def backtracking(self, candidates, target, sum, startIndex, used, path, res): if sum > target: return if sum == target: res.append(path[:]) return n = len(candidates) for i in range(startIndex, n): # 去重逻辑 if i > 0 and candidates[i] == candidates[i - 1] and used[i - 1] == False: continue path.append(candidates[i]) sum += candidates[i] used[i] = True self.backtracking(candidates, target, sum, i + 1, used, path, res) path.pop() used[i] = False sum -= candidates[i]

131. 分割回文串

类似于组合问题，startIndex就是切割线，[startIndex，i]就是子串范围

class Solution: def partition(self, s: str) -> List[List[str]]: res = [] self.backtracking(s, 0, [], res) return res def backtracking(self, s, startIndex, path, res): # 切割到了最后一个 if startIndex == len(s): res.append(path[:]) return for i in range(startIndex, len(s)): if self.isPalindrom(s, startIndex, i): path.append(s[startIndex : i + 1]) self.backtracking(s, i + 1, path, res) path.pop() def isPalindrom(self, s, left, right): while left < right: if s[left] != s[right]: return False left += 1 right -= 1 return True

动态规划

Why it work

本质：拆解问题（如何从子问题推导出父问题）+ 记住答案（下次使用）

动态规划的题都可以用暴力递归来解决，而暴力递归缺点是重复计算子问题导致效率低，动态规划的思想就是把计算过的子问题给保存下来，下次需要时可以直接用。另外，当父问题可以由已知的基本子问题推导出来时，就可以不再使用递归，大大提高效率。

解题步骤（从递归到动态规划）：

Recursion（暴力递归）
Memorize（存储计算过的值）
Bottom-Up（自底向上动态规划）

这三步之间是有关系的，所以我们遇到动态规划的题目时，可以先写出暴力递归的解法，然后在此基础上，将其修改为动态规划。

暴力递归改动态规划的模板：

if 的边界条件不变
创建用来存储的 dp 数组，并给出初始值
使用 for 循环自底向上构建 dp 数组：for 循环中，将递归调用变成从 dp 数组中取值，子问题的基本操作不变

注意

for 循环的起始值从 dp 基础值的后一个位开始
dp 数组保存的是暴力递归 return 的东西

动规五部曲

dp 数组以及下标的含义（包含所有状态）
递推公式（跟前面有关系，或是 max 比较两个，本质还是要求出 dp 的下标含义）
dp 数组如何初始化
遍历顺序（ for 循环从哪开始）
打印 dp 数组

509. 斐波那契数

class Solution: def fib(self, n: int) -> int: if n == 0: return 0 dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i -2] return dp[n]

70. 爬楼梯

暴力递归

class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n return self.climbStairs(n - 1) + self.climbStairs(n - 2)

动态规划

假设你现在站在第 3 阶台阶上。根据规则（每次只能爬 1 阶或 2 阶），你在到达第 3 阶的前一秒，只有两种可能的状态：

状态 A：你站在第 2 阶，然后跨了 1 阶上来的
状态 B：你站在第 1 阶，然后跨了 2 阶上来的

所以：到达第 3 阶的总方案数 = 经过第 2 阶上来的方案数 + 经过第 1 阶上来的方案数

class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

杨辉三角形

暴力递归

class Solution: def generate(self, numRows: int) -> List[List[int]]: # 这里的递归是用来：计算杨辉三角的每个值，而不是直接解题 def getValue(row, col): if col == 0 or col == row: return 1 return getValue(row - 1, col - 1) + getValue(row - 1, col) res = [] # 遍历每一行，利用递归求值 for row in range(numRows): current = [] for col in range(row + 1): current.append(getValue(row, col)) res.append(current) return res

动态规划

class Solution: def generate(self, numRows: int) -> List[List[int]]: if numRows == 0: return [] dp = [[0] * (numRows) for _ in range(numRows)] res = [] for row in range(numRows): current = [] for col in range(row + 1): if col == 0 or row == col: dp[row][col] = 1 else: dp[row][col] = dp[row -1][col - 1] + dp[row - 1][col] current.append(dp[row][col]) res.append(current) return res

打家劫舍

暴力递归

class Solution: def rob(self, nums: List[int]) -> int: def helper(index): if index >= len(nums): return 0 rob_current = helper(index + 2) + nums[index] skip_current = helper(index + 1) return max(rob_current, skip_current) if not nums: return 0 return helper(0)

动态规划

class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 dp = [0] * len(nums) dp[0] = nums[0] # 数组长度小于 2 时，不给 dp[1] 赋值 if len(nums) > 1: dp[1] = max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) # 取最后一个 return dp[-1]

完全平方数

暴力递归

class Solution: def numSquares(self, n: int) -> int: def recursion(k : int) -> int: if k == 0: return 0 min_cnt = float('inf') max_i = int(math.isqrt(k)) for i in range(1, max_i + 1): square = i * i cnt = 1 + recursion(k - square) min_cnt = min(cnt, min_cnt) return min_cnt return recursion(n)

动态规划

class Solution: def numSquares(self, n: int) -> int: if n == 0: return 0 dp = [0] + [float('inf')] * n for target in range(1, n + 1): max_i = int(math.isqrt(target)) for i in range(1, max_i + 1): dp[target] = min(dp[target], 1 + dp[target - i * i]) return dp[n]

322. 零钱兑换

完全背包类型问题，一维滚动数组

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [float('inf')] * (amount + 1) dp[0] = 0 # i 物品 for i in coins: # j 背包容量 for j in range(i, amount + 1): dp[j] = min(dp[j], dp[j - i] + 1) return dp[amount] if dp[amount] != float('inf') else -1

300. 最长递增子序列

回溯法

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) res = 0 def backtrack(start, path): nonlocal res res = max(res, len(path)) for i in range(start, n): if not path or nums[i] > path[-1]: path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return res

暴力递归

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: n = len(nums) def recursion(index, previous): if index == n: return 0 not_take = recursion(index + 1, previous) take = 0 if nums[index] > previous: take = 1 + recursion(index + 1, nums[index]) return max(take, not_take) return recursion(0, float('-inf'))

动态规划

需要两个状态所以需要 j

class Solution: # 子序列要求相对原队列相对顺序不变 def lengthOfLIS(self, nums: List[int]) -> int: dp = [1] * len(nums) dp[0] = 1 res = 1 for i in range(1, len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) # 找出每一次的最大值 res = max(dp[i], res) return res

343. 整数拆分

利用动态规划（DP）从小到大递推，通过遍历每一个可能的拆分点 j，在“直接拆成两个数

与“拆出 j 后对剩余部分取最优解

之间取最大值，从而逐步构建出目标数字 n 的最大乘积

class Solution: def integerBreak(self, n: int) -> int: dp = [0] * (n + 1) dp[0] = 0 dp[1] = 0 dp[2] = 1 for i in range(3, n + 1): for j in range(1, i // 2 + 1): dp[i] = max(j * (i - j), j * dp[i - j], dp[i]) return dp[n]

96. 不同的二叉搜索树

遍历每一个可能的节点作为根节点，将总方案数拆解为左子树形态数与右子树形态数的笛卡尔积（乘积）之和

class Solution: def numTrees(self, n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): for j in range(1, n + 1): dp[i] += dp[j - 1] * dp[i - j] return dp[n]

01背包

二维数组

通过决策“是否放入当前物品”，利用已经计算出的前 i-1 个物品在不同容量下的局部最优解，逐步递推出当前背包容量所能装载的最大价值

dp数组含义：在0到 i 任取物品，容量为 j 的背包的最大价值

n , bagweight = map(int, input().split()) weight = list(map(int, input().split())) value = list(map(int, input().split())) # i 为种类，j 为容量 dp = [[0] * (bagweight + 1) for _ in range(n)] for j in range(weight[0], bagweight + 1): dp[0][j] = value[0] for i in range(1, n): for j in range(1, bagweight + 1): if j < weight[i]: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) print(dp[n - 1][bagweight])

一维滚动数组

因为二维数组的 i 行只和 i - 1 行有关，所以可以简化为一维。利用滚动，即每一次 for j 的循环就是二维数组的一行，所引用的

仍是上一轮物品留下的“旧值”

倒序保证物品只被加了一次

n , bagweight = map(int, input().split()) weight = list(map(int, input().split())) value = list(map(int, input().split())) dp = [0] * (bagweight + 1) dp[0] = 0 # 倒序 for i in range(n): for j in range(bagweight, weight[i] - 1, -1): dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) print(dp[bagweight])

完全背包

递推公式：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])，和 01 背包的递推公式不同

这里的二维类似于 01 背包的一维滚动数组

198. 打家劫舍

在遍历每间房时权衡“抢（当前金额 + 前前家累计）”与“不抢（直接沿用前一家累计）”来获取最大化收益

class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0] dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]) return dp[-1]

121. 买卖股票的最佳时机

持有股票和不持有股票的两种状态，持有股票时又包括没有操作股票和当天买入股票两种状态，不持有股票同理（建模）

class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) dp = [[0] * 2 for _ in range(n)] dp[0][0] = -prices[0] dp[0][1] = 0 for i in range(1, n): # 持有股票 dp[i][0] = max(dp[i - 1][0], -prices[i]) # 不持有股票 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]) return max(dp[-1][0], dp[-1][1])

排序算法

归并排序

分而治之

分：大问题变小问题，使用递归
治：合并

class Solution: # 分 def mergeSort(self, nums): if len(nums) <= 1: return nums mid = len(nums) // 2 # 切片操作 left = nums[: mid] right = nums[mid : ] left = self.mergeSort(left) right = self.mergeSort(right) return self.merge(left, right) # 治 def merge(self, left, right): merge = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: merge.append(left[i]) i += 1 else: merge.append(right[j]) j += 1 while i < len(left): merge.append(left[i]) i += 1 while j < len(right): merge.append(right[j]) j += 1 return merge

快速排序

原理：选择一个基准值（pivot），将数组分为两部分：小于基准值的元素和大于基准值的元素，然后递归地对这两部分进行排序。

每次都只找到一个元素（基准值）的正确位置，利用递归找到所有元素的正确位置

时间复杂度：O(n log n)

def quicksort(arr, low, high): if low < high: pivot_index = partition(arr, low, high) quicksort(arr, low, pivot_index - 1) quicksort(arr, pivot_index + 1, high) def partition(arr, low, high): # 随机选择基准值，交换到数组末尾 pivot_index = random.randint(low, high) arr[high], arr[pivot_index] = arr[pivot_index], arr[high] pivot = arr[high] i = low - 1 # 左指针 for j in range(low, high): # 右指针 if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1

技巧

只出现一次的数字

class Solution: # 使用异或（相同为 0，不同为 1，可以看作不进位加法 ） # 任何数和 0 做异或，等于自己 # 自己和自己异或，等于 0 def singleNumber(self, nums: List[int]) -> int: result = 0 for i in nums: result ^= i return result

多数元素

class Solution: # 投票算法，最终留下的会是多数元素 def majorityElement(self, nums: List[int]) -> int: count = 0 candidate = 0 for num in nums: if count == 0: candidate = num if num == candidate: count += 1 else: count -= 1 return candidate

颜色分类

class Solution: # 荷兰国旗（三指针）,index 用来遍历，排序之后：low 之前都是 0，high 之后都是 1 def sortColors(self, nums: List[int]) -> None: low, index, high = 0, 0, len(nums) - 1 while index <= high: if nums[index] == 0: nums[low], nums[index] = nums[index], nums[low] low += 1 index += 1 elif nums[index] == 1: index += 1 elif nums[index] == 2: nums[high], nums[index] = nums[index], nums[high] high -= 1

下一个排列

class Solution: # “字典序”在这里就是把整个数组当成一个多位数，从左往右逐位比较大小 # 题意：找到“刚好大一点”的排列，找不到就回到最小排列，且原地修改，不能额外开数组。 def nextPermutation(self, nums: List[int]) -> None: n = len(nums) if n < 2: return # 从右往左找第一个下降到的位置 i（因为要刚好大一点），顺序的起始位置 i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: # 从右往左找第一个大于 nums[i] 的位置 j j = n - 1 while j >= 0 and nums[j] <= nums[i]: j -= 1 # 与大于i的j，交换位置 nums[i], nums[j] = nums[j], nums[i] # 翻转 i + 1 到末尾，使 i 之后的变成升序（最小字典） # 其中还包含了如果不存在 i（值为 -1 ），就全部翻转 # 利用双指针 left, right = i + 1, n - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1

寻找重复数

class Solution: # 快慢指针（Floyd 判圈算法） # 先每次走两步，相遇后，一个指针置放回起点，然后每次走一步，相遇的地方就是环的入口 # 使用条件：每个节点出度为 1 def findDuplicate(self, nums: List[int]) -> int: slow = nums[0] fast = nums[nums[0]] while slow != fast: slow = nums[slow] fast = nums[nums[fast]] fast = 0 while slow != fast: slow = nums[slow] fast = nums[fast] return slow

初学者刷题遇到的问题

原因一：LeetCode 题是循序渐进的，某些知识点可能会依赖另一个的知识点。如果前置知识不足，那么解题时肯定会晕头转向，依赖关系如下

原因二：做题囫囵吞枣（ 仅仅只是抄答案，甚至是复制粘贴 ），不思考，不总结。

原因三：选用的编程语言的语法繁琐。

原因四：没有复习做过的题

哈希表

Why it work?

1. 两数之和

字母异位词分组

最长连续序列

242. 有效的字母异位词

349. 两个数组的交集

字符串

344. 反转字符串

151. 翻转字符串里的单词

双指针

Why it work

移动零

盛水最多的容器

15. 三数之和（三元组不重复）

二分查找

Why it work?

搜索插入的位置

搜索二维矩阵

第一个和最后一个位置

搜索旋转排序数组

寻找排序数组中最小值

滑动窗口

Why it work

无重复字符的最长子串

找字符串中所有异位词

链表

Why it work

160. 相交链表

206. 反转链表

回文链表

141. 环形链表

21. 合并两个有序链表

两数之和

19. 删除链表的倒数第N个节点

24. 两两交换链表中的节点

排序链表

203. 移除链表元素

707. 设计链表

数组

Why it work

最大子数组和

合并区间

轮转数组

除自身以外数组的乘积

27. 移除元素

977. 有序数组的平方和

209. 长度最小的子数组

59. 螺旋矩阵Ⅱ

代码随想录：区间和

栈

Why it work?

20. 有效的括号

最小栈

字符串解码

每日温度

232. 用栈实现队列

225. 用队列实现栈

1047. 删除字符中的所有相邻重复项

二叉树

Why it work?

104. 二叉树的最大深度

111. 二叉树的最小深度

226. 翻转二叉树

101. 对称二叉树

110. 平衡二叉树

222. 完全二叉树的节点个数

二叉树的直径

102. 二叉树的层序遍历

108. 有序数组转二叉搜索树

98. 验证二叉搜索树

二叉搜索树中第 k 小元素

199. 二叉树的右视图

二叉树展开为链表

144. 94 145 二叉树的前中后序遍历

原因二：做题囫囵吞枣（仅仅只是抄答案，甚至是复制粘贴），不思考，不总结。