哈希表 两数之和 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target两个 整数，并返回它们的数组下标
示例 1：
1 2 3 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
1 2 输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
1 2 输入：nums = [3,3], target = 6 输出：[0,1]
暴力解法
遍历，时间复杂度为$O(N^2)$，空间复杂度为$O(1)$
1 2 3 4 5 6 7 8 9 class Solution : def twoSum (self, nums: List [int ], target: int ) -> List [int ]: n = len (nums) for i in range (n): for j in range (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 class Solution : def twoSum (self, nums: List [int ], target: int ) -> List [int ]: hashtable = dict () for i, num in enumerate (nums): if target - num in hashtable: return [hashtable[target - num], i] hashtable[nums[i]] = i return []
python 的 dict 和 C++ 的 unordered_map 基本一致
涉及到in判断就不能用defaultdict
字母异位词分组 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1 :
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 "bat"
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此
示例 2 :
输入: strs = [“”]
输出: [[“”]]
示例 3 :
输入: strs = [“a”]
输出: [[“a”]]
可以重构的字符串在排序后结果相同，可以以此作为哈希表的键，原字符串作为值，最后输出哈希表值的元组
哈希表排序
1 2 3 4 5 6 7 8 9 10 class Solution : def groupAnagrams (self, strs: List [str ] ) -> List [List [str ]]: mp = defaultdict(list ) for st in strs: key = "" .join(sorted (st)) mp[key].append(st) return list (mp.values())
这里用的不是sort而是sorted，因为st是字符串，而且不能对原对象产生修改
sorted不对原对象修改，可用于字符串、列表、任何可迭代对象，生成list，所以需要"".join转为str
时间复杂度为O(nklogk)，k为strs中字符串的最大长度，空间复杂度为nk
最长连续序列 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
请你设计并实现时间复杂度为 O(n) 的算法解决此问题
示例 1：
1 2 3 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
1 2 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
示例 3：
1 2 输入：nums = [1,0,1,2] 输出：3
既然要时间复杂度为O(n)那必然不能暴力枚举了
如果对每个数都向左、向右扩展，那最坏会退化成O(n²)
破解方法：只有当一个数是“连续序列起点”时，才从它开始向右数
不需要重复数字，直接用set快速剔除，保留不同数字
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution : def longestConsecutive (self, nums: List [int ] ) -> int : nums_set = set (nums) maxlen = 0 for num in nums_set: if (num - 1 ) not in 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:
不复制数组只能是直接交换，末尾都是0，头部都是非0值
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部[快慢指针]
右指针走的更快，以其为循环结束标志
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def moveZeroes (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]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量
示例 1：
1 2 3 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
发现盛水量等于(right-left)*min(height[left],height[right])
直接用双指针走就行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution : def maxArea (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 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组
示例 1：
1 2 3 4 5 6 7 8 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
1 2 3 输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
1 2 3 输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
排序 + 双指针
首先注意到不能有重复输出(不同排列方式)，所以最好的去重就是先排序，后续只需要移动指针判断是否值相等跳过自动就实现去重
固定一个，从左往右走，注意，固定的这个数必须小于0才有可能实现3数和为0，同时需要判断是否重复
剩下两个使用左右指针，和小于0加左边，和大于0加右边，如果和为0输出，这个时候左右指针同时向中心移动，注意，移动时候需要判断是否值重复，不然会有重复输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution : def threeSum (self, nums: List [int ] ) -> List [List [int ]]: nums.sort() ans = list () n = len (nums) for c in range (n - 2 ): if c > 0 and nums[c] == nums[c - 1 ]: continue if nums[c] > 0 : break l, r = c + 1 , n - 1 while l < r: sum = nums[c] + nums[l] + nums[r] if sum == 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 elif sum < 0 : l += 1 else : r -= 1 return ans
接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
1 2 3 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
1 2 输入：height = [4,2,0,3,2,5] 输出：9
首先要知道雨水怎么接的，看图可以发现是凹处能接到水，转为代码语言就是高度小于左侧右侧最大值其中较小值的地方
动态规划
具体来说，对于下标i，能接的雨水量等于下标i处的水能到达的最大高度减去heigh[i]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def trap (self, height: List [int ] ) -> int : n = len (height) leftmax = list () rightmax = list () max_l, max_r = 0 , 0 for i in range (n): max_l = max (max_l, height[i]) max_r = max (max_r, height[n - 1 - i]) leftmax.append(max_l) rightmax.append(max_r) rightmax = rightmax[::-1 ] water = 0 for i in range (n): water += min (leftmax[i], rightmax[i]) - height[i] return water
时间复杂度和空间复杂度都是O(n)
能否降低空间复杂度呢？
回到凹处的定义，是高度小于左侧右侧最大值其中较小值的地方
那如果先找到一个最大值，以其为分界，那么左右两块都只要看当前的最大值就能得知左右侧最大值的较小值，这样就不需要建立数组，使得空间复杂度降低为O(1)，因为不需要创建数组去记录了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution : def trap (self, height: List [int ] ) -> int : max_loc = -1 max_height = 0 for i in range (len (height)): if height[i] > max_height: max_loc = i max_height = height[i] if max_loc == -1 : return 0 water = 0 max_cur = 0 for i in range (max_loc): if height[i] > max_cur: max_cur = height[i] water += max_cur - height[i] max_cur = 0 for i in range (len (height) - 1 , max_loc, -1 ): if height[i] > max_cur: max_cur = height[i] water += max_cur - height[i] return water
但是在面试中一般考察的是双指针的用法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution : def trap (self, height: List [int ] ) -> int : left, right = 0 , len (height)-1 water = 0 leftmax, rightmax = 0 , 0 while left < right: leftmax = max (leftmax, height[left]) rightmax = max (rightmax, height[right]) if height[left] < height[right]: water += leftmax - height[left] left += 1 else : water += rightmax - height[right] right -= 1 return water
滑动窗口 无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度
示例 1:
1 2 3 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
示例 2:
1 2 3 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
1 2 3 4 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成
既然出现了不重复，肯定第一下要想到set，但是还需要记录长度，所以又要用到左右指针了，左指针记录无重复字符串的开端，右指针记录无重复字符串的尾端，长度为right-left+1
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def lengthOfLongestSubstring (self, s: str ) -> int : seen = set () left = 0 max_len = 0 for right in range (len (s)): while s[right] in seen: seen.remove(s[left]) left += 1 seen.add(s[right]) max_len = max (max_len, right - left + 1 ) return max_len
找到字符串中所有字母异位词 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
1 2 3 4 5 输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
1 2 3 4 5 6 输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104s 和 p 仅包含小写字母
方法一：滑动窗口
异位词其实就是组成的字母相同，如果枚举匹配那么复杂度直接爆炸，构建一个和p相同长度的滑动窗口，统计数量就行(注意，这是因为这里只有小写字母) ，如果有字符或者空格就比较麻烦了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution : def findAnagrams (self, s: str , p: str ) -> List [int ]: s_len, p_len = len (s), len (p) if s_len < p_len: return [] ans = [] s_count = [0 ] * 26 p_count = [0 ] * 26 for i in range (p_len): p_count[ord (p[i]) - ord ("a" )] += 1 s_count[ord (s[i]) - ord ("a" )] += 1 if p_count == s_count: ans.append(0 ) for i in range (s_len - p_len): s_count[ord (s[i]) - ord ("a" )] -= 1 s_count[ord (s[i + p_len]) - ord ("a" )] += 1 if s_count == p_count: ans.append(i + 1 ) return ans
方法二：优化的滑动窗口
在方法一的基础上，不再分别统计滑动窗口和字符串 p 中每种字母的数量，而是统计滑动窗口和字符串 p 中每种字母数量的差
引入变量 differ 来记录当前窗口与字符串 p 中数量不同的字母的个数，并在滑动窗口的过程中维护它
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution : def findAnagrams (self, s: str , p: str ) -> List [int ]: s_len, p_len = len (s), len (p) if s_len < p_len: return [] ans = [] count = [0 ] * 26 for i in range (p_len): count[ord (s[i]) - ord ("a" )] += 1 count[ord (p[i]) - ord ("a" )] -= 1 differ = [c != 0 for c in count].count(True ) if differ == 0 : ans.append(0 ) for i in range (s_len - p_len): if count[ord (s[i]) - ord ("a" )] == 1 : differ -= 1 elif count[ord (s[i]) - ord ("a" )] == 0 : differ += 1 count[ord (s[i]) - ord ("a" )] -= 1 if count[ord (s[i + p_len]) - ord ("a" )] == -1 : differ -= 1 elif count[ord (s[i + p_len]) - ord ("a" )] == 0 : differ += 1 count[ord (s[i + p_len]) - ord ("a" )] += 1 if differ == 0 : ans.append(i + 1 ) return ans
子串 和为 K 的子数组 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数
子数组是数组中元素的连续非空序列。
示例 1：
1 2 输入：nums = [1,1,1], k = 2 输出：2
示例 2：
1 2 输入：nums = [1,2,3], k = 3 输出：2
前缀和 + 哈希表优化
子串肯定不能直接去获取然后计算，这个时候需要一点数学技巧
比如需要从下标i到j的子串，那么是不是可以等价于从0到j的子串减去从0到i的子串，这样只要遍历一次就能获得所有的子串
prefix2 - prefix1 = k 转变为 查找已经存进哈希表的值里有没有等于 prefix2 - k 的
注意，要在哈希表里默认加一个0，这样才能准确认到自身单元素的情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution : def subarraySum (self, nums: List [int ], k: int ) -> int : ans = 0 prefix_sum = 0 mp = {0 : 1 } for x in nums: prefix_sum += x 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 class Solution : def subarraySum (self, nums: List [int ], k: int ) -> int : ans = 0 for start in range (len (nums)): sum = 0 for end in range (start, -1 , -1 ): sum += nums[end] if sum == k: ans += 1 return ans
滑动窗口最大值 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值
示例 1：
1 2 3 4 5 6 7 8 9 10 11 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2：
1 2 输入：nums = [1], k = 1 输出：[1]
对于每个滑动窗口可以使用O(k)时间遍历其中的每一个元素，找出其中的最大值
对于长度为n的数组而言，窗口的数量为n*−*k+1，因此该算法的时间复杂度为O((n-l+1)k)=O(nk)，k大的情况下复杂度太大，不能用普通的左右指针
优先队列
对于最大值的存储，可以想到优先队列
优先队列里存储一组pair，第一个数是确切值，第二个数是索引值
在判断最大值时只需要让最大值的索引在滑动窗口的范围内，就是窗口的最大值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution {public : vector<int > maxSlidingWindow (vector<int >& nums, int k) { int n = nums.size (); priority_queue<pair<int , int >> q; for (int i = 0 ; i < k; i++) { q.emplace (nums[i], i); } vector<int > ans = {q.top ().first}; for (int i = k; i < n; i++) { q.emplace (nums[i], i); while (q.top ().second <= i - k) { q.pop (); } ans.push_back (q.top ().first); } return ans; } };
相比暴力解法，时间复杂度为O(nlogn)，每次放入和移出优先队列的复杂度为O(logn)，n个元素
空间复杂度为O(n)，只有一个存储的优先队列
在python中
结构
C++
Python
堆
priority_queueheapq
队列
dequedeque
哈希
unordered_mapdict
并且不太一样的是，c++中是最大值优先队列，在py中是最小堆
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution : 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 heapq.heappop(q) ans.append(-q[0 ][0 ]) return ans
单调队列
当然，用优先队列会有一些额外开支
一是其实没必要一直去排序整个队列，换个思路来说，只需要在进入序列时排序，节省额外的排序开支
二是没必要保存值，只需要保存最大值的索引，判断是否在滑动窗口内就行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {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 class Solution : def maxSlidingWindow (self, nums: List [int ], k: int ) -> List [int ]: n = len (nums) dq = deque() for i in range (k): while dq and nums[i] >= nums[dq[-1 ]]: dq.pop() dq.append(i) ans = [nums[dq[0 ]]] for i in range (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 的子串中， 因此没有符合条件的子字符串，返回空字符串。
这个题的第一思路肯定就是滑动窗口，窗口内需要关注
t的需求表 need
当前窗口的计数表 window
哪些字符已经满足 valid
右指针不断向右扩大窗口，更新窗口计数，直到窗口满足条件，记录当前窗口长度，与最小窗口长度进行比较，更新最小值
满足条件后，左指针向右移动，直到缩掉某个字符后不再满足窗口条件，然后重新开始右扩，直到走到尽头
每个字符最多进窗口一次、出窗口一次，复杂度为O(m+n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution : def minWindow (self, s: str , t: str ) -> str : need = defaultdict(int ) for c in t: need[c] += 1 window = defaultdict(int ) valid = 0 need_size = len (need) left, right = 0 , 0 start = 0 min_len = float ("inf" ) while right < len (s): c = s[right] right += 1 if c in need: window[c] += 1 if window[c] == need[c]: valid += 1 while valid == need_size: if right - left < min_len: start = left min_len = right - left d = s[left] left += 1 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1 return "" if min_len == float ("inf" ) else s[start : start + min_len]
普通数组 最大子数组和 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
子数组 是数组中的一个连续部分
示例 1：
1 2 3 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大为 6
示例 2：
示例 3：
1 2 输入：nums = [5,4,-1,7,8] 输出：23
**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解
动态规划
第一思路应该会想到和和为 K 的子数组 这道题一样的前缀和，但是更简单，只需要判断是从当前位置重新开始还是继续延伸
用 $f(i)$ 表示以第 $i$ 个数结尾的连续子数组的最大和，在计算时考虑 $nums[i]$ 单独成为一段，还是加入 $f(i-1)$ 对应的那一段
1 2 3 4 5 6 7 8 class Solution : def maxSubArray (self, nums: List [int ] ) -> int : prefix_sum = 0 maxAns = nums[0 ] for num in nums: prefix_sum = max (prefix_sum + num, num) maxAns = max (maxAns, prefix_sum) return maxAns
合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
示例 1：
1 2 3 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
1 2 3 输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：
1 2 输入：intervals = [[4,7],[1,4]] 输出：[[1,7]]
排序
合并区间首先排序区间，这样方便边界判定，合并以后只需要看前一个的Right和后一个Left是否有重叠，没重叠就开新区间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution : def merge (self, intervals: List [List [int ]] ) -> List [List [int ]]: intervals.sort(key = lambda x : x[0 ]) left, right = intervals[0 ] ans = [] for i in range (1 , len (intervals)): cur_l, cur_r = intervals[i] if cur_l <= right: right = max (right, cur_r) else : ans.append([left, right]) left, right = cur_l, cur_r ans.append([left, right]) return ans
轮转数组 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
示例 1:
1 2 3 4 5 6 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
1 2 3 4 5 输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
首先，要考虑k大于数组长度，会出现一些循环，所以需要计算最终实际的轮转数k%len(nums)
移动起始会发现就是把后k个元素放到前面
数组翻转
1 2 3 4 5 6 7 8 class Solution : def rotate (self, nums: List [int ], k: int ) -> None : n = len (nums) k %= n nums.reverse() nums[:k] = nums[:k][::-1 ] nums[k:] = nums[k:][::-1 ]
这种方法每个元素都被翻转两次，时间复杂度为O(n)，空间复杂度为O(1)
切片拼接
相当于使用额外的数组
将原数组下标为i的元素放至新数组下标为 (i+k)mod n 的位置，最后将新数组拷贝至原数组即可
1 2 3 4 5 6 7 class Solution : def rotate (self, nums: List [int ], k: int ) -> None : """ Do not return anything, modify nums in-place instead. """ k %= len (nums) nums[:] = nums[-k:] + nums[:-k]
这种方法就是有额外开支，空间复杂度为O(n)
除了自身以外数组的乘积 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题
示例 1:
1 2 输入: nums = [1,2,3,4] 输出: [24,12,8,6]
示例 2:
1 2 输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组 不被视为 额外空间）
最直觉的想法一定是总乘积 / nums[i]，但是这里限制了除法
左右乘积列表
answer[i] 的定义是左边所有数 × 右边所有数，那这样来看似乎可以维护两个数组，分别代表左边和右边所有数的乘积
无论是左还是右，最边界的那个值都应该是1，因为没有其它数了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def productExceptSelf (self, nums: List [int ] ) -> List [int ]: n = len (nums) L = [1 ] * n for i in range (1 , n): L[i] = nums[i - 1 ] * L[i - 1 ] R = [1 ] * n for i in range (n - 2 , -1 , -1 ): R[i] = nums[i + 1 ] * R[i + 1 ] ans = [0 ] * n for i in range (n): ans[i] = L[i] * R[i] return ans
这种做法满足了时间复杂度为O(n)，但是由于构建了数组，空间复杂度也为O(n)
怎么才能让空间复杂度降为O(1)呢
就不构建两个数组，直接把乘操作放到一个数组的两步，因为每个位置都是L[i]*R[i]，把R[i]转化为L[i]再乘即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution : def productExceptSelf (self, nums: List [int ] ) -> List [int ]: n = len (nums) ans = [1 ] * n for i in range (1 , n): ans[i] = ans[i - 1 ] * nums[i - 1 ] R = 1 for i in range (n - 1 , -1 , -1 ): ans[i] *= R R *= nums[i] return ans
缺失的第一个正数 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案
示例 1：
1 2 3 输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
1 2 3 输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
1 2 3 输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
因为限制了内存，没法直接用哈希表，如果不限制内存：
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def firstMissingPositive (self, nums: List [int ] ) -> int : mp = {} for x in nums: if x > 0 : mp[x] = True n = len (nums) for i in range (1 , n + 2 ): if i not in mp: return i
置换法
最关键的点： 如果数组长度是 n，在恢复后，数组应当有 [1, 2, ..., N] 的形式
找第一个不符合的位置，如果都符合就是都存在，返回n+1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def firstMissingPositive (self, nums: List [int ] ) -> int : n = len (nums) for i in range (n): while 1 <= nums[i] <= n and nums[nums[i] - 1 ] != nums[i]: correct_dix = nums[i] - 1 nums[i], nums[correct_dix] = nums[correct_dix], nums[i] for i in range (n): if nums[i] != i + 1 : return i + 1 return n + 1
不开另外的内存，把索引也作为一个信号
矩阵 矩阵置零 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 **0 **，请使用原地算法
示例 1：
1 2 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
1 2 输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
使用标记数组
最直观的做法，遍历矩阵，用标记数组记录是否有0出现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def setZeroes (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 in range (m): for j in range (n): if matrix[i][j] == 0 : row[i] = col[j] = True for i in range (m): for j in range (n): if row[i] or col[j]: matrix[i][j] = 0
这种方法：时间复杂度：O(m * n)，空间复杂度：O(m + n)
更近一步就是将空间复杂度降低至O(1)
使用两个标记变量
可以把矩阵的第一行和第一列的位置用来作为标记，因为如果一行或者一列上有0，那么这些位置本身也要置0
但这样的话无法记录它们本身是否为0，所以需要引入两个标记变量来分别记录第一行和第一列是否原本包含0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution : def setZeroes (self, matrix: List [List [int ]] ) -> None : """ Do not return anything, modify matrix in-place instead. """ m, n = len (matrix), len (matrix[0 ]) flag_col0 = any (matrix[i][0 ] == 0 for i in range (m)) flag_row0 = any (matrix[0 ][j] == 0 for j in range (n)) for i in range (1 , m): for j in range (1 , n): if matrix[i][j] == 0 : matrix[i][0 ] = 0 matrix[0 ][j] = 0 for i in range (1 , m): for j in range (1 , n): if matrix[i][0 ] == 0 or matrix[0 ][j] == 0 : matrix[i][j] = 0 if flag_col0: for i in range (m): matrix[i][0 ] = 0 if flag_row0: for j in range (n): matrix[0 ][j] = 0
时间复杂度：O(m * n)，循环遍历矩阵两次
空间复杂度：O(1)
压缩到1个标记变量实在是可读性太差了，放弃
螺旋矩阵 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素
示例 1：
1 2 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
示例 2：
1 2 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
把向右移和向下移看作一组，把向左移和向上移看作一组，每一组必须在除去扫过的部分还有矩阵才能继续
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution : def spiralOrder (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 in range (left, right + 1 ): ans.append(matrix[top][j]) top += 1 for i in range (top, bottom + 1 ): ans.append(matrix[i][right]) right -= 1 if top > bottom or left > right: break for j in range (right, left - 1 , -1 ): ans.append(matrix[bottom][j]) bottom -= 1 for i in range (bottom, top - 1 , -1 ): ans.append(matrix[i][left]) left += 1 return ans
时间复杂度为O(mn)，空间复杂度为O(1)
旋转图像 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度
必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像
示例 1：
1 2 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
1 2 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
经过书写可得交换下标的结论
[i][j]->[j][n-i-1]->[n-i-1][n-j-1]->[n-j-1][i]->[i][j]
原地旋转
可以知道只需要旋转n//2行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution : def rotate (self, matrix: List [List [int ]] ) -> None : """ Do not return anything, modify matrix in-place instead. """ n = len (matrix) for i in range (0 , n // 2 ): for j in range (i, n - i - 1 ): ( matrix[i][j], matrix[j][n - i - 1 ], matrix[n - i - 1 ][n - j - 1 ], matrix[n - j - 1 ][i], ) = ( matrix[n - j - 1 ][i], matrix[i][j], matrix[j][n - i - 1 ], matrix[n - i - 1 ][n - j - 1 ], )
用翻转代替旋转
因为直接用旋转需要思考，还不够直观，如果直接用多次翻转来等效旋转会更简单
顺时针旋转90°相当于(i, j) → (j, n - 1 - i)
怎么这样变呢，水平翻转等价于(i, j) → (n - 1 - i, j)，主对角线翻转等价于(i, j) → (j, i)
那么旋转90°等价于水平翻转+主对角线翻转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution : def rotate (self, matrix: List [List [int ]] ) -> None : """ Do not return anything, modify matrix in-place instead. """ n = len (matrix) for i in range (0 , n // 2 ): for j in range (n): matrix[i][j], matrix[n - i - 1 ][j] = matrix[n - i - 1 ][j], matrix[i][j] for i in range (n): for j in range (i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
拓展：
如果要逆时针旋转90°呢？
旋转 90° 的标准坐标变换是(i, j) → (n - 1 - j, i)
那么相当于左右翻转后再主对角线翻转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution : 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 (0 , n // 2 ): matrix[i][j], matrix[i][n - j - 1 ] = matrix[i][n - j - 1 ], matrix[i][j] for i in range (n): for j in range (i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
搜索二维矩阵 II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
1 2 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true
示例 2：
1 2 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 输出：false
Z 字形查找
利用单调性不断裁剪搜索空间，以右上角开始，如果值大了往左边移动，值小了向下移动，直到越界
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution : def searchMatrix (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 : return True return False
时间复杂度O(m+n)，空间复杂度O(1)
这个方法应该是最优的，但是了解一下二分解法
二分查找
因为行之间也不是完全有序的，所以无法直接flatten再二分，于是需要每行做二分来查找
1 2 3 4 5 6 7 8 class Solution : 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
bisect_left 的含义：在有序数组 row 中，找到 target 应该插入的位置（最左边），并且插入后仍然保持有序。
1 2 3 4 5 6 row = [1, 3, 5, 7] bisect_left(row, 5) # 2 bisect_left(row, 6) # 3 bisect_left(row, 0) # 0 bisect_left(row, 8) # 4
所以还需要满足row[idx] == target
因为用到了二分查找，所以时间复杂度：O(mlog n)，空间复杂度仍然为O(1)
相比暴力解法肯定是更快
标准二分工具bisect：
.bisect_left：找左边界
.bisect_right：找右边界
两者一减：数数量
手搓二分查找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def binary_search (nums, target ): 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 -1
手搓二分找第一个 ≥ target 的位置
1 2 3 4 5 6 7 8 9 10 def lower_bound (nums, target ): left, right = 0 , len (nums) while left<right: mid = (left+right)//2 if nums[mid] < target: left = mid+1 else : right = mid return left
这里right不用``len(nums)-1是因为返回的是左边界，需要考虑nums`中右边界索引
链表 相交链表 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
图示两个链表在节点 c1 开始相交**：**
题目数据 保证 整个链式结构中不存在环
注意 ，函数返回结果后，链表必须 保持其原始结构
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案
示例 1：
1 2 3 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）
示例 2：
1 2 3 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：No intersection 这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值
双指针
用两个指针分别从A，B的头开始遍历，指向None时指向另一个的头
假设两个链表有相交，那么走了A再走B会到达同一位置，也就是交界点；如果没有相交，就同时指向None，也会相等从而跳出循环
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def getIntersectionNode ( self, headA: ListNode, headB: ListNode ) -> Optional [ListNode]: pA, pB = headA, headB while pA is not pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA
时间复杂度为O(m+n)，空间复杂度为O(1)
对齐长度
如果已经知道两者的长度，那么就很容易找相交点了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution : def getIntersectionNode ( self, headA: ListNode, headB: ListNode ) -> Optional [ListNode]: def get_len (head ): cnt = 0 while head: cnt += 1 head = head.next return cnt lenA = get_len(headA) lenB = get_len(headB) pA, pB = headA, headB if lenA > lenB: for _ in range (lenA - lenB): pA = pA.next else : for _ in range (lenB - lenA): pB = pB.next while pA is not pB: pA = pA.next pB = pB.next return pA
这种做法的时间复杂度也是O(m+n)，空间复杂度O(1)
更直观，但是我感觉没有双指针好用
反转链表 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
示例 1：
1 2 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
迭代三指针法
核心思路：先存next再断开连接
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution : def reverseList (self, head: Optional [ListNode] ) -> Optional [ListNode]: prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev
递归法
比较抽象，核心思路：直接从后往前改
直接让当前节点的next指向none
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def reverseList (self, head: Optional [ListNode] ) -> Optional [ListNode]: if not head or not head.next : return head new_head = self .reverseList(head.next ) head.next .next = head head.next = None return new_head
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 原始链表：1 → 2 → 3 → None reverse(1) | v reverse(2) | v reverse(3) 返回 3 在reverse(2)这一层 2 → 3 → None 3 → 2 ↑ ↓ └───┘ head.next = None -> 3 → 2 → None 回 reverse(1) 这一层 1 → 2 → None 3 → 2 → 1 ↑ ↓ └───┘ head.next = None -> 3 → 2 → 1 → None
回文链表 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
示例 1：
1 2 输入：head = [1,2,2,1] 输出：true
示例 2
1 2 输入：head = [1,2] 输出：false
**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
将值复制到数组中后用双指针法
把链表里的值全部取出来，当成一个数组，判断这个数组是不是回文
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution : def isPalindrome (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]: return False left += 1 right -= 1 return True
这种做法就是时间复杂度和空间复杂度都为O(n)
如果要降到O(1)的空间复杂度只能在原链表上操作，如何找到一半的位置是重点
这里用到快慢指针
快指针走多一步
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution : def isPalindrome (self, head: Optional [ListNode] ) -> bool : if not head or not head.next : return True slow = fast = head while fast and fast.next : slow = slow.next fast = fast.next .next prev = None cur = slow while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt p1, p2 = head, prev while p2: if p1.val != p2.val: return False p1 = p1.next p2 = p2.next return True
如果要恢复链表就要多做一次反转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution : def isPalindrome (self, head: Optional [ListNode] ) -> bool : if not head or not head.next : return True slow = fast = head while fast and fast.next : slow = slow.next fast = fast.next .next second = self .reverse(slow) p1, p2 = head, second result = True while p2: if p1.val != p2.val: result = False break p1 = p1.next p2 = p2.next self .reverse(second) return result def reverse (self, head ): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev
环形链表 给你一个链表的头节点 head ，判断链表中是否有环
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况
如果链表中存在环 ，则返回 true 。 否则，返回 false
示例 1：
1 2 3 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点
示例 2：
1 2 3 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点
示例 3：
1 2 3 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
方法一：哈希表
最简单的思路，遍历head，用一个哈希表记录，出现相同的head则代表出现环形
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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
这种方法时间复杂度为O(n)，空间复杂度也为O(n)
方法二：快慢指针
如果有环形，两个指针虽然步数不一样，那么在多步以后应该指向同一位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def hasCycle (self, head: Optional [ListNode] ) -> bool : slow = head fast = head while fast and fast.next : slow = slow.next fast = fast.next .next if slow == fast: return True return False
时间复杂度仍为O(n)，空间复杂度为O(1)
环形链表 II 给定一个链表的头节点head，返回链表开始入环的第一个节点，如果链表无环，则返回 null
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始 ）
如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递 ，仅仅是为了标识链表的实际情况
不允许修改 链表
示例 1：
1 2 3 输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
1 2 3 输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
1 2 3 输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环
**进阶：**你是否可以使用 O(1) 空间解决此题？
方法一：哈希表
同样的做法，遍历记录head，找到第一个重复的位置即为入口
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution : def detectCycle (self, head: Optional [ListNode] ) -> Optional [ListNode]: seen = set () while head: if head in seen: return head seen.add(head) head = head.next return None
这种方法时间复杂度为O(n)，空间复杂度也为O(n)
方法二：快慢指针
a = 头到入口距离
b = 入口到相遇点距离
c = 环长
相遇时：慢指针走了 a + b，快指针走了 a + b + k·c
因为 fast 速度是 slow 的 2 倍：2(a + b) = a + b + k·c
整理得到：
而 c − b 正好是从相遇点回到入口的距离
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution : def detectCycle (self, head: Optional [ListNode] ) -> Optional [ListNode]: if not head or not head.next : return None slow = head fast = head while fast and fast.next : slow = slow.next fast = fast.next .next if slow == fast: break else : return None slow = head while slow != fast: slow = slow.next fast = fast.next return slow
这种做法时间复杂度O(n)，空间复杂度只有O(1)，只用到快慢指针
合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
1 2 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
1 2 输入：l1 = [], l2 = [] 输出：[]
示例 3：
1 2 输入：l1 = [], l2 = [0] 输出：[0]
方法一：迭代
很直观的做法，先构建一个虚拟头节点，然后逐个比大小，直到结尾，注意，一个走到底以后要直接拼接另一个剩下的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution : def mergeTwoLists ( self, list1: Optional [ListNode], list2: Optional [ListNode] ) -> Optional [ListNode]: dummy = ListNode(0 ) cur = dummy 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 if list1 else list2 return dummy.next
时间复杂度O(m+n)，while 循环的次数不会超过两个链表的长度之和，空间复杂度为O(1)
在链表题中常用dummy，用 dummy 节点就不需要专门处理第一个节点，在最后返回 dummy.next 即可，这是链表题里的常规技巧
方法二：递归
递归的思路比较独特，有点类似拼接剩余的想法
如果把这个函数写成两个头部的拼接，那么只要确定了最终的头部以后，后续只需要重复这个过程就行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution : def mergeTwoLists ( self, list1: Optional [ListNode], list2: Optional [ListNode] ) -> Optional [ListNode]: if list1 is None : return list2 elif list2 is None : return list1 elif list1.val < list2.val: list1.next = self .mergeTwoLists(list1.next , list2) return list1 else : list2.next = self .mergeTwoLists(list1, list2.next ) return list2
更简洁，但不一定更优
在这里递归会消耗栈空间，空间复杂度 O(n + m)更高
两数相加 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头
示例 1：
1 2 3 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
1 2 输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
1 2 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
和正常算术一个思想，最主要的是怎么把握进位
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution : def addTwoNumbers ( self, l1: Optional [ListNode], l2: Optional [ListNode] ) -> Optional [ListNode]: dummy = ListNode(0 ) cur = dummy carry = 0 while l1 or l2 or carry: val1 = l1.val if l1 else 0 val2 = l2.val if l2 else 0 total = val1 + val2 + carry carry = total // 10 cur.next = ListNode(total % 10 ) cur = cur.next if l1: l1 = l1.next if l2: l2 = l2.next return dummy.next
时间复杂度O(max(m,n))，空间复杂度O(1)
删除链表的倒数第 N 个结点 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
示例 1：
1 2 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
1 2 输入：head = [1], n = 1 输出：[]
示例 3：
1 2 输入：head = [1,2], n = 1 输出：[1]
**进阶：**你能尝试使用一趟扫描实现吗？
方法一：反转链表
直观但复杂，通过反转链表后跳过第N个节点，再反转回去
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution : def removeNthFromEnd (self, head: Optional [ListNode], n: int ) -> Optional [ListNode]: back = self .reverse(head) dummy = ListNode(0 ) dummy.next = back cur = dummy for _ in range (n-1 ): cur = cur.next cur.next = cur.next .next return self .reverse(dummy.next ) def reverse (self, head ): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev
时间复杂度O(n)，空间复杂度O(1)，但是扫描链表多次，而且写起来很丑陋
方法二：栈
反转的方法太过复杂，如果用栈就能很快实现后进先出，从而快速定位并移除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution : def removeNthFromEnd (self, head: Optional [ListNode], n: int ) -> Optional [ListNode]: stack = list () dummy = ListNode(0 , head) cur = dummy while cur: stack.append(cur) cur = cur.next for _ in range (n): stack.pop() prev = stack[-1 ] prev.next = prev.next .next return dummy.next
时间复杂度O(n)，空间复杂度O(n)，但是只扫描链表一次
方法三：双指针
让快指针先走n步，那么当快指针走到链表尾部时，慢指针到达倒数第 n 个数的前一个位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def removeNthFromEnd (self, head: Optional [ListNode], n: int ) -> Optional [ListNode]: dummy = ListNode(0 , head) fast = slow = dummy for _ in range (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)，且只扫描链表一次，快慢指针是最优雅的做法
两两交换链表中的节点 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
示例 1：
1 2 输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
示例 3：
方法一：迭代
标准结构为：
1 prev → node1 → node2 → nxt
要用prev把前后连接起来，不然单反转会导致前后不连续
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def swapPairs (self, head: Optional [ListNode] ) -> Optional [ListNode]: dummy = ListNode(0 , head) prev = dummy while prev.next and prev.next .next : node1 = prev.next node2 = node1.next node1.next = node2.next node2.next = node1 prev.next = node2 prev = node1 return dummy.next
时间复杂度O(n)，空间复杂度O(1)
K 个一组翻转链表 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换
示例 1：
1 2 输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：
1 2 输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
非常类似两两反转，但不同的是需要维护一个函数来反转k个子链表，一样的结构
1 2 3 prev → a1 → a2 → ... → ak → next 变成 prev → ak → ... → a2 → a1 → next
分为几步：
用一个指针 tail = prev，往后走 k 步，如果中途遇到 None → 不够 k 个，直接结束
保存下一段起点，next_group = tail.next
反转当前段，start = prev.next，end = tail进行局部反转
重新接回：原 start 变成尾部，原 tail 变成头部
1 2 3 prev.next = 新头 原start.next = next_group prev = 原start
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution : def reverseKGroup (self, head: Optional [ListNode], k: int ) -> Optional [ListNode]: dummy = ListNode(0 , head) prev = dummy while head: tail = prev for _ in range (k): tail = tail.next if not tail: return dummy.next next_group = tail.next start = prev.next new_head, new_tail = self .reverse(start, tail) prev.next = new_head new_tail.next = next_group prev = new_tail def reverse (self, start, end ): prev = end.next cur = start while prev != end: nxt = cur.next cur.next = prev prev = cur cur = nxt return end, start
时间复杂度O(n)，空间复杂度O(1)
随机链表的复制 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝，深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值
新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y，返回复制链表的头节点
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null
你的代码 只 接受原链表的头节点 head 作为传入参数
示例 1：
1 2 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
1 2 输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
1 2 输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
方法一：回溯+哈希表
如果是普通链表，可以直接按照遍历的顺序创建链表节点
因为随机指针的存在，当拷贝节点时，当前节点的随机指针指向的节点可能还没创建，所以需要先确保所有新节点都存在
第一遍循环对每个原节点，创建一个新节点，并记录val映射
第二遍循环再恢复边结构
用哈希表可以很快实现一一匹配
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 """ # 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 """ class Solution : def copyRandomList (self, head: "Optional[Node]" ) -> "Optional[Node]" : if head is None : return None node_map = {} cur = head while cur: node_map[cur] = Node(cur.val) cur = cur.next cur = head while cur: node_map[cur].next = node_map.get(cur.next ) node_map[cur].random = node_map.get(cur.random) cur = cur.next return node_map[head]
时间复杂度O(n)，空间复杂度O(n)(哈希表开销)
方法二：迭代+拆分
如果为了让空间复杂度降为O(1)，不用哈希表保存“原节点 → 新节点”的映射，而是把映射关系临时嵌入链表结构中
用拓扑结构暂存映射信息，这是一种“结构编码映射”的技巧
成立的前提是：
链表结构允许临时修改
节点之间的物理邻接关系可被利用
如果结构是只读的，这个方法就不可行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 """ # 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 """ class Solution : def copyRandomList (self, head: "Optional[Node]" ) -> "Optional[Node]" : if head is None : return None cur = head while cur: newNode = Node(cur.val) newNode.next = cur.next cur.next = newNode cur = newNode.next cur = head while cur: if cur.random: cur.next .random = cur.random.next cur = cur.next .next cur = head newhead = cur.next while cur: newNode = cur.next cur.next = newNode.next if newNode.next : newNode.next = newNode.next .next cur = cur.next return newhead
排序链表 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表
示例 1：
1 2 输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：
1 2 输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：
**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
方法一：自顶向下归并排序
直接对一整条链表排序过于困难，有什么办法可以简化这个问题呢？
之前有合并过两个有序链表，那么是否可以把这个问题也简化成这样呢？
通过快慢指针可以将链表拆分为两部分
1 2 slow = head fast = head.next
这里fast不从head开始是保证在奇数情况slow停在中点位置，在偶数情况slow停在左侧尾端
这里和之前不一样的地方就是，整个链表本身无序，所以即使拆分了也不能像之前那样直接遍历，需要通过“不断二分 + 有序合并”构造全局有序
1 2 3 4 5 4 2 1 3 / \ 4 2 1 3 / \ / \ 4 2 1 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution : def sortList (self, head: Optional [ListNode] ) -> Optional [ListNode]: if not head or not head.next : return head slow = head fast = 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 .merge(left, right) def merge (self, l1: Optional [ListNode], l2: Optional [ListNode] ) -> Optional [ListNode]: dummy = ListNode(0 ) cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else : cur.next = l2 l2 = l2.next cur = cur.next if l1: cur.next = l1 else : cur.next = l2 return dummy.next
sortList中并不排序，排序全部集中在合并函数中
每次递归都要用快慢指针找中点O(n)，递归排序所以时间复杂度是O(nlogn)
空间复杂度主要取决于递归调用的栈空间，由于递归栈，空间复杂度为O(logn)
这种方法相当于切分到最小再往上合并，递归会消耗而外空间
为了降低空间复杂度，把“自顶向下归并排序”改成“自底向上归并排序”
方法二：自底向上归并排序
从长度 = 1 的子链表开始，两两合并，长度翻倍，直到覆盖整个链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 class Solution : def sortList (self, head: Optional [ListNode] ) -> Optional [ListNode]: if not head or not head.next : return head cur = head length = 0 while cur: length += 1 cur = cur.next dummy = ListNode(0 , head) step = 1 while step < length: prev = dummy cur = dummy.next while cur: left = cur right = self .split(left, step) cur = self .split(right, step) merged = self .merge(left, right) prev.next = merged while prev.next : prev = prev.next step *= 2 return dummy.next def split (self, head, n ): while n - 1 and head: head = head.next n -= 1 if not head: return None second = head.next head.next = None return second def merge (self, l1, l2 ): dummy = ListNode(0 ) cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else : cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 return dummy.next
这样就不需要递归，直接在链表上不断从小块到大块排序，空间复杂度降为O(1)
合并 K 个升序链表 给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表
示例 1：
1 2 3 4 5 6 7 8 9 10 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
示例 3：
方法一：暴力排序
和排列两个有序链表一样，如果遍历每一个进行比较也可以实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution : def mergeKLists (self, lists: List [Optional [ListNode]] ) -> Optional [ListNode]: dummy = ListNode(0 ) cur = dummy while True : min_index = -1 min_value = float ("inf" ) for i in range (len (lists)): if lists[i] and lists[i].val < min_value: min_value = lists[i].val min_index = i if min_index == -1 : break cur.next = lists[min_index] cur = cur.next lists[min_index] = lists[min_index].next return dummy.next
但这种做法的时间复杂度O(nk)，容易超时
方法二：最小堆
链表本身已经有序，每条链表只有头节点可能成为全局最小，所以可以维护一个子链表头部的优先队列 ，直接插入即可，就不需要每次遍历，从而降低时间复杂度
算法流程：
把每个非空链表的头节点放入最小堆
每次：
弹出堆顶（当前最小节点）
接到结果链表
如果该节点有 next，把 next 放入堆
重复直到堆空
这样做的话时间复杂度为O(nlogk)，相比之前暴力做法好了很多
在放入优先队列时，组合为
带上编号是为了避免在同值时出错，使得尚能比较
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution : def mergeKLists (self, lists: List [Optional [ListNode]] ) -> Optional [ListNode]: heap = [] for i, node in enumerate (lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy = ListNode(0 ) cur = dummy while heap: _, i, node = heapq.heappop(heap) cur.next = node cur = cur.next if node.next : heapq.heappush(heap, (node.next .val, i, node.next )) return dummy.next
二叉树 BFS：Breadth-First Search（广度优先搜索）
BST：Binary Search Tree（二叉搜索树） 满足：左子树 < 根 < 右子树
二叉树的中序遍历 给定一个二叉树的根节点 root ，返回它的 中序 遍历
示例 1：
1 2 输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
示例 3：
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
什么是二叉树遍历
遍历方式
顺序
前序
根 → 左 → 右
中序
左 → 根 → 右
后序
左 → 右 → 根
1 2 3 4 5 6 7 8 9 10 11 50 / \ 30 70 / \ / \ 20 40 60 80 / \ / \ / \ / \ 10 25 35 45 55 65 75 90 / 5 5 10 20 25 30 35 40 45 50 55 60 65 70 75 80 90
方法一：递归
按照这个遍历模式，可以利用递归走到子节点再往回慢慢加结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def inorderTraversal (self, root: Optional [TreeNode] ) -> List [int ]: result = [] def dfs (node ): if node is None : return dfs(node.left) result.append(node.val) dfs(node.right) dfs(root) return result
递归天然等价于“隐式栈”，后进先出（LIFO）
时间复杂度和空间复杂度均为O(n)
方法二：迭代
也可以把递归这个隐式栈显式写出来
一直往左走，把“回来的路径”压入栈
左到底后，开始回退
每弹出一个节点：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution : def inorderTraversal (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) cur = cur.right return result
同样时间复杂度和空间复杂度均为O(n)
空间复杂度O(1)方法太深，没研究
二叉树的最大深度 给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
1 2 输入：root = [3,9,20,null,null,15,7] 输出：3
示例 2：
1 2 输入：root = [1,null,2] 输出：2
递归
左子树和右子树的最大深度又可以以同样的方式进行计算，可以先递归计算出其左子树和右子树的最大深度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution : def maxDepth (self, root: Optional [TreeNode] ) -> int : if root is None : return 0 l_depth = self .maxDepth(root.left) r_depth = self .maxDepth(root.right) return max (l_depth, r_depth) + 1
时间复杂度O(n)，n 为二叉树节点的数目
空间复杂度O(h)，h 是树高（递归栈深度）
翻转二叉树 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点
示例 1
1 2 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]
示例 2：
递归
递归翻转左子树
递归翻转右子树
最后在当前节点交换左右
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution : def invertTree (self, root: Optional [TreeNode] ) -> Optional [TreeNode]: if root is None : return None l = self .invertTree(root.left) r = self .invertTree(root.right) root.left, root.right = r, l return root
时间复杂度为O(n)，空间复杂度O(h)
对称二叉树 给你一个二叉树的根节点 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 18 19 20 21 22 class Solution : def isSymmetric (self, root: Optional [TreeNode] ) -> bool : def isMirror (t1, t2 ): if not t1 and not t2: return True if not t1 or not t2: return False if t1.val != t2.val: return False return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left) if not root: return True return isMirror(root.left, root.right)
直接比较根节点的左右两端，返回第一个端点左和第二个端点右，第一个端点右和第二个端点左 两组的比较结果
时间复杂度为O(n)，空间复杂度O(h)
方法二：迭代
用一个双端队列，不断比较，直到全部比完，从上到下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution : def isSymmetric (self, root: Optional [TreeNode] ) -> bool : if not root: return True dq = deque() dq.append(root.left) dq.append(root.right) while dq: t1 = dq.popleft() t2 = dq.popleft() if not t1 and not t2: continue if not t1 or not t2: return False if t1.val != t2.val: return False dq.append(t1.left) dq.append(t2.right) dq.append(t1.right) dq.append(t2.left) return True
二叉树的直径 给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
1 2 3 输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度
示例 2：
递归函数 depth(node) 做两件事：
返回以 node 为根的最大深度
在每个节点尝试更新一次直径
因为：
left 是左子树最大深度
right 是右子树最大深度
left + right 就是经过当前节点的最长路径
遍历所有节点，自然会覆盖全局最大情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def diameterOfBinaryTree (self, root: Optional [TreeNode] ) -> int : self .diameter = 0 def depth (node ): if not node: return 0 left = depth(node.left) right = depth(node.right) self .diameter = max (self .diameter, left+right) return max (left, right) + 1 depth(root) return self .diameter
二叉树的层序遍历 给你二叉树的根节点 root ，返回其节点值的 层序遍历 （即逐层地，从左到右访问所有节点）
示例 1：
1 2 输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
示例 3：
广度优先搜索
为什么必须用队列？因为层序遍历的结构逻辑是：
这是一种“先进先出”的访问顺序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution : def levelOrder (self, root: Optional [TreeNode] ) -> List [List [int ]]: if root is None : return [] res = [] dq = deque([root]) while dq: level = [] size = len (dq) for _ in range (size): node = dq.popleft() level.append(node.val) if node.left: dq.append(node.left) if node.right: dq.append(node.right) res.append(level) return res
将有序数组转换为二叉搜索树 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
示例 1：
1 2 3 输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
示例 2：
1 2 3 输入：nums = [1,3] 输出：[3,1] 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
对于任意节点：
左子树所有值 < 当前节点值
右子树所有值 > 当前节点值
如果对二叉搜索树（BST）做中序遍历，得到的一定是升序序列
题目其实在问：如何从一个有序数组构造一棵“尽量矮”的 BST？
所以核心就在于找中点，然后递归构造左右子树，选中点是为了保证左右规模接近，从而高度平衡
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution : def sortedArrayToBST (self, nums: List [int ] ) -> Optional [TreeNode]: def build (left, right ): if left > right: return None mid = (left + right) // 2 root = TreeNode(nums[mid]) root.left = build(left, mid - 1 ) root.right = build(mid + 1 , right) return root return build(0 , len (nums) - 1 )
验证二叉搜索树 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
1 2 输入：root = [2,1,3] 输出：true
示例 2：
1 2 3 输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。
这题的重点是不能只递归比较当前node的val和left\right的val
需要注意的是全局约束
左子树所有值 < 当前节点
右子树所有值 > 当前节点
1 2 3 4 5 5 / \ 3 7 / 4 ← 这里违反了整体区间约束
递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def isValidBST (self, root: Optional [TreeNode] ) -> bool : def dfs (node, lower, upper ): if node is None : return True if node.val <= lower or node.val >= upper: return False return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper) return dfs(root, float ("-inf" ), float ("inf" ))
二叉搜索树中第 K 小的元素 给定一个二叉搜索树BST的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）
示例 1：
1 2 输入：root = [3,1,4,null,2], k = 1 输出：1
示例 2：
1 2 输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
暴力做法
不依赖BST特性，当作普通二叉树来做
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution : def kthSmallest (self, root: Optional [TreeNode], k: int ) -> int : nums = [] dq = deque([root]) while dq: size = len (dq) for _ in range (size): node = dq.popleft() nums.append(node.val) if node.left: dq.append(node.left) if node.right: dq.append(node.right) nums.sort() return nums[k - 1 ]
不考虑二叉树特性，层序遍历以后排序
时间复杂度O(nlogn)，空间复杂度O(n)
中序遍历
如果利用BST特性，左<根<右
那么就可以先走到最左边，然后回头慢慢找
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution : def kthSmallest (self, root: Optional [TreeNode], k: int ) -> int : stack = [] node = root while True : while node: stack.append(node) node = node.left node = stack.pop() k -= 1 if k == 0 : return node.val node = node.right
时间复杂度O(h+k)，空间复杂度O(h)
如果树经常被修改，同时要频繁查询第 k 小，那么单纯中序遍历是低效的
要做的是让“第 k 小”变成O(log n)
核心思想：给每个节点增加一个统计量
在每个节点维护一个字段：size = 以该节点为根的子树节点总数
设当前节点为 node：
左子树节点数 = left_size
当前节点在整棵子树中的排名 = left_size + 1
于是：
若 k ≤ left_size → 去左子树
若 k = left_size + 1 → 当前节点
若 k > left_size + 1 → 去右子树找第 k - left_size - 1 小
了解就行了，写起来太麻烦了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class MyBst : def __init__ (self, root: TreeNode ): self .root = root self ._build_size(root) def _build_size (self, node ): if not node: return 0 node.size = 1 + self ._build_size(node.left) + self ._build_size(node.right) return node.size def kth_smallest (self, k: int ) -> int : node = self .root while node: left_size = node.left.size if node.left else 0 if k <= left_size: node = node.left elif k == left_size + 1 : return node.val else : k -= left_size + 1 node = node.right class Solution : def kthSmallest (self, root: TreeNode, k: int ) -> int : bst = MyBst(root) return bst.kth_smallest(k)
.webp)
 (1).png)
