哈希

定义哈希表的方式

Dict = {}空表

dict()函数，hash_table = dict([('a',1),('b',2)])

字典推导式hash_table = {x:x**2 for x in range(5)}# {0:0, 1:1, 2:4, 3:9, 4:16}

for key, value in hash_table.items(): print(key, value)

键必须可哈希：即不可变类型（如 int, str, tuple），列表、字典等可变类型不能作为键。

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

哈希表，用字典实现，注意key不能是可变的，如列表、字典

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i,x in enumerate(nums):
            if target - x in dict:
                return [dict[target-x],i]
            dict[x] = i
        

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

defaultdict(list)，Python collections 模块中的一个类，dict的子类，当访问一个不存在的键时，不会抛出 KeyError，而是自动调用一个默认工厂函数来生成一个默认值，并把这个键和默认值存入字典中。

d[key] 如果 key 不存在，就会自动执行 d[key] = list()，然后返回这个新列表的引用。

关于默认工厂：如下表

计数除了counter，还可以用cnt = defauldict(int):for x in [1,2]:cnt[x]+=1---->cnt:{1:1,2:1}

做法：默认字典，遍历s in str，把s排序之后作为键，d[sorted].append(s),返回列表d.values()

• sorted(s)：返回的是列表，原字符串不变。

• s.sort()：这个方法只存在于列表中，字符串没有 .sort() 方法，所以不能对字符串直接调用 s.sort()。

• 做key时候，list是可变的不能做key，只能用字符串

记住这个铁律：在 Python 里想用排序后的结果做字典的键，必须 ''.join(sorted(s))。

三刷时候，defaultdict定义写法：defaultdict(list)

返回值的写法：list(d.values())

工厂函数	作用	示例
list	默认空列表	d = defaultdict(list)
int	默认 0	d = defaultdict(int) 适合计数
set	默认空集合	d = defaultdict(set) 适合去重收集
str	默认空字符串 ''	较少使用
lambda: 100	自定义默认值	d = defaultdict(lambda: 100)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            s_sorted = ''.join(sorted(s))
            d[s_sorted].append(s)
        return list(d.values())

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

数字有重复，去重--->set。

序列长度，先找到起点i，然后while找到终点--->这是一个序列，记录一下长度

什么叫-序列不可能挨着：当前的一个序列长度ans，ans*2已经>=总长，ans不可能再大了

去重-i是否为起点-序列长度-长度两倍大于等于总长，剪枝

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 排序nlogn  去重的list，后-前的list，最长1字段
        s = set(nums)
        ans = 0
        l = len(s)
        for i in s :
            if i-1 in s :
                continue #i-1也在里面，i不能是起点
            # i是起点
            y = i + 1
            while y in s :
                y += 1
            ans = max(ans,y-i) #每个起点更新一下ans
            # 因为序列不可能挨着，如果ans已经>=长度的一半就可以直接end
            if ans * 2 >= l :
                break
        return ans
            

双指针

双指针一般都是while

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

保持相对顺序

学会变换题目的意思：把非0的拿出来列一下，然后其他地方后全是0，更像是技巧的做法

双指针做法：相当于是120034这样，两个指针之间是0，左处理好的序列尾，右待处理的头部

class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) l = r = 0 while r < n: if nums[r]: nums[l],nums[r] = nums[r], nums[l] l += 1 r += 1

盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

左右，留下一个长度高的。

先算一个值，然后考虑移动方向

class Solution: def maxArea(self, height: List[int]) -> int: ans = 0 left = 0 right = len(height)-1 while left < right: ans = max(ans,(right-left)*min(height[left],height[right])) 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：

输入：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] 。 注意，输出的顺序和三元组的顺序并不重要。

固定当前i，遍历jk，固定当前i，所以，nums[i]==nums[i-1]时候，要跳过去。也就是nums[0]的三元组算过了，如果nums[1]==nums[0]，说明nums[1]的三元组和nums[0]的是一样的

其中jk的增减是:

j+1，且只要nums[j]==nums[j-1],j++;

k-1,且只要nums[k]==nums[k+1],k--；为了找到包含i的全部的三元组

然后思考优化方法，在移动jk之前

移动时候，j<k还是j<n----j<k

一直都是j<k,双指针的遍历while

最后考虑优化：

如果前三个和大于0，也就是最小的三个和已经大于0，那么直接break，因为不可能等于0了；

如果当前x加最后两个最大的还小于0，说明x不可能组成三元组，x太小了，跳过

再刷，

这里，i-1就要记得判断i大于0

class Solution: def threeSum(self, nums: list[int]) -> list[list[int]]: nums.sort() ans = [] n = len(nums) for i in range(n-2): x = nums[i] if i > 0 and x == nums[i - 1]: continue ##优化 if x + nums[i+1] + nums[i+2] > 0: break if x + nums[-2] + nums[-1] < 0: continue j = i + 1 k = n - 1 while j < k: s = x + nums[j] + nums[k] if s > 0: k -= 1 elif s < 0: j += 1 else: ans.append([x, nums[j], nums[k]]) j += 1 while j < k and nums[j] == nums[j-1]: j += 1 k -= 1 while j < k and nums[k] == nums[k+1]: k -= 1 return ans

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

hard，很难想

前后缀分解onon

计算每个桶的装水量，需要用到左边最高的，右边最高的，然后取左右的min和自己的height，min-height

class Solution: def trap(self, height: List[int]) -> int: ans = 0 n = len(height) pre = [0] * n pre[0] = height[0] suf = [0] * n suf[-1] = height[-1] for i in range(1,n): pre[i] = max(pre[i-1],height[i]) for i in range(n-2,-1,-1): suf[i] = max(suf[i+1],height[i]) for i in range(n): ans += min(pre[i],suf[i]) - height[i] return ans

class Solution: def trap(self, height: List[int]) -> int: ans = 0 n = len(height) pre = 0 suf = 0 l = 0 r = n-1 while l <= r: pre = max(pre, height[l]) suf = max(suf, height[r]) if pre < suf: ans += pre - height[l] l += 1 else: ans += suf - height[r] r -= 1 return ans

双向双指针

前缀max比后缀max小，左边的容量就是前缀max，左边右移

前缀max比后缀max大，右边的容量就是后缀max，右边左移

看了代码就是上面这段话的写法。但是不明白逻辑分析：

目前知道的前缀，后缀，max。短的那个可以算了，长的不能动，

对于任意位置 i，它能蓄的水量取决于：

• 左边（包括自己）的最高柱子高度 left_max

• 右边（包括自己）的最高柱子高度 right_max

• 则 i 处的水量 = min(left_max, right_max) - height[i]（若为负则取0）。

想明白了。

class Solution: def trap(self, height: List[int]) -> int: ans = 0 n = len(height) pre = 0 suf = 0 l = 0 r = n - 1 while l <= r: pre = max(pre,height[l]) suf = max(suf,height[r]) if pre < suf: ans += pre - height[l] l += 1 else: ans += suf - height[r] r -= 1 return ans

单调栈

滑动窗口

无重复字符的最长字串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

又遇到Counter()了。cnt = Counter()空计数器。

cnt = Counter(nums) 的时间复杂度是 O(n)，空间复杂度是 O(k)，其中 n 是 nums 的长度，k 是 nums 中不同元素的数量（最坏情况下 k = n）。

这个滑窗左右都是从0开始的

疑问之why：cnt[s[left]]-=1

需要连着的字符串没错吧?这个字符串保存在l和r之间没错吧?当右边出现重复的了，说明这个区间不满足了，左侧就开始出去，直到满足了之后，才再次开始动右侧的。

我的疑惑大概就是疑惑abcb这种，想的是到第二个b了，左+会导致a出去，但此时ans已经记录3了，不影响。

类比理解，拿糖果，拿到重复的了，只能从左边依次拿掉之前拿的。

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ans = 0 left = 0 cnt = Counter() #hashmap, key:cher,v:int for right,x in enumerate(s): cnt[x] += 1 while cnt[x] > 1: #针对连续的相同的 cnt[s[left]] -= 1 left += 1 ans = max(ans, right-left+1) return ans

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

遍历，某一段的cnt相等，把段首的下标append进ans

但其实代码实现是，cntp，然后遍历s，进来一个cntp的x-1，如果数目小于0了，说明不是，就left右移，把剪掉的加回来。如果不是cnt<0,而且窗口大小和p一样大，left就能进到答案了。

和上一题有点像啊。这个是不定长滑窗。这个判断结束的窗口大小和p一样很妙。

以后试试每个算法都想一下结束条件？

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: # 不定长滑窗，枚举右端点，发现有cnts>cntp，left+=1 # 满足cnt--->长度--->append cnt = Counter(p) ans = [] left = 0 for right,x in enumerate(s): cnt[x] -= 1 #进来一个减1 while cnt[x] < 0: #小于0了，开始复原移动 # cnt[x] += 1 # 左端离开,而不是单单复原，全局看 cnt[s[left]] += 1 left += 1 if right - left + 1 == len(p): ans.append(left) return ans

子串

和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2 输出：2

子数组和字串有区别的，子数组连续的

前缀和-sj-si = k多少对。但是on2

优化成两数之和，si = sj-k，枚举当前前缀和sj，看看多少个前缀和等于sj-k，这样它们之间的和就是sj-sj+k=k

需要次数了，用cnt，cnt = defaultdict(int)，和counter啥区别？

为什么defaultdict(int)：如果哈希表中没有 s - k 这个键，我们希望返回 0

这个写法，优化了，直接一边遍历一边记录了

• defaultdict(int)：来自 collections.defaultdict，是一个带有默认工厂的字典。这里 int 作为工厂函数，当访问不存在的键时自动调用 int() 返回 0，并插入该键。

• defaultdict(int)：执行 cnt[key] 如果 key 不存在，会立刻创建键并设值为 0，然后返回 0。

• Counter()：执行 cnt[key] 如果 key 不存在，不会创建键，只返回 0。但执行 cnt[key] += 1 时，由于需要先读后写，会创建键并赋值为 1。

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: # 前缀和， 看有多少对下标ij满足sj-si=k # 求出前缀和再暴力找，太慢了n方 # 两数之和，si = sj - k，枚举当前前缀和sj，看看之前有多少个前缀和等于sj-k # 哈希cnt，k为sj，v为次数 ans = s = 0 cnt = defaultdict(int) for x in nums: cnt[s] += 1 # 0出现1次 s += x # 记录到当前位置的前缀和s ans += cnt[s-k] # s当前前缀和，这样写，写法简单了 return ans

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：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：

输入：nums = [1], k = 1 输出：[1]

看题的第一眼，想不到什么。暴力的话，onk也就是最坏on2？

单调队列，怎么想到：维持一个单调递减的队列。

单调队列是一种“优化技巧”，它基于观察：

• 当新元素进入窗口时，它会把窗口中所有比它小的元素“淘汰掉”，因为它们永远不可能成为该窗口及后面窗口的最大值（因为新元素更大且更晚离开）。 这个观察不是直觉能立马捕捉的，需要做过类似题目，或者通过分析“窗口移动时，哪些元素有希望成为未来最大值”才能得出。

滑动窗口求最值，单调队列来帮忙

索引队列，单调减的索引队列

知豆ans的大小n-k+1，q双端队列，左出右进

首先判断是否要出去或进去：队列不空而且新来的x比队列中最右的大，那最右边的就要出队，否则就进去。

再判断队列首部的元素过期没有：当前遍历的左端点索引（0~n-k+1）是i-k+1，当这个左端点已经大于队首时候，说明队首过期了，popleft

最后判断记录否：i>=k-1，and[i-k+1]=numsq[0]

也就是答案记录位置在ans里，就是相当于原nums的0到n-k+1

感觉自己就是不明白i-k+1，总觉得i-k+1不是ans的下标。

是啊，一共就i-k+1个值。只有i>=k-1才开始记录。

class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) ans = [-inf] * (n - k + 1) # 结果数组长度 q = deque() for i, x in enumerate(nums): # 1. 右入：维护队列单调递减（从队首到队尾值递减） while q and nums[q[-1]] <= x: q.pop() # 弹出队尾那些比 x 小的，因为他们不可能再是最大 q.append(i) # 2. 左出：如果队首索引已离开窗口，弹出 if i - k + 1 > q[0]: # 窗口左边界 = i - k + 1，如果左边界 > 队首索引，说明队首过期 q.popleft() # 3. 记录答案：当 i 至少为 k-1 时，窗口形成 if i >= k - 1: ans[i - k + 1] = nums[q[0]] return ans

最小覆盖字串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

又要用counter了哈哈哈

判断合不合适就是看cnts>=cntt，这就说明s包含t了。更新区间，取min

然后滑动左边的，看看区间见能否再小。

一直不满足s>=t,ansleft设置成-1，就能用这个判断了

马上要执行 left += 1，这个字符即将离开滑动窗口，所以它在窗口中的出现次数必须减去 1。

class Solution: def minWindow(self, s: str, t: str) -> str: # 要记录个数，应该要用到哈希？ # 但哈希怎么记录个数?用字典？ #------------------------------#想的是啥？？？ # 涵盖 cntt = Counter(t) cnts = Counter() ansleft = -1 ansright = len(s) left = 0 for right,x in enumerate(s): cnts[x] += 1 while cnts >=cntt: if right - left < ansright - ansleft: ansleft,ansright = left,right cnts[s[left]] -= 1 left += 1 return "" if ansleft < 0 else s[ansleft:ansright+1]

普通数组

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

数组和，前缀

遍历同时记录前缀和，前缀减去之前的最小前缀和，更新之前的min前缀和

知屿pre为什么可以初始化成0，代表从开头到当前的累计和，还没开始遍历当然就是0

class Solution: def maxSubArray(self, nums: List[int]) -> int: ans = -inf min_pre = pre = 0 for x in nums: pre += x ans = max(ans, pre - min_pre) min_pre = min(min_pre, pre) return ans

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start(i), end(i)] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

这个的写法，sort，按照第一个元素，就是key = lambda p : p[0]

排序，遍历，合并：ans不空且p[0]<=ans[-1][1]，更新右端点为maxp[1],ans[-1][1]。直接加入append

也就是先的排序，让后面的简洁了

nums.sort()于sorted（nums）：

.sort() 是列表的方法，原地修改原列表，返回 None；而 sorted() 是内置函数，返回一个新列表，不改变原对象。

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: #先按照第一个sort，然后看下面的左区间》=上一个的右，就合并两个 ans = [] n = len(intervals) intervals.sort(key = lambda p : p[0]) # 合并 for p in intervals: if ans and p[0] <= ans[-1][1]: ans[-1][1] = max(p[1], ans[-1][1]) else:# 不合并 ans.append(p) return ans

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: 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]

原地修改

关键在于想明白：轮转k相当于（k=n%k）：

先翻转整个数组

再翻转0~k-1的数组

最后反转k~n-1的数组

so：先实现一个reverse

Why,k%=n?--------k如果是n的倍数，真正有效的只有k%n次。取模可以避免无效重复旋转。且k可能大于n，会越界

class Solution: 2 def rotate(self, nums: List[int], k: int) -> None: 3 """ 4 Do not return anything, modify nums in-place instead. 5 """ 6 #负负得正，可不可以复制数组呢 7 def reverse(i:int,j:int) -> None: 8 while i < j: 9 nums[i], nums[j] = nums[j], nums[i] 10 i += 1 11 j -= 1 12 n = len(nums) 13 k %= n 14 reverse(0,n-1) 15 reverse(0,k-1) 16 reverse(k,n-1)

除了自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]输出: [24,12,8,6]

太巧妙了。。。

先遍历求出来后缀的乘积suf

然后前缀pre先为1，遍历i，x in nums

i=0时候自然的suf[i] = suf[i] * pre，刚好就是除了i位置之外的其他的乘积；

之后更新pre，pre记录了前面的乘积，suf记录了后面的乘积，每次让pre*suf就是除了i之外的其他的了。

自己写时候能不能试试先求前缀乘积然后再后缀呢？

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) suf = [1] * n # 后缀的乘积 for i in range(n-2,-1,-1): suf[i] = suf[i+1] * nums[i+1] # 前缀， pre = 1 for i,x in enumerate(nums): #i=0时候，pre=1刚好ans就是suf #然后循环，pre就记录了nums[0]-nums[i-1]的乘积 suf[i] *= pre pre *= x return suf

果然反过来也是可行的

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) suf = 1 pre = [1] * n for i in range(1,n): pre[i] = pre[i - 1] * nums[i - 1] for i in range(n-1,-1, -1): pre[i] *= suf suf *= nums[i] return pre

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。

又看了遍答案，看不懂了。。。

原地哈希

利用数组本身作为哈希表，将每个正整数 x 放到数组索引 x-1 的位置上（即数值1放在索引0，数值2放在索引1，依此类推）。这样，遍历数组后，第一个出现 nums[i] != i+1 的位置就是缺失的最小正数。

为什么能这样放，不会怕x-1小于0就没法放了？---找的是最小正数

先归位：nums[i]在1-n之间而且不在对的位置上，交换位置

硅烷位置之后，遍历找第一个不在位置的

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]: #and后面的就是没坐正确位置时候 j = nums[i] - 1 nums[i], nums[j] = nums[j], nums[i] #排完座之后 for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1

矩阵

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

看不懂，为什么

rowzero = [0 in row for row in matrix]

colzero = [0 in col for col in zip(*matrix)]

这不是两个全0的吗？

if row0 or col0:

matrix[i][j] = 0

If true，如果这两个里有个不是0或者全不是0，才弄成0，不对吧？

我嘞个都啊，0 in row，返回的bool

1. rowzero = [0 in row for row in matrix] 这行代码的意思是：对于每一行 row，检查 0 in row（该行是否包含0），得到一个布尔值。所以 rowzero 是一个列表，长度等于行数，每个元素是 True（该行有0）或 False（该行无0）。

2. colzero = [0 in col for col in zip(*matrix)] zip(*matrix) 将矩阵转置，得到每一列的元组。然后检查每一列是否包含0，得到一个布尔列表，长度等于列数。

转置，zip(*matrix)

class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ rowzero = [0 in row for row in matrix] colzero = [0 in col for col in zip(*matrix)] for i,row0 in enumerate(rowzero): for j,col0 in enumerate(colzero): if row0 or col0: matrix[i][j] = 0

原地解法

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

定义方向DIRS，右下左上；遍历ij，转为记录di

遍历ij，遍历过的标记为none，更新下一步的位置为x，y

判断xy的合法性&标记否

不合法或已经标记，转弯，di = （di+1）%4

%4即在0~3之间循环，

更新ij

x和y的区间

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 右下左上 class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: m, n = len(matrix), len(matrix[0]) ans = [] i = j = di = 0 for _ in range(m*n): #记录，标记 ans.append(matrix[i][j]) matrix[i][j] = None #下一步位置xy x = i + DIRS[di][0] y = j + DIRS[di][1] #位置不合法 或 已标记，转弯改di if x < 0 or x >=m or y < 0 or y >= n or matrix[x][y] == None: di = (di + 1) % 4 #合法且未标记 i = i + DIRS[di][0] j = j + DIRS[di][1] return ans

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]

原地操作

先转置，再每行反转

转置，遍历i>j上三角部分

用坐标变换：顺时针旋转 90 度后，原位置 (i, j) 的新位置是 (j, n-1-i)。

• 先转置：(i, j) → (j, i)

• 再水平翻转（行反转）：(j, i) → (j, n-1-i)。

转置是，ij，ji=ji，ij

on2，o1

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(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] #行reverse for row in matrix: row.reverse()

搜索二维矩阵Ⅱ

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。

• 每列的元素从上到下升序排列。

左下角ij

当ij满足条件时候，也就是j<n，i>=0

判断是，true；<target，需要更大的数，j+；否则就是i-

Return

从大的看，慢慢删除大的

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: #在一个点，往右往下二选一？广搜深搜？ # 好啊好啊，从大的看，慢慢删除大的 m, n = len(matrix), len(matrix[0]) i, j = m - 1, 0 while j < n and i >= 0: if matrix[i][j] == target: return True if matrix[i][j] < target: j += 1 else: i -= 1 return False

链表

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

相当于pre，cur向右平移

为什么不返回cur next，不存在指向pre的指针了吗

none的next不合法

循环內部确实是cur next= pre

cur=head也就是cur指向head

则cur.next指向head的下个节点

暂时无法在飞书文档外展示此内容

nxt就是中介，为了让pre和cur成功交换

# 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]: pre = None cur = head while cur != None: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre#逐步，让pre指向头

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

• listA - 第一个链表

• listB - 第二个链表

• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数

• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

直接从头节点开始同时next

如果下一个节点存在就next，不存在等于另一个链表的头节点，why？

假设链表 A 的长度为 a，链表 B 的长度为 b，它们的公共部分长度为 c（不相交时 c=0）。

• 指针 p 走完链表 A 再走链表 B 的总路程：a + (b - c)

• 指针 q 走完链表 B 再走链表 A 的总路程：b + (a - c)

两者相等：a + b - c = b + a - c。

因此，当 p 和 q 都完成“先走自己的链表，再走对方的链表”后，它们一定会同时到达相交节点（如果相交）或同时到达 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) -> Optional[ListNode]: # 4的next是1，6的next也是1，不能说明1是开始节点。 p , q = headA, headB while p is not q:#指针判等，！=，也可 p = p.next if p else headB q = q.next if q else headA return p #到头之后，走别人的路

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

回文 序列是向前和向后读都相同的序列。

栈：

先全部入栈

head，栈顶记录并弹出

比较两个值，不等false

不然就是headnext

返回

快慢指针：

遍历完之后，slow指向中间

栈

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: # 栈，最后为空；进，top = cur，pop---->on # 快慢指针+栈 # 反转，递归 stack = [] cur = head while (cur):#入栈 stack.append(cur) cur = cur.next #看底和top，一个pop，一个next node1 = head while(stack): node2 = stack.pop() if node1.val != node2.val:#为啥不能指针相等 return False else : node1 = node1.next return True

快慢指针

快一慢二，奇数快指最后一个节点（fast.next=null）；偶数快指空fast=null

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: # 快慢指针找中间 slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 反转后半部分 pre = None while slow: nxt = slow.next slow.next = pre pre = slow slow = nxt # 判断是否相等 while pre: if pre.val != head.val: return False pre = pre.next head = head.next return True

递归on

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false。

快慢指针，有环会遇到

# 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 = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if fast is slow: return True return False

环形链表Ⅱ

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

为什么相等时候需要判断slow不等于head？

当快慢指针相遇（fast == slow）时，只能说明链表中有环，但相遇点不一定是环的入口。为了找到入口，经典方法是：将其中一个指针（如 slow）留在相遇点，另一个指针（head）重新指向链表头，然后两个指针同时以每次一步的速度向前移动，它们再次相遇的节点就是环的入口。

相遇慢没走完一圈

相遇点开始，往下走，直到head=slow，slow即入口；否则返回none

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast:#没环时候，因为while，都不可能相等 # 不一定非判等，判布冯 while slow != head: head = head.next slow = slow.next return slow return None

合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

递归，判空返回，否则比较大小，递归，返回

迭代，哨兵，cur = bing = ListNode(),

• ListNode() 相当于 ListNode(0, None)，创建了一个值为 0 且 next 为 None 的节点。

• 这个 0 不会被使用，因为结果链表从 bing.next 开始，哨兵本身的值被忽略

• bing = ListNode() 创建哨兵节点，简化链表构建逻辑。

• 最终返回 bing.next，即合并后链表的真实头节点。

• 哨兵模式在链表问题中非常常见（如合并、删除、反转等），可以有效避免空指针异常和边界判断。

迭代，递归

迭代，哨兵：

递归，二叉树：

递归

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: # 递归，终止条件 #种植、 if list1 is None:return list2 if list2 is None:return list1 if list1.val < list2.val: list1.next = self.mergeTwoLists(list1.next,list2) return list1 list2.next = self.mergeTwoLists(list1, list2.next) return list2

迭代

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: #迭代 # 哨兵 cur = bing = ListNode() #都不空时候，小的加入到cur额就是烧饼下面 while list1 and list2: if list1.val < list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next #cur往下 cur = cur.next #有空了，合并不空的，cur.next = list1 or list2 cur.next = list1 or list2 #返回哨兵的next即新头 return bing.next

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

迭代方法，弄个头节点，代码就很容易理解了，就是简单的迭代

递归：每次递归只处理当前一位（两个链表当前节点值和进位），然后递归处理剩下的链表

参数多一个

先确定终止条件：两个链表都空且没进位，返回none

处理当前这一位，用s记录进位

看不懂最后的返回：

return ListNode(s % 10, self.addTwoNumbers(l1, l2, s // 10))

其实就是：

total = carry

if l1: total += l1.val l1 = l1.next

if l2: total += l2.val l2 = l2.next # 当前位的数字

digit = total % 10 # 新的进位

new_carry = total // 10 # 递归调用，得到后续部分的链表

next_node = self.addTwoNumbers(l1, l2, new_carry) # 创建当前节点，并指向后续链表 return ListNode(digit, next_node)

写时候别忘了在函数中初始化carry的值，carry:int=0

递归（时空均O(n)）

左边的数相加之后，得到的值保存，然后进位，递推.其中除10的余为新值，商为进位

写法一：创建新节点

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode],carry = 0) -> Optional[ListNode]: #carry 进位 # 终止条件 if l1 is None and l2 is None and carry == 0: return None # 当前位的和 s = carry if l1: s += l1.val l1 = l1.next if l2: s += l2.val l2 = l2.next return ListNode(s % 10, self.addTwoNumbers(l1,l2,s // 10))

递归通过调用栈隐式保存了每一层的“剩余任务”，每一层返回的是 以当前节点为头的局部链表。

我懂懂懂，刚开始代码看不懂是因为把if当成while的逻辑了

最后return的分开的写法，别忘了参数初始化，carry的初始值

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode],carry:int=0) -> Optional[ListNode]: # 递归,函数中加个carry参数，进位 # 终止条件 if l1 is None and l2 is None and carry == 0: return None s = carry if l1: s += l1.val l1 = l1.next if l2: s += l2.val l2 = l2.next digit = s % 10 # 当前位 new_carry = s // 10 next_node = self.addTwoNumbers(l1,l2,new_carry) return ListNode(digit,next_node)

写法二：原地修改

简化代码的小技巧：如果递归中发现 l 2的长度比 l 1更长，那么可以交换 l 1和 l 2，保证 l 1不是空节点，从而简化代码逻辑。

迭代（时n，空1）

无法向空节点添加值，所以，创建个dummy node，循环结束后，dummy node.next极为返回的

其实这个就是正常就这么想的。

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = cur = ListNode() # 创建哨兵节点，dummy 固定指向头，cur 移动 carry = 0 # 进位初始为 0 while l1 or l2 or carry: # 只要还有节点或进位，就继续 if l1: # 如果 l1 有节点，加上它的值 carry += l1.val l1 = l1.next if l2: # 如果 l2 有节点，加上它的值 carry += l2.val l2 = l2.next cur.next = ListNode(carry % 10) # 当前位 = 总和 % 10 carry //= 10 # 新进位 = 总和 // 10 cur = cur.next # cur 移到新节点 return dummy.next # 哨兵的下一个就是结果链表的头

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。能使用一趟扫描实现吗

烧饼节点，dummy和l和r都在这个位置。n不0且r不空时候右移动n次，这时候在lr同时移动，当r的next为none时候，l就是要删除的那个节点的前面的节点。让l的next=l的next的next，就把那个删除了

烧饼节点，好像用到了很多，一般都是:

dummy = ListNode()

dummy.next = head

前后指针

# 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 = ListNode() dummy.next = head left = right = dummy while n and right: right = right.next n -= 1 while right.next != None: left = left.next right = right.next left.next = left.next.next return dummy.next

有点easy啊（二刷我怎么有点看不懂啊~~哦看懂了）

两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

返回头节点，“不修改节点内部的值”业绩是不能用val

dummy = ListNode(next = head)。dummy=listnode，dummy.next=head

迭代：和交换节点还是哪个题有点像，但是自己脑海里总是模拟不出来。看注释

递归：递归先看终止条件。再看递归还是有点难理解，从后往前推理。

swapPairs(head) 的职责是：交换以 head 为起点的链表中的相邻节点对，并返回交换后的新头节点。

• 如果链表不足两个节点（head == None 或 head.next == None），不用交换，直接返回 head。

• 否则，取出第一对节点 node1 和 node2，以及后面链表的头 node3。

• 我们相信递归调用 swapPairs(node3) 能正确交换 node3 后面的所有节点对，并返回交换后那一段的新头。

• 然后我们把 node1 和 node2 交换：让 node2 指向 node1，node1 指向后面已经处理好的链表。

• 最后返回 node2 作为整个链表的新头。

这个解释，牛的，浅显易懂

递归的做法：

1. 你先把第一节车厢 1 和第二节车厢 2 拆下来，但暂时不动它们。

2. 你让助手去处理从第三节车厢开始的剩余车厢，让他把后面所有的车厢按规则两两交换好，并告诉你交换后那一段的头是哪一节（比如交换后第三段的新头是 4）。

3. 然后你把车厢 2 放在最前面，让 2 指向 1，再让 1 指向助手返回的那段火车的头（即 4）。

4. 最后你把 2 作为整列火车的新车头交给别人。

1. dummy = ListNode(next = head)

• 值：val 使用默认值 0。

• next 指针：直接指向 head（原链表的头节点）。

• 结果：一步到位，虚拟节点已经“挂”在了原链表前面。

2. dummy = ListNode(0)

• 值：val 设置为 0。

• next 指针：使用默认值 None（因为只传了位置参数 0，对应 val，未指定 next）。

• 结果：虚拟节点是孤立的，必须额外执行 dummy.next = head 才能连上原链表。

突然就懂迭代的写法了，很容易看懂也会写了。

迭代

# 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 = ListNode(next = head) # 什么交不修改节点内部的值？不能用到val？是的 node0 = dummy node1 = head while node1 and node1.next:#至少两个才能换 node2 = node1.next node3 = node2.next # 要交换的是node1和node2，斜交叉,从左到右 node0.next = node2 node2.next = node1 node1.next = node3 # 移动指针，准备下一对，0指向交换的前一个，1指向交换的第一个 node0 = node1 node1 = node3 return dummy.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]: # 边界 if head is None or head.next is None: return head node1 = head node2 = node1.next node3 = node2.next node1.next = self.swapPairs(node3) node2.next = node1 return node2

K个一组翻转链表🙂🙂hate you

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

看这个题目后面的笑脸，感觉不简单。。。

dummy虚拟头，pre指向等待反转的前一个节点

循环：

够k个否

截取这一段（start = pre.next，end = tail）

记录下一段起点 next_segment = end.next

断开，end.next = none

翻转这一段

接回源来的链表pre.next = new_head，new_tail.next = next_segment。

移动 pre 到下一段的前一个节点（即 new_tail）。

但是这个做法很麻烦，要断开。不断开的做法，看着很难懂，一直都很难想明白交换节点的具体过程

• dummy：虚拟头节点，它的 next 永远指向当前结果链表的头（因为头可能会变，用 dummy 简化操作）。

• p0：“当前组的前一个节点”。初始时 p0 = dummy，也就是在第一个组之前。 每次处理完一组后，p0 会移动到当前组的最后一个节点（即反转后的尾节点），成为下一组的前驱。

• cur：当前组的第一个节点（未反转前的头）。每次循环开始时，cur 指向待反转的第一个节点。

• pre：反转过程中的前驱节点。在每组反转开始时必须重置为 None。反转结束后，pre 指向该组反转后的新头。

• nxt：临时变量，用于在反转时保存 cur.next。

自己想的：得自己写reverse函数，还得断开链表啥的...

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: #长度 n = 0 cur = head p0 = dummy = ListNode(next = head) # p0 指向当前组的前一个节点 pre = None while cur: n += 1 cur = cur.next cur = head #每k，反转链表，然后重置三件套 while n>=k: n -= k pre = None # 关键：每组反转前重置 pre # 反转前k个,也就是指针方向变一下 for _ in range(k): nxt = cur.next cur.next = pre pre = cur cur = nxt # 链接反转后的子链表 nxt = p0.next# 当前组的原第一个节点（反转后变成尾节点） nxt.next = cur # 该尾节点指向下一组的头 p0.next = pre# 上一组的尾指向当前组的新头 p0 = nxt # p0 移动到当前组的尾，为下一组做准备 #返回 return dummy.next

统计节点个数-k个一组（反转链表+重置新三件，也就是反转链表）-返回

这个地方，每次pre和cur都向前移动1，并且把pre和cur反过来了

还是转不过来反转完k个之后是怎么重置的

随机链表的复制

给你一个长度为 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 作为传入参数。

看题目，其实就是复制

哈希：

如果像普通链表一样，一边遍历一边复制，那么当你复制到一个节点时，它的 random 可能指向一个还没有被复制出来的节点，你就无法正确设置 new_node.random。所以遍历两遍。

思考路径：

1. 先想朴素方法：如果边复制边设置指针，当遇到一个指针指向还未创建的节点时，无法处理。

2. 自然想到：能不能先创建所有节点，再来设置指针？

3. 那么就需要一种方式，通过原节点快速找到对应的新节点 —— 这正是哈希表（字典）的强项。

4. 于是得出：第一遍创建节点并建立映射；第二遍设置指针。

拼接拆分，空间o1：

1. 穿插复制节点：在每个原节点后面插入一个它的复制节点（只复制 val，next 和 random 暂不处理）。

2. 设置复制节点的 random：利用原节点的 random 关系，设置复制节点的 random。

3. 拆分两个链表：把原链表和复制链表分开，恢复原链表，提取复制链表。

三部曲，画个图A->A'->B->B'->C->C'-None,一目了然

哈希表，O(n)/O(n)

两次遍历原链表，第一次复制节点并存入map，第二次存入random和next。

第一次，key是节点，v也是节点，且该节点的值是源节点的值dic[cur] = Node(cur.val)

第二次，新节点的next=get原的next

能不能直接next遍历并记录cur和next，先复制出来一个正常的链表，遇到next等null不就是到头了吗，然后知道了长度，就再遍历一遍记录random的

不能，如何在新链表中找到原链表 random 指向的那个节点所对应的新节点？直接看val一样不一样？不行，可能是重复的，所以就需要映射。同时得到next和random

懂了，学到了新用法之dit[cur].next = dic.get(cur.next)。

""" # 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]': # 返回的是val，random指向的节点在正常链表中的顺序 # 哈希 if head == None: return None dic = {} # 第一遍遍历：创建所有新节点，存入哈希表 cur = head while cur: # 只复制值，next和random先不设置，都为none dic[cur] = Node(cur.val) cur = cur.next # 第二遍遍历：设置新节点的 next 和 random cur = head while cur: # 新next，对应原的next dic[cur].next = dic.get(cur.next) dic[cur].random = dic.get(cur.random) cur = cur.next cur = head return dic[cur]

拼接 + 拆分，空间复杂度更低O(1)

新旧交替，

就这一句看半天，因为一直在想右边的，cur.random.next岂不是已经不是random了？忘记了此时他的next才是我的新链表。之后要分出来的

拼接：

666看不懂问着问着把自己问明白了，但是自己想还是想不到，

拆分：

""" # 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]': # 返回的是val，random指向的节点在正常链表中的顺序 # head none if head is None: return None # 复制一份节点值在旧的后面 cur = head while cur: tmp = Node(cur.val) #复制节点 tmp.next = cur.next #复制节点的next指向源节点的next cur.next = tmp # 原的next指向复制的 cur = tmp.next # 移动cur到下一个原节点 # 复制random指针 cur = head while cur:# cur存在，cur始终指向原节点 if cur.random: #这个条件自己还写错了，有random时候 # 画个图很好理解 cur.next.random = cur.random.next # cur的random为空，直接走到下一个cur，这里的cur都是原节点 #没有random，可能是第一个没有，直接遍历下一个cur cur = cur.next.next # 缩进，就算curnext为空，cur还得往下走，比如题示的第一个节点的ranmdo就是null # 拆分 cur = res = head.next # cur指向新表，这里res是新头，要返回 pre = head # pre始终指向就表节点 while cur.next: # cur指向新的表的节点，next不存在就是到最后了 pre.next = pre.next.next #原 cur.next = cur.next.next #新 pre = pre.next # 移动 cur = cur.next # 移动 # 返回 return res

排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表

都是归并

递归：

递归函数 sortList(head) 的职责就是：输入一个链表的头节点，返回排序后的链表头。 你相信它能处理好规模更小的子问题，所以直接调用 self.sortList(head) 和 self.sortList(mid)，它们就会返回已经排好序的左半部分和右半部分。

还是那个说法，相信这个函数

迭代

归并排序，递归（时间nlogn,空间logn）

边界，中点，分割，递归，合并，返回。

写时候：调用递归忘记self了；合并时候忘记用res记录一下了，因为后面h会变，要能返回去需要记录一下；合并时候if条件只是更新了h next，忘记把h更新一下了，这样结果就只有最后一个值最大的节点了。

# 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]: # 递归 # 边界 if head is None or head.next is None: return head # 中点 slow = head fast = head.next # 偶数时候slow位置也正确 while fast and fast.next: slow, fast = slow.next, fast.next.next # 分割 mid, slow.next = slow.next, None # 递归 left, right = self.sortList(head), self.sortList(mid) # 合并 h = res = ListNode(0) #值为0，单独的节点 while left and right: if left.val < right.val: h.next = left left = left.next else: h.next = right right = right.next h = h.next h.next = left if left else right # 返回 return res.next

归并排序，迭代(空间变成1)🙂

边界，链表长度，dummy，归并逻辑，合并函数

归并逻辑：子链表长度step从1开始，step<<=1

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

最小堆

• 把这 K 个链表的当前头节点都放进一个最小堆里。

• 每次从堆中弹出最小的节点，接到结果链表的末尾。

• 如果这个被弹出的节点还有下一个节点，就把它的下一个节点放入堆中。（也就是，某个链表的内容往下迭代呗）

• 重复直到堆为空。

关于ListNode.__lt__ = lambda a, b: a.val < b.val

在 Python 的堆（heapq）中，元素需要能够比较大小。默认情况下，两个 ListNode 对象无法比较，因为不知道比较它们的什么属性。 这行代码给 ListNode 类添加了 lt（less than）方法，告诉 Python：比较两个节点时，比较它们的 val 属性。这样堆就知道如何对节点排序了。

还有就是堆的用法，如heapify，heappop，heappush

分治

先顶一个合并两个的

然后得到一共m个链表，递归得到左侧一半的merge，右侧一般的merge

最后合并这两个即可

• 如果 lists 为空，返回 None。

• 如果 lists 只有一个链表，直接返回它。

• 否则，将 lists 分成左右两半，递归地合并左半部分，递归地合并右半部分，得到两个有序链表。

• 最后用 mergeTwoLists（合并两个有序链表的函数）将这两个有序链表合并成一个，并返回。

这就像归并排序：先分，再合，只是这里的“元素”是链表。

最小堆

• 时间复杂度：O(Llogm)，其中 m 为 lists 的长度，L 为所有链表的长度之和。

• 空间复杂度：O(m)。堆中至多有 m 个元素。

把头入堆，然后弹出来最小的

ListNode.__lt__ = lambda a, b: a.val < b.val # 让堆可以比较节点大

这一句不会写。就是让堆能比较节点大小

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ListNode.__lt__ = lambda a, b: a.val < b.val # 让堆可以比较节点大 class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: # 最小堆 # 哨兵 cur = dummy = ListNode() # 每个有序链表的第一个进堆 h = [head for head in lists if head] # 最小堆 heapify(h) # 依次弹出堆头，也就是min。同时如果这个头有next，next进堆 # 也就是一个链表里，最小的弹出去的，第二小的就要进去 while h: node = heappop(h) if node.next: heappush(h,node.next) cur.next = node cur = cur.next return dummy.next

分治（递归，迭代）

递归像是在后序遍历一棵平衡二叉树。由于平衡树的高度是 O(logm)，所以每个链表节点只会出现在 O(logm) 次合并中！这样就做到了更快的 O(Llogm) 时间。空间O(logm)

递归：时间Llogm,空间logm

迭代：时间Llogm,空间1

递归：

合并两个链表，合并k个，边界（长度为0，1），递归左边部分列表，右半部分列表，返回合并两个的

写时候，报错，因为m==1时候返回的是lists[0]，写成了List[0]，报错在合并两个的函数中，val。因为此时List啥也不是，也就没有val变量

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # 让堆可以比较节点大 class Solution: def mergeTwoLists(self, list1 : Optional[ListNode], list2 : Optional[ListNode]) -> Optional[ListNode]: cur = dummy = ListNode() # 连接链表 while list1 and list2: if list1.val < list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next cur.next = list1 if list1 else list2 return dummy.next def mergeKLists(self, lists:List[Optional[ListNode]]) -> Optional[ListNode]: m = len(lists) if m == 0: return None if m == 1: return lists[0] left = self.mergeKLists(lists[:m//2]) right = self.mergeKLists(lists[m//2:]) return self.mergeTwoLists(left, right)

LRU缓存🙂

典型使用orderdict的题

题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

OrderDict，

# OrderedDict = dict + 双向链表

在 Python 3.7+ 中，普通的 dict 也保证了插入顺序（这是语言规范），但 OrderedDict 依然有它的价值：

1. 额外的顺序操作方法

   1. move_to_end(key, last=True)：将某个键移到末尾（或开头）

   2. popitem(last=True)：弹出末尾（或开头）的键值对 普通字典没有这些方法。

2. 明确表达意图 当你需要依赖顺序时，用 OrderedDict 能让代码更清晰。

3. 一些旧代码或需要严格顺序比较的场景 虽然普通 dict 也保持顺序，但 OrderedDict 在比较相等性时会考虑顺序，而普通 dict 只比较键值对。

实现

class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = OrderedDict() #这个就是双向链表+dict def get(self, key: int) -> int: if key not in self.cache: return -1 # 没有这个书，返回 # 有的话，发感到最上面 self.cache.move_to_end(key, last = False) return self.cache[key] def put(self, key: int, value: int) -> None: self.cache[key] = value # 添加书，也放最上面 self.cache.move_to_end(key, last = False) if len(self.cache) > self.capacity: self.cache.popitem() # 书超了去掉最后一个 # 双向链表 # 如何找到key？哈希 # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)

链表小结

写链表的题，dummy head很有用

二叉树

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

递归，O(n),O(h)

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # 中序 左中右 def dfs(node: Optional[TreeNode]) -> None: if node is None: return dfs(node.left) ans.append(node.val) dfs(node.right) ans = [] dfs(root) return ans

O(1)空间复杂度，Morris遍历

叶子结点的右儿子一定空---建立线索---叶子结点的右儿子指向后继节点---也就是找到一个结点的前驱节点

找前驱：

二叉树最大深度

自底向上

On,on,递归最差就是一条

递归调用深入到底层，然后逐层返回时 +1

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right 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

自顶向下

nonlocal关键字：dfs 函数内声明 nonlocal ans，就是明确地告诉 Python：“这里的 ans 不是一个局部变量，请到外层函数（maxDepth）的作用域里去寻找这个变量

ans始终记录当前最大的深度：左子树遍历完再右子树

函数参数什么时候需要self：调用用到self，修改

全局作用域，静态装饰器，方法内部的局部函数均不需

# 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 maxDepth(self, root: Optional[TreeNode]) -> int: ans = 0 def dfs(node: Optional[TreeNode], depth: int) -> None: if node is None: return depth += 1 nonlocal ans ans = max(depth, ans) dfs(node.left,depth) dfs(node.right,depth) dfs(root,0) return ans

翻转二叉树

原问题-子问题-递归-找边界root为none

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: # 广度优先，对同一层的反转 if root is None: return None # root.left, root.right = root.right, root.left self.invertTree(root.left) self.invertTree(root.right) root.left, root.right = root.right, root.left return root

对称二叉树

整个反转后和原来一样

递归，底向上

怎么判断等？

p.val==q.val && is_same(p.left,q.left) && is_Same(p.right,q.right)递归is_same

边界node=none

改为镜像判断的，值相同，p左q右，p右q左。

# 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 is_Same(self,p:Optional[TreeNode],q: Optional[TreeNode]) -> bool: if p is None or q is None: return p is q return p.val == q.val and self.is_Same(p.left,q.right) and self.is_Same(p.right,q.left) def isSymmetric(self, root: Optional[TreeNode]) -> bool: # if not root: # return True return self.is_Same(root.left,root.right)

Is same需要self，不然后面issymmetric无法识别issame时哪个issame

迭代

队列实现，每次提取两个节点判断比较值

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

定义了一个求树高的函数，就是纯粹的求树高的

左边最高的高度+右边最高的高度

递归，none

怎么可能不经过根节点？

递归，左右最高子树，记录一个max，同时需要返回给上一层本层的max

层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

Python 中使用 collections 中的双端队列 deque() ，其 popleft() 方法可达到 O(1) 时间复杂度；列表 list 的 pop(0) 方法时间复杂度为 O(N)

根先入队列，记录长度，然后将根的左右入队，弹出根；

记录现在的队列长度，弹出一个，入队这个节点的左右孩子；直到该长度弹完全

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: # bfs，借助队列先入先出 if not root: return [] res, queue = [], collections.deque() # 忘记根节点入库了， queue.append(root) while queue: # 队列不空 tmp = [] #记录根的值 # 遍历对立 for _ in range(len(queue)): node = queue.popleft() tmp.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(tmp) return res

有序数组-二叉搜索树

函数自己掉自己,self

平衡二叉搜索树，递归，中间为根，左右平衡，数组长度为0返回空；

中间为根节点，偶数默认右边；

# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: # 递归，中间的为根，左右平衡，边界数组长度为0，返回空 # 偶数中间默认右边 if not nums: return None m = len(nums) // 2 left = self.sortedArrayToBST(nums[:m]) right = self.sortedArrayToBST(nums[m+1:]) return TreeNode(nums[m],left,right)

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 严格小于 当前节点的数。

• 节点的右子树只包含 严格大于 当前节点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

二叉所搜，左《中《右

每个子树都返回该子树中的最小值和最大值，然后利用这些值来检查当前节点是否满足 BST 的条件。

要判断一棵树是不是 BST，我们可以递归地获取：

• 左子树的最小值 l_min 和最大值 l_max

• 右子树的最小值 r_min 和最大值 r_max

然后检查：

l_max < x < r_min

并且左子树本身是 BST，右子树本身也是 BST。

空节点返回 (inf, -inf) —— 注意顺序是 (最小值, 最大值)。

空子树的最小值记为 inf，最大值记为 -inf。这样当父节点与空子树比较时：

• l_max（左子树的最大值）为 -inf，肯定小于当前节点值。

• r_min（右子树的最小值）为 inf，肯定大于当前节点值。

• f(root) 返回根节点子树的 (min, max)。

• 如果整棵树是 BST，那么最大值应该是树中实际的最大值，不会是 inf（因为 inf 只出现在非法情况下或空节点）。

• 如果树不是 BST，某个节点会返回 (-inf, inf)，这个 inf 会一直向上传递到根，所以根返回的最大值就是 inf。

• 因此 f(root)[1] != inf 为真时表示合法，否则非法。

# 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: pre = -inf def isValidBST(self, root: Optional[TreeNode]) -> bool: def f(node): if node is None: return inf,-inf #这里，难懂 l_min, l_max = f(node.left) r_min, r_max = f(node.right) x = node.val if x <= l_max or x >= r_min: return -inf,inf # 标记为非法 BST return min(l_min,x),max(r_max,x) return f(root)[1] != inf

前序遍历，on

在函数上额外传入两个参数，根到当前节点的min，max；当前值必须在此之间。原理为：

往左递归，更新右。均on

#def check(node,left,right) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isValidBST(self, root: Optional[TreeNode], left = -inf, right = inf) -> bool: if root is None: return True x = root.val return left < x < right and self.isValidBST(root.left, left, x) and self.isValidBST(root.right, x, right)

中序遍历，on

左中右->严格递增数组；如何判断言给递增，比较相邻，左，当前大于上一个，记录当前，下一个和那个比；

初始化一个-inf

根空，true

左不行，false

当前小于前一个，false

记录pre为当前

递归右

还是有点模糊的

# 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: pre = -inf def isValidBST(self, root: Optional[TreeNode]) -> bool: if root is None: return True if not self.isValidBST(root.left): return False if root.val <= self.pre: #没加等是错的 return False self.pre = root.val return self.isValidBST(root.right)

后序遍历，on

范围上传

最小最大都要返回，而不能只返回左子树的min

递归函数：

node空，返回无穷区间

递归左，拿到min，max

递归右，拿到

节点值x

如果x小于l的max，或大于r的min，返回无穷区间

最后返回min的左minmx，maxrmax，x

最终递归函数返回的不是无穷大则是f(root)[1] != inf

# 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: pre = -inf def isValidBST(self, root: Optional[TreeNode]) -> bool: def f(node): if node is None: return inf,-inf #这里，难懂 l_min, l_max = f(node.left) r_min, r_max = f(node.right) x = node.val if x <= l_max or x >= r_min: return -inf,inf return min(l_min,x),max(r_max,x) return f(root)[1] != inf

二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

中序遍历,on,oh

ans记录，定义dfs，返回none：

k,ans为nonlocal

Node 空或k<=0，返回

dfs左

k-1

k=0的话，ans取值

dfs右

主函数中dfs root

返回ans

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: ans = 0 def dfs(node:Optional[TreeNode]) -> None: nonlocal k,ans if node is None or k <= 0 : return dfs(node.left) k -= 1 if k == 0: ans = node.val dfs(node.right) dfs(root) return ans

不记录答案+提前返回

二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

给的输入root是层序遍历

bfs

dfs：

优先遍历右子树，这样每一层第一个被访问到的节点就是最右边的节点。

关键：len(ans) 表示已经记录了多少层。当 len(ans) == depth 时，说明这一层还没有节点被加入答案，而当前节点就是这一层最先被访问到的节点。由于我们先递归右子树，再递归左子树，所以每一层最先访问到的节点一定是该层最右边的节点。

BFS,on,on

每层最后一个节点值保存

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]: if root is None: return [] ans = [] cur = [root] #当前在根 while cur: ans.append(cur[-1].val) # 把这一层最右的加入 nxt = [] # 临时记录下一层的东西 for node in cur: if node.left: nxt.append(node.left) # node的下一层进nxt if node.right: nxt.append(node.right) # node的下一层进nxt cur = nxt # 进来完了， return ans

BFS

借助队列先入先出

DFS,on,oh

深度优先，先右子树再左子树，某个深度首次到达，对应节点就在右视图

递归同时记录递归深度，深度等于答案长度就记录

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]: ans = [] def f(node, depth): if node is None: return if len(ans) == depth:# 当前深度还没有记录过节点 ans.append(node.val)# 那么这个节点就是该层最右边的（因为优先遍历右子树） # f(node.left, depth + 1) f(node.right, depth + 1) #注意先后顺序啊，先右 f(node.left, depth + 1) f(root, 0) return ans

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

头插法注意head的定义，head定义在函数内部时候，每次调用 flatten 都会创建新的局部变量 head，初始为 None，但是我需要的head是右下已经遍历好的头，所以不能初始化在函数内

先序，中左右。输入还是层序的

头插法,on,on

右子树 - 左子树 - 根的顺序 DFS 这棵树。DFS 的同时，记录当前链表的头节点为 head。一开始 head 是空节点。

# 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: head = None def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ if root is None: return self.flatten(root.right) self.flatten(root.left) root.left = None root.right = self.head self.head = root

分治,on,on

只在DFS中解决

左边一个链，右边一个链，根root。把左尾连右，再根连左，也就是dfs需要返回链表的尾节点

疑问：为什么返回的是right_tail or left_tail or root？这样的话，反的是尾节点，但是输出不应该是从头开始嘛

答：虽然返回的是尾节点，但是flatten(root)，使用root作为链表头，无需关心返回值，原地修改且无返回值

in-place解法,on,o1

非递归，不使用辅助空间及全局变量，前面的递归解法实际上也使用了额外的空间，因为递归需要占用额外空间。下面的解法无需申请栈，也不用全局变量，是真正的 In-Place 解法。

具体思路：

当前节点不空时候，且左树不空，右子树搬到左子树的右下

左子树换到右子树，左置空

下一个节点，同样的操作

不然就是左空，直接root = root.right

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ while(root != None): if root.left != None: # 左边不空才操作 most_right = root.left # 左子树先存一下 while most_right.right != None: most_right = most_right.right # 找到左子树的右下 most_right.right = root.right # 右子树放在最左树下 root.right = root.left # 左树放右数 root.left = None # 左空 root = root.right # 左空时候，直接向下 return

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

递归

注意返回的是None如果中序遍历不存在的话，而不是[]

not看空，也就是看[]

[]并不是none

很熟悉。

递归on2,on2

前序确定根，中序确定左右子树

这里注意一个：

• if not preorder:：检查 preorder 是否为“空”。对于列表，空列表 [] 会被视为 False，因此条件成立。

• if preorder is None:：检查 preorder 是否是 None 对象。空列表 [] 并不是 None，所以条件不成立。

也就是not判断空，None！=[],not值

# 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: #if preorder is None: #if not preorder:：检查 preorder 是否为“空”。对于列表，空列表 [] 会被视为 False，因此条件成立。 #if preorder is None:：检查 preorder 是否是 None 对象。空列表 [] 并不是 None，所以条件不成立。 return None left_size = inorder.index(preorder[0]) left = self.buildTree(preorder[1:1 + left_size], inorder[:left_size]) right = self.buildTree(preorder[1 + left_size:],inorder[1 + left_size:]) return TreeNode(preorder[0],left,right)

优化

哈希表预处理inorder的下标，这样o1查找到preorder[0]在inorder的位置，从而o1知道左子树的大小；递归参数改成子数组下标区间的左右端点，避免复制数组

路经总和Ⅲ

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

枚举终点，看多少个起点

DFS 遍历这棵树，遍历到节点 node 时，假设 node 是路径的终点，那么有多少个起点，满足起点到终点 node 的路径总和恰好等于 targetSum？

On,On

# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: # key根到node值和 # v 这个和出现的次数 cnt = defaultdict(int) cnt[0] = 1 ans = 0 # s,根到node的父，不包括node的和 def dfs(node: Optional[TreeNode], s:int) -> None: if node is None: return nonlocal ans s += node.val # node作为终点，统计起点个数 ans += cnt[s - targetSum] cnt[s] += 1 dfs(node.left, s) dfs(node.right, s) cnt[s] -= 1 # 恢复 # why恢复？因为只能上到下的路径，这条路径遍历完之后遍历吓一跳。需要恢复 dfs(root, 0) return ans

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

递归函数的功能

递归函数 lowestCommonAncestor 到底返回什么？ 它返回的不是“p 和 q 的公共祖先”，而是更通用的：“在以当前节点为根的子树中，如果包含 p 或 q，则返回 p 或 q 本身（或它们的 LCA）；否则返回 None”。具体规则：

• 如果当前节点是 None，返回 None。

• 如果当前节点等于 p 或 q，返回当前节点（因为自身就是目标之一）。

• 否则，递归去左子树和右子树查找，得到 left 和 right。

  • 如果 left 和 right 都非空，说明 p 和 q 分别位于左右两侧，当前节点就是 LCA，返回当前节点。

  • 如果一侧为空，另一侧非空，则返回非空的那一侧（表示该侧包含了 p 或 q，但另一侧没有）。

  • 如果两侧都为空，返回 None。

因此，当 left 和 right 都为空时，说明当前节点的子树中不包含 p 或 q，自然返回 None。这个 None 会向上传递，直到某个祖先节点发现一侧有值、另一侧也有值，才返回该祖先。

接下来需要判断：

1. 如果 left 为 None 说明左子树中既没有 p 也没有 q（或它们的公共祖先不在左子树）。那么 p 和 q 必然都在右子树中（或者其中一个在右子树，另一个等于当前 root？但注意递归前已经处理了 root == p or root == q 的情况，所以当前 root 一定不是 p 或 q）。因此整个树中的 LCA 一定是右子树返回的结果，即 right。 → 直接 return right

2. 如果 right 为 None 对称地，说明右子树中无目标，LCA 在左子树中，返回 left。

3. 如果 left 和 right 都不为 None 说明 p 和 q 分别位于当前节点的左子树和右子树中（一边一个）。那么当前节点 root 就是它们的最低公共祖先。 → return root

所有val都不同

这个题的解答的图，详细的说明了递归的运行

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solutions/240096/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu

# 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': # 情况 # p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）； # p=root ，且 q 在 root 的左或右子树中； # q=root ，且 p 在 root 的左或右子树中； if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p , q) right = self.lowestCommonAncestor(root.right,p , q) if not left : return right if not right: return left return root

二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

dfs 函数返回的是：以当前节点为起点（必须包含当前节点）向下的最大单侧路径和，且如果这个和小于 0，则返回 0（表示不选择该路径）。具体来说：

• 对于当前节点 node，它先递归计算左子树的最大单侧路径和 l_val 和右子树的 r_val（注意如果子树返回 0 意味着不走那边）。

• 然后更新全局答案 ans：l_val + r_val + node.val 表示以当前节点为最高点的路径（可以左右都走）的总和。

• 最后返回 max(l_val, r_val) + node.val 与 0 的较大值。这个值就是当前节点能向上级提供的最大单侧路径和（因为上级只能选择一条分支继续延伸，所以取左右中较大的一条加上自身，如果这个值小于 0，则对上级没有贡献，直接返回 0）。

因此，dfs 的返回值是：当前节点向下（单边）的最大非负贡献值。

第一时间想到了，哈希那个，路经总和有点像

On，On

# 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 maxPathSum(self, root: Optional[TreeNode]) -> int: ans = -inf def dfs(node: Optional[TreeNode]) -> int: if node is None: return 0 # 无节点，和0 l_val = dfs(node.left) r_val = dfs(node.right) nonlocal ans ans = max(ans, l_val + r_val + node.val) #拼成路径 return max(max(l_val,r_val)+node.val,0) # 当前子树的最大链和 dfs(root) return ans

回溯

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

写法1，交换：

• 递归函数 dfs(x) 表示：已经固定了前 x 个位置的数字（索引 0..x-1），现在要处理第 x 个位置。

• 我们需要把 nums[x] 与它后面的每个元素（包括自己）交换，这样每个元素都有机会出现在 x 位置。

• 交换后，递归调用 dfs(x+1) 处理下一个位置。

• 递归返回后，必须把交换过的元素换回来，恢复原状，以便进行下一次交换。

• why： res.append(list(nums)) ，nums 是一个列表，在递归过程中会被不断交换修改。如果不加 list()，直接 res.append(nums)，那么 res 中存储的将是同一个列表对象的引用。后续回溯对 nums 的修改会直接影响到已经存入 res 中的排列；list(nums) 实现浅拷贝，防止结果被后续修改覆盖。

写法2：

• 枚举所有长度为 n 的排列，每个位置 i 可以放 nums 中尚未使用过的任意一个数字。

• dfs(i) 表示：已经确定了前 i 个位置（索引 0..i-1）的数字，现在要决定第 i 个位置放什么。

• 当 i == n 时，所有位置都已填满，得到一个完整排列，将其加入结果集。

• 在 dfs(i) 中，遍历所有 nums 中的数字，如果当前数字 nums[j] 没有被使用（on_path[j] == False），则：

  • 将 nums[j] 放入 path[i]。

  • 标记 on_path[j] = True，表示该数字已被使用。

  • 递归调用 dfs(i+1) 去填下一个位置。

  • 递归返回后，撤销标记 on_path[j] = False，以便后续循环可以使用该数字。

写法1：

这个写法，不好理解，主要就是swip的作用，固定了某个字符在某个位置

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: def dfs(x): if x == len(nums) - 1: res.append(list(nums)) # 终止条件满足，写入答案 return # 返回 for i in range(x, len(nums)): #横向遍历，里面递归纵向 nums[i], nums[x] = nums[x], nums[i] # 处理节点,nums[i]固定在第x位 dfs(x + 1) #递归 nums[i],nums[x] = nums[x], nums[i] #恢复 res = [] dfs(0) return res

写法2：

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: n =len(nums) path = [0] * n on_path = [False] * n res =[] # 枚举path[i]填nums的哪个数 def dfs(i:int) -> None: if i == n: res.append(path[:]) # 终止条件满足，写入答案 return # 返回 for j, on in enumerate(on_path): #横向遍历，里面递归纵向 if not on: #on,false path[i] = nums[j] on_path[j] = True dfs(i + 1) #递归 on_path[j] = False #恢复 #这里path不用回复，应为长度固定了，直接覆盖 dfs(0) return res

子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

组合问题

选不选，dfs(i)就是nums[i]是否选择。遍历i-n

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: n = len(nums) res = [] path =[] def dfs(i:int) -> None:#nums[i]是否选择 if i == n:#遍历完了，结束，写入 res.append(path[:]) return # 不选nums[i] dfs(i + 1) # 直接这样，path没变化，不需要回复 # 选nums[i] path.append(nums[i]) dfs(i + 1) path.pop() dfs(0) return res

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

弄了个mapping，用来把digits中的数字转为字符串

For c in mapping[int(didits[i])]

path[i] = c

这里和上面的不同就是，这里是字符，所以path = ['']*n

这里不用恢复，因为覆盖赋值不需要恢复，因为新值会替换旧值；而增加/删除元素需要恢复，以保持状态一致。

MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" #why，两个空,0,1不对应数字 class Solution: def letterCombinations(self, digits: str) -> List[str]: n = len(digits) if n == 0: return [] res = [] # 字符 path = [''] * n def dfs(i:int) -> None: if i == n: res.append(''.join(path)) return for c in MAPPING[int(digits[i])]: path[i] = c dfs(i + 1) dfs(0) return res

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

# 第一个参数还是i，可以重复选 dfs(i,left-candidates[i])

和子集那个题的一点不同

和子集那一题差不多，写法选择：选与不选nums[i]。不同的就是多了一个和需要满足条件，于是dfs参数要多一个left。

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: #找出全部的组合情况，判断组合和满足，写入res。 #应该可剪枝 #一个数可以选多次，和子集的不同，dfs需要参数i,left n = len(candidates) res = [] path = [] def dfs(i : int,left : int) -> None: if left == 0: res.append(path[:]) return if i == len(candidates) or left < 0: return # 不选i dfs(i + 1, left) # 选i path.append(candidates[i]) # 第一个参数还是i，可以重复选 dfs(i,left-candidates[i]) #回复 path.pop() dfs(0,target) return res

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

字符初始化path=['']*2*n

乍一看看不懂open是什么参数

open 表示当前已经放置的左括号数量。i 表示当前正在填充的位置（从 0 开始）。

回溯过程中，需要保证生成的括号序列始终是合法前缀（即任何时候右括号数 ≤ 左括号数）。两个分支：

1. 如果 open < n（左括号还没放完），就可以在 path[i] 放一个 (，然后递归，同时 open + 1。

2. 如果 i - open < open（已放的右括号数 < 左括号数），就可以放一个 )，递归后 open 不变。

当 i == 2n 时，得到一个完整合法组合，加入答案。

这个算法不需要显式恢复 path，因为每次循环直接覆盖 path[i] 的值。

选和不选，枚举选哪个两种思路。都可以想一下比较一下。枚举看不懂

class Solution: def generateParenthesis(self, n: int) -> List[str]: ans =[] path = [''] * (2 * n) def dfs(i, open) -> None: if i == 2 * n: ans.append(''.join(path)) return if open < n: path[i] = '(' dfs(i + 1, open + 1) if i - open < open : path[i] = ')' dfs(i + 1,open) dfs(0,0) return ans

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

不明白 board[i][j] = word[k]这里是为什么

• 标记：board[i][j] = '' 表示当前格子正在被使用（避免重复）。

• 恢复：board[i][j] = word[k] 表示释放格子，恢复原状。

• 这是回溯算法的标准模式：修改状态 → 递归 → 恢复状态。

深搜加剪枝：dfs函数，边界，访问记录，递归四个方向，恢复，返回。主函数，遍历，满足dfs则true

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i,j,k)->bool: # 边界false if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k] : return False # 边界true if k == len(word) - 1: return True # 访问逻辑，递归，回复 board[i][j] = '' res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1) board[i][j] = word[k] # 返回 return res # 遍历 for i in range(len(board)): for j in range(len(board[0])): if dfs(i,j,0):return True # dfs返回true，不然就false return False

分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

这个枚举字串结束的位置反而好理解。选与不选难理解。

判断是否回文串，t == t[::-1]则是

逗号选不选这个做法不理解：

我们遍历字符串的索引 i，同时维护一个“当前子串的起始位置” start。对于每个位置 i，有两种选择：

1. 不在 i 后面切分（即把 s[i] 合并到当前子串中）：这相当于延迟分割，继续向后移动 i，但 start 不变。

2. 在 i 后面切分（即让当前子串结束于 i）：先检查子串 s[start:i+1] 是否为回文。如果是，则将其加入路径，然后从 i+1 开始新的子串（start = i+1），继续递归。

当 i 到达字符串末尾（i == n）时，表示已经处理完所有字符，当前路径 path 就是一组有效的分割方案，加入答案。

逗号选不选

不理解为什么是dfsi+1,i+1

# 分,[start, i]

t = s[start:i+1]

if t == t[::-1]:

path.append(t)

dfs(i+1,i+1)

class Solution: def partition(self, s: str) -> List[List[str]]: # 选或不选 n = len(s) ans = [] path = [] def dfs(i:int, start:int) -> None: if i == n: ans.append(path[:]) return # 不分 if i < n-1: dfs(i + 1,start) # 分,[start, i] t = s[start:i+1] if t == t[::-1]: path.append(t) dfs(i+1,i+1) path.pop() dfs(0,0) return ans

枚举字串结束位置

就像是，切割分段，看看这一段是不是回文串

class Solution: def partition(self, s: str) -> List[List[str]]: # 选或不选 n = len(s) ans = [] path = [] def dfs(i:int) -> None: if i == n: ans.append(path[:]) return for j in range(i,n): t = s[i:j+1] if t == t[::-1]: path.append(t) dfs(j+1) path.pop() dfs(0) return ans

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

• col：长度为 n 的列表，col[r] 表示第 r 行皇后所在的列号（0~n-1）。当所有行都放好时，就根据 col 构造棋盘。

• s：一个集合，里面存放当前还没有被占用的列号。这样在放置下一行时，只需从 s 中选列，避免同一列出现两个皇后。

• dfs(r, s)：递归函数，表示正在放第 r 行，并且当前可用的列是集合 s。

过程：

1. 如果 r == n，说明 0~n-1 行都已成功放置皇后，将当前解加入答案。

2. 否则，遍历 s 中的每一列 c（即所有还没被占用的列）：

   1. 检查对角线冲突：对于之前已经放好的每一行 R（0 <= R < r），该行皇后在 col[R]。要检查 (r, c) 是否与 (R, col[R]) 在同一对角线上。 对角线条件：

      • 主对角线（左上到右下）：r - c == R - col[R] 即 r - c == R - col[R]（行减列相等）

      • 副对角线（右上到左下）：r + c == R + col[R]（行加列相等） 因此，如果 r+c == R+col[R] 或 r-c == R-col[R]，则冲突。

   2. 如果所有已放置的行都不冲突，那么可以放置皇后：

      • col[r] = c

      • 递归调用 dfs(r+1, s - {c})，即下一行，可用的列去掉 c。

   3. 如果冲突，则尝试下一列。

3. 递归返回后不需要显式恢复 col[r]，因为下一次循环 c 会覆盖。

伪代码思路

Def dfs(checkborad,n,row):

If row==n:

ans.append(checkboard)

For i in rang(n) :

If hefa(row,i,checkboard,n):

board[row][i]='Q'

dfs(checkboard,n,row+1)

checkboard[row][i]='.'

class Solution: def solveNQueens(self, n: int) -> List[List[str]]: ans = [] col = [0] * n def dfs(r,s): if r == n : ans.append(['.'*c + 'Q' + '.'*(n-1-c) for c in col]) return for c in s: if all(r+c != R+col[R] and r-c != R-col[R] for R in range(r)): col[r] = c dfs(r+1,s-{c}) dfs(0,set(range(n))) return ans

行全排列

R当前行，s剩余列

传统写法

• 棋盘表示：board 是一个二维字符列表，方便修改和恢复。

• 列标记：cols 直接标记列是否被占用。

• 主对角线标记：在同一个主对角线上，r - c 为定值。范围是从 -(n-1) 到 (n-1)，加上偏移量 n-1 后变为 0 到 2n-2，因此 diag1 的长度至少为 2n-1。

• 副对角线标记：在同一个副对角线上，r + c 为定值，范围 0 到 2n-2，直接作为索引。

• 回溯结构：标准的“尝试 → 递归 → 撤销”模式，保证每个分支尝试所有可能性。

def solveNQueens(self, n): # 结果列表，用于存储所有合法的棋盘布局 res = [] # 创建一个 n x n 的棋盘，初始填充为 '.'（表示空位） # 例如 n=4: board = [['.', '.', '.', '.'], ['.', '.', '.', '.'], ...] # 每行都是n个.，共n行 board = [['.'] * n for _ in range(n)] # 列占用标记：cols[c] = True 表示第 c 列已经有皇后 cols = [False] * n # 主对角线（左上到右下）占用标记 # 主对角线上满足：行索引 - 列索引 = 常数，范围是 -(n-1) 到 (n-1) # 为了作为数组索引，加上偏移量 (n-1)，映射到 0 到 2n-2 # diag1 的长度设为 2*n-1 即可，这里用 2*n 多一个也无影响 diag1 = [False] * (2 * n - 1) # 副对角线（右上到左下）占用标记 # 副对角线上满足：行索引 + 列索引 = 常数，范围是 0 到 2n-2 diag2 = [False] * (2 * n - 1) # 回溯函数，参数 r 表示当前正在处理的行索引（从 0 开始） def backtrack(r): # 如果已经成功放置了 n 行（即 r == n），说明找到了一个完整解 if r == n: # 将 board 的每一行从字符列表转换成字符串，并存入结果 # 例如 [['Q','.','.','.'], ...] -> ['Q...', '....', ...] res.append([''.join(row) for row in board]) return # 尝试在当前行的每一列放置皇后 for c in range(n): # 检查当前位置 (r, c) 是否与已放置的皇后冲突： # 1. 列不冲突：cols[c] == False # 2. 主对角线不冲突：diag1[r - c + n - 1] == False # 3. 副对角线不冲突：diag2[r + c] == False if not cols[c] and not diag1[r - c + n - 1] and not diag2[r + c]: # 放置皇后 board[r][c] = 'Q' # 标记列、主对角线、副对角线为已占用 cols[c] = True diag1[r - c + n - 1] = True diag2[r + c] = True # 递归处理下一行 backtrack(r + 1) # 回溯：撤销当前位置的皇后，清空占用标记（恢复现场） board[r][c] = '.' cols[c] = False diag1[r - c + n - 1] = False diag2[r + c] = False # 从第 0 行开始求解 backtrack(0) return res

二分查找

二分和双指针？区别？

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

最典型的二分

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

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。

• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

二分

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: #先比较边界的，看看范围 # 暴力on方应该也行？ # 不会处理二维的数组 # m,n = len(matrix),len(matrix[0]) # a[i] = matrix[i//n][i%n] # 闭区间 m, n = len(matrix),len(matrix[0]) low, high = 0, m * n - 1 while low <= high: mid = (low + high) // 2 x = matrix[mid // n][mid % n] if x == target: return True if x < target : low = mid + 1 else: high = mid - 1 return False

排除

灵神的图，很清晰

看右上角满足，true

右上角小于target，i+1，target肯定在下面

右上角大于target，j-1，taget肯定在左边

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: if matrix[i][j] == target: return True if matrix[i][j] < target : i += 1 else: j -= 1 return False

在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

这个，就算是中间等了，还得找左右分别得到一个数，

二分+线性扫描On

自己写了，边界判断要注意，while l > 0 and nums[l - 1] == target:是nums[l-1]；而且找到了要在大while中返回。

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

二分Ologn

分别二分查找左右，也就是两个二分。。写的时候发现，要关注目标，比如find left，只是为了找left，所以满足《=时候，r往左移。

• 当 nums[mid] >= target 时，说明 target 在左半边（包括 mid），所以我们向左收缩右边界 r = mid - 1。 同时，如果 nums[mid] == target，就把 mid 记录为候选答案（因为越往左可能还有更左的 target，所以记录后还要继续向左找）。

• 当 nums[mid] < target 时，说明 target 在右半边，向右收缩左边界 l = mid + 1。

• 循环结束后，res 保存的就是最左边的 target 索引（如果存在）；否则为 -1。

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: def find_left(): l, r = 0, len(nums) - 1 res = -1 while l <= r: mid = (l + r) // 2 if nums[mid] >= target: if nums[mid] == target: res = mid r = mid - 1 else: l = mid + 1 return res def find_right(): l, r = 0, len(nums) - 1 res = -1 while l <= r: mid = (l + r) // 2 if nums[mid] <= target: if nums[mid] == target: res = mid l = mid + 1 else: r = mid - 1 return res return [find_left(),find_right()]

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

想二分，得先恢复数组，但k不知，遍历到不是递增的第一个数？又on了

一次二分

发现自己习惯闭区间，然后看解法左闭右开的，很不一样，闭区间更新时候lr要有+-1。开区间没。

还是二分，就多个中间结果

class Solution: def search(self, nums: List[int], target: int) -> int: # if not nums: # return -1 l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 if nums[mid] == target: return mid # 判断左半部分是否有序 if nums[l] <= nums[mid]: # 左半有序，检查 target 是否在左半范围内 if nums[l] <= target < nums[mid]: r = mid - 1 else: l = mid + 1 else: # 右半有序，检查 target 是否在右半范围内 if nums[mid] < target <= nums[r]: l = mid + 1 else: r = mid - 1 return -1

寻找旋转排序数组中的最小值

找第一个满足条件的位置

的二分

思考：

旋转数组 = 两段有序数组

左段整体比较大

右段整体比较小

最小值 = 右段的第一个元素

转为二分：我要找第一个落入右段的位置。

和最后一个数比：比它大，说明在左高区，答案在右边；比它小或等于它，说明在右低区，答案可能是自己，往左收。

class Solution: def findMin(self, nums: List[int]) -> int: # 先找中间，看左右相邻的大小，左右都比他大，那他就是min # 左小右大只能说明他在一段中，两端分别找一个min？ # 题解思路，x和最后一个属比大小 l, r = 0, len(nums) - 1 while l < r: mid = (l + r) // 2 if nums[mid] > nums[-1]: l = mid + 1 else: r = mid return nums[l]

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

两个有序数组 / 两个有序链表 / 两个有序序列

要求第 k 小 / 中位数 / Top K

不要合并全部，只围绕目标位置淘汰候选。

第 k 小问题：

1. 每次看两个数组的第 k//2 个元素

2. 谁小，谁前面那一批就不可能是答案

3. 丢掉那一批

4. k 减去丢掉的数量

5. 直到 k == 1

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # 如果nums1的-1 < nums2的0，直接找 m+n/2，和m+n/2 -m # 二分找出nums2的元素应该放在nums1的哪里，放进去再二分 # 想的复杂了，因为合并后可能是交叉的。应该想如何在两个有序数组中快速找第 k 小？ # 合并后第k小的->怎么不合并也可以->每次比较两个数组的第k//2个元素，淘汰较小的一批 # 方法二，二分切割，一个数组分左右，全部的左《=全部的右，中位数就在边界附近；max左《=min右 total = len(nums1) + len(nums2) # 总元素个数 if total % 2 == 1: # 奇数个，中位数就是第 (total//2 + 1) 小的数 return self.getKth(nums1, nums2, total // 2 + 1) else: # 偶数个，中位数是中间两个数的平均值 left = self.getKth(nums1, nums2, total // 2) # 左中位数（第 total/2 小） right = self.getKth(nums1, nums2, total // 2 + 1) # 右中位数（第 total/2+1 小） return (left + right) / 2 def getKth(self, nums1: List[int], nums2: List[int], k: int) -> int: # 在两个有序数组中查找第 k 小的数（k 从 1 开始计数） i, j = 0, 0 # i, j 分别指向 nums1 和 nums2 当前未被淘汰的起始位置 m, n = len(nums1), len(nums2) # i 表示 nums1 当前还没被淘汰的起点。 while True: # nums被淘汰完 # 剩余nums2[j:],找第k哥就是nums2[j+k-1] if i == m: # nums1 全部被淘汰，答案在 nums2 剩余部分 return nums2[j + k - 1] # 从 j 开始数 k 个，下标为 j+k-1 # nums2被淘汰完 if j == n: # nums2 全部被淘汰，答案在 nums1 剩余部分 return nums1[i + k - 1] # 从 i 开始数 k 个 if k == 1: # 只需要找最小的，即两个数组当前首元素的最小值 return min(nums1[i], nums2[j]) half = k // 2 # 每次比较前 half 个元素（避免越界取 min） # 在 nums1 中取第 half 个元素的下标（考虑边界） # 在不等长数组中安全取第 half 个元素 new_i = min(i + half, m) - 1 # 实际比较的元素索引，若剩余不够 half 则取最后一个 # 在 nums2 中取第 half 个元素的下标 new_j = min(j + half, n) - 1 pivot1 = nums1[new_i] # nums1 中参与比较的元素 pivot2 = nums2[new_j] # nums2 中参与比较的元素 if pivot1 <= pivot2: # nums1 的前 half 个（或更少）元素不可能成为第 k 小，淘汰它们 k -= new_i - i + 1 # 淘汰的元素个数 = new_i - i + 1 i = new_i + 1 # 移动 nums1 的起始位置 else: # nums2 的前 half 个元素被淘汰 k -= new_j - j + 1 j = new_j + 1

栈

有效的括号

就是pair的用处，不会用。栈定义就stack就行

class Solution: def isValid(self, s: str) -> bool: # 遇到左，进栈； # 遇到右，弹出栈顶，匹配了就接着，直到遍历完 stack = [] # 栈，怎么定义的？ # 匹配 pairs = {')':'(',']':'[','}':'{'} if s[0] in ")]}": return False for ch in s: if ch in "({[": stack.append(ch) else: if not stack or stack[-1] != pairs[ch]: return False stack.pop() return not stack

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。

• void push(int val) 将元素val推入堆栈。

• void pop() 删除堆栈顶部的元素。

• int top() 获取堆栈顶部的元素。

• int getMin() 获取堆栈中的最小元素。

设计类型的题，一直不会

二刷还是不会emmm

不明白pop的逻辑，why？

辅助栈 min_stack 的作用是同步记录历史最小值。当 pop 操作发生时，我们需要判断被弹出的元素是否恰好是当前的最小值（即 min_stack 的栈顶）。如果是，那么 min_stack 也需要弹出，以保持其栈顶始终是剩余元素中的最小值；如果不是，则 min_stack 保持不变。

self.stack.pop() 会移除并返回主栈的栈顶元素，然后与 min_stack 的栈顶比较。如果相等，说明被移除的元素正是当前最小值，因此 min_stack 也要弹出；如果不相等，说明移除的不是最小值，min_stack 不动。

class MinStack: def __init__(self): self.stack = [] self.min_stack = [] def push(self, val: int) -> None: self.stack.append(val) # stack一定append if not self.min_stack or val <= self.min_stack[-1]: # 如果 min中没有值，或者val比min小 self.min_stack.append(val) # min的栈顶更新 def pop(self) -> None: if self.stack.pop() == self.min_stack[-1]: # 判断，pop的是不是min的最小的，是的话才pop self.min_stack.pop() def top(self) -> int: return self.stack[-1] # top就是stack的定 def getMin(self) -> int: return self.min_stack[-1] # 最小的一直在，min定 # 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()

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 10(5)。

示例 1：

输入：s = "3[a]2[bc]" 输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]" 输出："accaccacc"

感觉很难真的想

辅助栈，写完了对着看我也要看好一会，不好理解

递归，[,开始；]，结束，返回 i，res；中间用tmp保存一下

辅助栈:

遇到 [ 就把当前状态保存到栈，遇到 ] 就弹出并重复构建.

• res：当前层已经解析出来的字符串（不含乘数）。

• multi：当前层需要重复的次数（可能有多位数字）。

• stack：存储 [multi, res] 的列表，当遇到 [ 时保存，遇到 ] 时弹出。

解释：

字符串 "3[a2[c]]" 可以看作：

• 外层：重复 3 次 "a" + (内层结果)

• 内层：重复 2 次 "c" → "cc"

• 外层："a" + "cc" = "acc"，再重复 3 次 → "accaccacc"

当你在解析时，一旦遇到 [，就表示要进入一个新的子表达式。这个子表达式完全独立于外层正在构建的 res 和 multi。外层还没处理完，它的 multi 和 res 必须保存起来，等内层算完后再恢复。

重置 res = "", multi = 0 就是为了清空工作区，开始专心构建内层的字符串。如果不重置，内层的字符就会混到外层的 res 里，导致错误。

自己模拟了一下，代码逻辑完全对，但是自己想的话想不出来。

递归：

• 返回值是 (新的索引, 本层解码字符串)。调用者拿到后，会从新的索引继续遍历。

• 当遇到 ] 时，返回当前层的结果和当前索引 i（此时 i 指向 ]）。外层在收到返回值后，会继续执行外层循环，但注意外层调用 dfs(s, i+1) 时传入了 i+1，而返回的 i 是内层 ] 的位置。外层拿到后，会在自己的循环中 将 i 更新为返回的索引（代码中通过赋值 i = ...），然后外层循环会继续 i += 1，从而跳过 ] 继续处理后面的字符。这个细节很微妙，但正是递归能正确解析嵌套的关键。

自己动手模拟，发现看不懂retun，是怎么回到上次的dfs的，特别是return i，res并没有回到dfs啊

递归返回后，控制权会精确地回到 dfs 被调用的那一行的 下一行

也就是到了]，返回i，res赋值给了i，tmp，就接着i，tmp下一行继续执行了。

辅助栈

class Solution: def decodeString(self, s: str) -> str: # 也就是找到一对，才能开始扩展。如何判断是一对了 stack, res, multi = [], "", 0 for c in s: if c == '[': stack.append([multi,res]) res ,multi = "",0 elif c == ']': cur_multi, last_res = stack.pop() res = last_res + cur_multi * res elif '0' <= c <= '9': multi = multi * 10 + int(c) else: res += c return res

递归

class Solution: def decodeString(self, s: str) -> str: # 也就是找到一对，才能开始扩展。如何判断是一对了 def dfs(s,i): res, multi = "",0 while i < len(s): if '0' <= s[i] <= '9': multi = multi * 10 + int(s[i]) elif s[i] == '[': i, tmp = dfs(s, i + 1) res += multi * tmp multi = 0 elif s[i] == ']': return i, res else: res += s[i] i += 1 return res return dfs(s,0)

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]

暴力超时

栈，用到下标，下标入栈，映射判断，找到比自己大的了，自己就可以弹出去了。不然就持续push

else: while stack and temperatures[i] > temperatures[stack[-1]]:

注意是while！！！因为可能会持续弹出来好多个

注意到栈的写法，持续的新值小的时候，会重复入栈某个下标。虽然没什么害处但是写法冗余

暴力

class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: answer = [0] * len(temperatures) for i in range(len(temperatures)): for j in range(i+1,len(temperatures)): if temperatures[j] > temperatures[i]: answer[i] = j-i break return answer

栈的做法

class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: answer = [0] * len(temperatures) stack = [] stack.append(0) for i in range(1,len(temperatures)): if temperatures[i] <= temperatures[stack[-1]]: stack.append(i) # 新的小于等于之前的，进栈 else: while stack and temperatures[i] > temperatures[stack[-1]]: answer[stack[-1]] = i - stack[-1] stack.pop() stack.append(i) return answer

class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: answer = [0] * len(temperatures) stack = [] # ?why--下标进站 stack.append(0) for i in range(1,len(temperatures)): while stack and temperatures[i] > temperatures[stack[-1]]: answer[stack[-1]] = i - stack[-1] stack.pop() stack.append(i) return answer

柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

看题目根本连想不到单调栈相关的

一个柱子i为基准，找左右第一个比它小的，这样右减左就是大于等于这个高度的柱子heights[i]的宽度，面积自然就的出来了。然后就是遍历全部取最大的。

和每日温度解法有点像，都是入栈下标。不过这个要注意一下首尾为了遍历顺利，都加个0。但是python的数组怎么加呢？直接+

求一个元素左边或右边第一个比他大或比他小的元素---单调栈

也就是便利的是i但是找到的是弹出的栈顶的这个地方的面积。栈顶位置两边两个小的，一个是当前的i，一个是栈顶的下一个元素。（栈是从底到顶递增的）

• 在数组首尾各加一个高度为 0 的哨兵，保证所有柱子都能被处理。

• 栈中存储的是柱子的索引，且栈内索引对应的高度是严格递增的（从栈底到栈顶高度递增）。

• 遍历每个柱子 i：

  • 如果当前高度 >= 栈顶高度，则直接入栈（维持递增）。

  • 否则，当前高度小于栈顶高度，说明栈顶柱子的右边第一个比它低的柱子就是 i（因为遇到更矮的柱子了）。此时我们弹出栈顶，并计算以该弹出柱子高度为高的矩形面积：

    • 左边第一个比它低的柱子就是弹出后新的栈顶（因为栈内是递增的，新栈顶的高度小于弹出柱子的高度）。

    • 宽度 = i - (新栈顶索引) - 1。

    • 更新答案。

  • 继续弹出直到栈顶高度 <= 当前高度，最后将当前索引入栈。

class Solution: def largestRectangleArea(self, heights: List[int]) -> int: # 找左右比自己小的的下标。右-左-1就是宽，该就是自己的heights if len(heights)==1: return heights[0] heights = [0] + heights + [0] #首位加了0，防止只有1个元素没法搞 stack = [] res = 0 stack.append(0) for i in range(1,len(heights)): # 遍历到这里 if heights[i] >= heights[stack[-1]]: stack.append(i) else: while stack and heights[i] < heights[stack[-1]]: mid = stack[-1] stack.pop() #比当前小的都在栈里，把自己出来，下一个就是比自己小的的下标 l = stack[-1] w = i - l - 1 res = max(res,w*heights[mid]) stack.append(i) # stack空了就直接入栈 return res

堆

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2 输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4

排序，nums[k-1]但是要on

自己想len和k怎么比，有点乱了，貌似没用堆

我想不明白，quick_select(small,k-len(nums)+len(small))如果在small里，这第二个参数是怎么确定的：

，，，就是正常的推断，只是这么写不容易让人理解，还不如直接就显式的写呢

1. 如果 k <= len(big) → 第 k 大一定在 big 中，因为 big 里的元素都大于 pivot，且前 len(big) 大的元素全部在 big 里。 → 递归 quick_select(big, k)。

2. 如果 len(big) < k <= len(big) + len(eq) → 第 k 大就是 pivot（因为 big 不够 k 个，加上所有等于 pivot 的正好覆盖）。 → 直接返回 pivot。

3. 如果 k > len(big) + len(eq) → 第 k 大在 small 中。因为 big 和 eq 一共才 len(big)+len(eq) 个元素，它们都是大于等于 pivot 的，但数量不足 k，所以真正的第 k 大一定是更小的数，只能在 small 里找。 → 在 small 中要找的是第几大？ 原本我们在全体中找第 k 大，已经排除了 len(big)+len(eq) 个更大的数，所以在 small 中要找的是第 k - (len(big)+len(eq)) 大。 而 len(big)+len(eq) = n - len(small)，因此参数为 k - (n - len(small)) = k - n + len(small)。

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # 排序 # return sorted(nums)[len(nums)-k],nlogn # 快速选择 def quick_select(nums,k): pivot = random.choice(nums) # 随机选择一个哨兵 big, eq, small = [], [], [] for num in nums: if num > pivot: big.append(num) elif num < pivot: small.append(num) else: eq.append(num) if k <= len(big): # 肯定在big里面 return quick_select(big,k) if len(nums) - len(small) < k:# why，这样就是在small，也就是大于等于的不够k个，肯定就不是第k大。但自己怎么想出来啊 return quick_select(small,k-len(nums)+len(small)) return pivot return quick_select(nums,k)

class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: # 排序 # return sorted(nums)[len(nums)-k],nlogn # 快速选择 def quick_select(nums,k): pivot = random.choice(nums) small,eq,big = [],[],[] for num in nums: if num > pivot: big.append(num) elif num < pivot: small.append(num) else: eq.append(num) if k <= len(big): return quick_select(big,k) elif k > len(big) + len(eq): return quick_select(small,k-(len(big)+len(eq))) else: return pivot return quick_select(nums,k)

前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

输入：nums = [1], k = 1

输出：[1]

mapping[nums[i]],记录nums[i]出现的次数，这样，哈希？

1，哈希，mapping[nums[i]]

2，出现次数一样的nums[i],放到一个桶中。桶buckets[c]是个列表，存出现次数为c的元素，遍历哈希表把buckets填了

3，倒遍历buckets，加入答案，直到答案长度为k

注意写法，Counter，Cnt.values(),reversed,buckets初始化,cnt.items()

写时候，kv没错但是！！k是本来的参数啊被覆盖了

cnt = Counter(nums):自动将 nums 列表中的每个不同元素作为键，该元素出现的次数作为值;

cnt.values() 会返回 cnt 中所有值的一个视图，也就是 nums 列表中所有元素对应的出现频率;

cnt.items() 是字典的常用方法，它会返回一个由 (键, 值) 元组构成的视图

关于reversed：

桶排序解法中，buckets 是一个列表，它的长度是 max_cnt + 1（max_cnt 是数组中元素的最大出现次数）。

• 索引：表示出现次数（例如索引 3 对应出现 3 次的元素）

• 值：是一个列表，存放所有出现次数等于该索引的元素值。

为什么要 reversed(buckets)？ 因为我们需要频率从高到低收集元素。buckets 的索引从小到大对应频率从低到高（索引 0 表示 0 次，索引 1 表示 1 次，…，索引 max_cnt 表示最高频）。 使用 reversed 可以让我们从最后一个桶（最高频）开始遍历，从而优先取出出现次数最多的元素，直到凑够 k 个。

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: cnt = Counter(nums) max_cnt = max(cnt.values()) buckets = [[] for _ in range(max_cnt+1)] #max_cnt + 1行 for k_, v in cnt.items(): buckets[v].append(k_) # 出现v次的元素k ans = [] for bucket in reversed(buckets): ans += bucket # 不能append，因为bucknet是列表，append成了[[],[]] if len(ans)==k: return ans

数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。

• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。

• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10(-5) 以内的答案将被接受。

示例 1：

输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0

又是，函数定义类的。。。

分左右之后一个大堆一个小堆！牛

堆默认小顶的，大的得写max

def addNum(self, num: int) -> None:

if len(self.left) == len(self.right):

heappush_max(self.left,heappushpop(self.right,num)) #先加入右，然后把右的顶加入到左

else:

heappush(self.right,heappushpop_max(self.left,num)) # 默认小队

也就是保证中间的两个数一致在栈顶，这就需要左边是大定，右边是小顶

class MedianFinder: def __init__(self): self.left = [] # 大定，存小数 self.right = [] # 小顶，存大数 # 约定left>=right def addNum(self, num: int) -> None: if len(self.left) == len(self.right): # 左右一样长时候 # 先进右侧，然后右侧弹出，加到左侧。保证left>=right heappush_max(self.left,heappushpop(self.right,num)) #先加入右，然后把右的顶加入到左 else: # 左比右多，先放到左，再弹出放到右 heappush(self.right,heappushpop_max(self.left,num)) # 默认小队 def findMedian(self) -> float: if len(self.left) > len(self.right): return self.left[0] return (self.left[0] + self.right[0])/2 # Your MedianFinder object will be instantiated and called as such: # obj = MedianFinder() # obj.addNum(num) # param_2 = obj.findMedian()

贪心

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

dpp[i][0],第i天持有，dp[i][1]第i天不持有，而不是动作的买入卖出，因为只能买卖一次；

dp[0][0]=-price[0],dp[0][1]=0，这个是为啥，第0天不持有，也就是都没买，0

搞明白状态转移就知道dp怎么变了,主要是的定义，是状态

class Solution: def maxProfit(self, prices: List[int]) -> int: # n行两列， dp = [[0,0] for _ in range(len(prices))] dp[0][0] = -prices[0] # 0天，买入 dp[0][1] = 0 for i in range(1,len(prices)): 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 dp[len(prices)-1][1]

跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

贪心和动规区别是？

覆盖范围，直到范围覆盖住了尾巴

错误写法：

for i in range(cov + 1): 这一行：range 在循环开始时就确定了范围，后续 cov 的变化不会影响循环次数。

但是cpp的就可以for(int i=0;i<=cov;i++)

所以要用while i<=cov：它体现了贪心算法的核心：只在当前能到达的范围内进行扩展。

或者i in range(n)

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

跳跃游戏Ⅱ

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

• 0 <= j <= nums[i] 且

• i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

贪心和dp？感觉这个就像传统dp，在一个位置条和不跳，但是调可以调的步数不唯一🤔

覆盖范围

先弄出来当前的覆盖范围i+nums[i]，然后遍历完覆盖范围看有没有到终点，没有？-再走，扩大覆盖，覆盖重点了，返回

i==cur就是：遍历完覆盖范围看有没有到终点（范围遍历完才是跳了一下）没有：往下走一步，也就是跳一下res++，更新覆盖范围，cur=next

AI解释：

1. 从索引 0 开始，初始 cur = 0，next_ = 0。

2. 遍历数组的每个位置 i（从 0 到 n-1）：

   1. 更新 next_ = max(next_, i + nums[i])，表示在当前这一步所能到达的范围内，记录下所有可能跳到的位置中的最远者。

   2. 当 i 达到当前这一步的边界（即 i == cur）时：

      • 说明我们已经走完了当前步所能覆盖的所有位置，不得不进行下一步跳跃。

      • 步数 res 加 1。

      • 将下一步的边界更新为 next_（即这一步中找到的最远位置）。

      • 如果新的边界已经能到达或超过最后一个位置（cur >= len(nums)-1），则直接返回步数。

3. 因为题目保证总能到达终点，循环一定会中途返回。

我们要从位置 0 跳到位置 n-1，每个位置 i 可以跳 nums[i] 步（即跳到 i+1, i+2, ..., i+nums[i]）。问最少跳跃次数。

贪心策略是：在当前步的覆盖范围内，选择下一步能到达的最远位置。也就是说，当我们在第 k 步时，已经知道当前步能到达的范围是 [cur_start, cur_end]，我们扫描这个范围内的所有位置，找出它们能跳到的最大位置 next_end，然后下一步的覆盖范围就是 [cur_end+1, next_end]。

class Solution: def jump(self, nums: List[int]) -> int: # 覆盖范围 # 一个的覆盖范围走一遍，结果最远的地方没有到尾巴 # 需要下一步，res+1，同时更新覆盖范围 res = 0 next_ = 0 #下一步 cur = 0 #当前遍历的最远的地方 if len(nums) == 1: return 0 for i in range(len(nums)): next_ = max(next_,i + nums[i]) if i == cur: res += 1 cur = next_ if cur >= (len(nums) - 1): return res

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

思考大概就是，第一个字母a，需要找到最后一个字母a，看看中间有什么字母，比如中间有bc，那么如果两个a之外还有bc，就需要把bc再抱进去。

a只能出现在一个片段，片段尽可能多

我去，合并区间

得到每个字母的下标区间-判断合并

last = {c: i for i, c in enumerate(s)}

记录字符串 s 中每个字母最后一次出现的索引

class Solution: def partitionLabels(self, s: str) -> List[int]: # 更新右端点，然后遍历时候直到右端点和end相等了，这就是一个区间了 # 和跳跃那个的i==cur有点像，虽然前面也在更新max，但是其实更新是没变的 last = {c:i for i, c in enumerate(s)} # 这样就得到了，最后的下边的位置 ans = [] start = end = 0 for i, c in enumerate(s): end = max(end,last[c]) if end == i: ans.append(end-start+1) start = end + 1 return ans

图论

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

DFS

class Solution: def numIslands(self, grid: List[List[str]]) -> int: # dfs，bfs # dfs，遇到岛屿开始遍历上下左右dfs，种植：越过边界；值为0，删除岛屿即置为0 def dfs(grid, i, j): if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0': return grid[i][j] = '0' dfs(grid, i + 1, j) dfs(grid, i, j + 1) dfs(grid, i - 1, j) dfs(grid, i, j - 1) count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': dfs(grid, i, j) # 发现之后先清除，再加1 count += 1 return count

BFS

借助队列，判断队列首部节点是否：未越界且为1：

  是，置零，上下左右加入对立

  不是，跳过

循环pop队列首节点，直到队列空

class Solution: def numIslands(self, grid: List[List[str]]) -> int: def bfs(grid, i, j): queue = [[i, j]] while queue: [i, j] = queue.pop(0) if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1': grid[i][j] = '0' queue += [[i+1,j],[i-1,j],[i,j+1],[i,j-1]] count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '0': continue bfs(grid, i, j) count += 1 return count

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；

• 值 1 代表新鲜橘子；

• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

最短，最少，一层层---bfs

多个烂橘子，多源

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a(i), b(i)] ，表示如果要学习课程 a(i) 则 必须 先学习课程 b(i)( )。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

拓扑排序：有向无环图->线性排序

先选入度为0的，入列，逐个出列减少相关课的入度。像bfs

数据结构：入读数组，邻接表

Bfs

入度表

class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # 初始化数据结构 indegrees = [0 for _ in range(numCourses)] adjacency = [[] for _ in range(numCourses)] queue = deque() # 填充数据结构 for cur, pre in prerequisites: indegrees[cur] += 1 adjacency[pre].append(cur) # 入读为0的 for i in range(len(indegrees)): if not indegrees[i]: queue.append(i) # bfs while queue: pre = queue.popleft() numCourses -= 1 for cur in adjacency[pre]: indegrees[cur] -= 1 if not indegrees[cur]: queue.append(cur) return not numCourses

Dfs

判断是否有环

实现Trie（前缀树）

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。

• void insert(String word) 向前缀树中插入字符串 word 。

• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。

• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

这种感觉很难想明白，特别是在lc这种不用in的

class Node: __slots__ = 'son', 'end' def __init__(self): self.son = {} self.end = False class Trie: def __init__(self): self.root = Node() def insert(self, word: str) -> None: cur = self.root for c in word: if c not in cur.son: # 没有路 cur.son[c] = Node() #弄成路 cur = cur.son[c] cur.end = True def find(self, word: str) -> int: cur = self.root for c in word: if c not in cur.son: # 不是一条路 return 0 cur =cur.son[c] return 2 if cur.end else 1 # 2完全匹配，1前缀匹配 def search(self, word: str) -> bool: return self.find(word) == 2 def startsWith(self, prefix: str) -> bool: return self.find(prefix) != 0 # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix)

动态规划

动规五部曲：

下标含义；递推公式；初始化；遍历顺序；打印dp

爬楼梯

最简单的，只需要注意初始化中，dp = [0] * (n+1)之后，如果n等于1的话，之后又初始化了dp[2]就越界了，so，n<=1return1

关于空间复杂度，dp来写，on；只用dp1，2和一个total，是o3，直接用变量记录1，2的情况，o1

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

下标定义 ：dp[i][j],第i行第j个数；i=1~n，j=1~i，

递推公式：dp[i][j] = dp[i-1][j-1]+dp[i-1][j]

初始化：dp= [[0]*(n+1)],dp[1][1]=1,dp[2][1]=1,dp[2][2] = 1

遍历顺序：上到下前到后

打印dp：

初始化n*n的dp都错了，其实也可以递推写

dp：

class Solution: def generate(self, numRows: int) -> List[List[int]]: if numRows == 0: return [] # 初始化 dp，dp[i] 表示第 i 行（i 从 0 开始），长度为 i+1 dp = [[0] * (i+1) for i in range(numRows)] # 第一行 dp[0][0] = 1 # 逐行构造 for i in range(1, numRows): dp[i][0] = dp[i][i] = 1 # 每行首尾为1 for j in range(1, i): dp[i][j] = dp[i-1][j-1] + dp[i-1][j] return dp

递归：

class Solution: def generate(self, numRows: int) -> List[List[int]]: res = [] for i in range(numRows): row = [1] * (i + 1) for j in range(1,i):# 第一个数肯定1，不在遍历 row[j] = res[i-1][j-1] + res[i-1][j] res.append(row) return res

打家劫舍

初始化时侯

dp = []*n是错的，应为[]本来就是空列表成n还是空列表.应该是：dp = [0] * n 或者dp = [0 for _ in range(n)]

dp

class Solution: def rob(self, nums: List[int]) -> int: #dp[i],偷到i个位置的最大的金额，投不投？ # 不投dp[i] = dp[i-1]，投，dp[i] = dp[i-2] + nums[i] # dp[i] = max(dp[i-2]+nums[i],dp[i-1]) n = len(nums) if n == 1: return nums[0] if n == 2: return max(nums[0],nums[1]) dp = []*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[n-1]

递推

class Solution: def rob(self, nums: List[int]) -> int: prev2, prev1 = 0, 0 # prev2 = dp[i-2], prev1 = dp[i-1] for num in nums: cur = max(prev2 + num, prev1) prev2, prev1 = prev1, cur return prev1

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

最少数量。和零钱兑换很像。先物品后背包-组合；先背包后物品-排列。而求最少，既不是组合又不是排列，也就是没关系。这一题那个顺序都行。变相的背包问题

class Solution: def numSquares(self, n: int) -> int: dp = [inf] * (n+1) dp[0] = 0 for i in range(1,n+1):#背包 for j in range(1,int(i ** 0.5)+1):# 物品 dp[i] = min(dp[i-j*j]+1,dp[i]) return dp[n]

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

算是代码随想录的母题了，这题讲解可听

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

完全背包问题。递推公式怎么写？站在当前，往可以推出来当前结果的方向看。

dp[i] 表示 s 的前 i 个字符（即 s[0:i]）是否可以被成功拆分。dp[0] = True 表示空字符串总是可以被拆分。

• 外层循环 i 从 0 到 len(s)，依次判断前 i 个字符是否可拆分。

• 内层循环 j 从 0 到 i-1，尝试将子串 s[j:i] 作为最后一个单词。

• 如果 dp[j] 为真（即前 j 个字符可拆分），并且 s[j:i] 在单词集合中，那么 dp[i] 就为真，并跳出内层循环（因为只要找到一个拆分方式即可）。

分割回文串

字符串长度i，能组成时候dp[i]为true---dp[len(s)]

[j,i]&& dp[j]==true

dp[0]=true,其他false

求的是排列，先背包后物品

For i=1 s.size i+

j=0 j<i j++

String word(sbustr(j,i-j))以j为开始，长度为i-j

是否在字典中 word find and dp[j] == true-----true

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: #完全背包问题？ 线性dp # dp[i][j] wordSet = set(wordDict) dp = [False] * (len(s) + 1) dp[0] = True for i in range(len(s) + 1):#i 表示当前子串的结束位置（不包含 i） for j in range(i):# j 表示子串的开始位置 if dp[j] and s[j:i] in wordSet: dp[i] = True break return dp[len(s)]

why：wodrDict->wordSet

用空间换时间策略，牺牲少量内存（存储哈希表）换取查询的高效;set去重，set查找o1，list查找on

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

和单词拆分的遍历形式太像了

dp[i]：0-i数组的最长严格递增子序列长度为dp[i];以nums[i]为结尾的

递推公式：dp[i]=max(dp[i-1],dp[i-1]+1 if dp[i]>dp[i-1])(可以删除，真的可以这样嘛)，dp[i] > dp[i-1]逻辑不对吧？子序列，可以不连续。子序列和子数组不一样，子数组是连续的；所以这个状态转移需要看前面的很多状态;其实写dp[i] > dp[i-1]本就不对，应该是nums的比大小；

定义状态： dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

状态转移方程： 对于每个 i，考虑它之前的所有位置 j（0 ≤ j < i），如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面，从而形成一个新的更长的子序列，其长度为 dp[j] + 1

class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [1] * (len(nums)) # 0-7 for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i],dp[j]+1) return max(dp)

乘积最大子数组(典型正负)

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

示例 1:

输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。

dp[i]：nums[i]为结尾的最大的连续子数组乘积

递推公式：dp[i]=max(dp[i-1],dp[i-1]*nums[i])

初始化：dp = -inf

遍历顺序：前到后，整个数组用i，前面的用j遍历前面的

If nums[j] < nums[i]

dp[i] = (dp[i],dp[j]+1)

以上思路有问题，没考虑nums为负数，，，

需要同时维护以当前结尾的最大值和最小值:

max_dp[i] = max(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])

min_dp[i] = min(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])

关于inf：

-inf 并不是一个内置的常量或关键字，而是一个未定义的变量名。Python 中表示无穷大的标准方法是使用 float('inf')（正无穷）和 float('-inf')（负无穷）

o1

class Solution: def maxProduct(self, nums: List[int]) -> int: max_dp = min_dp = ans = nums[0] for i in range(1,len(nums)): x = nums[i] cur_max = max(x,max_dp * x,min_dp * x) cue_min = min(x,max_dp * x,min_dp * x) max_dp,min_dp = cur_max,cue_min ans = max(ans,max_dp) return ans

常规dp

class Solution: def maxProduct(self, nums: List[int]) -> int: max_dp = [float('-inf')] * len(nums) min_dp = [float('-inf')] * len(nums) if len(nums) == 1: return nums[0] max_dp[0] = min_dp[0] = ans = nums[0] for i in range(1,len(nums)): max_dp[i] = max(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i]) min_dp[i] = min(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i]) ans = max(ans,max_dp[i]) return ans

分割等和子集（0-1背包）

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。

Dp = [False]*len(nums)

下标含义：dp[i] ,以nums[i]为结尾的能否分成两个和相等的子集；容量为j的背包，最大价值为dp[j](重量等与价值)，dp[target] == target即可

递推公式：dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])

初始化：0

遍历：一维01，先物品后背包，而且背包是倒着的，才能是一个物品放一次

打印dp

01背包都没看出来，就瞎想

二刷看不懂了，特别是循环中的j的区间--j<nums[i]，搞清楚j的含义，背包容量是j，如果j比nums[i]还小，装不下，dp[j]就不用变化；为什么 nums[i]-1 作为停止条件？range(start, stop, step) 在 stop 处停止（不包含 stop）。为了包含 nums[i]，需要将 stop 设为 nums[i]-1，这样循环最后一次取到 nums[i]。

• 令 target = total // 2，问题变为：是否存在一个子集，其元素和恰好等于 target？

• 有一个容量为 target 的背包，每个数字 nums[i] 的重量和价值都是它本身，问能否恰好装满背包。

• 外循环 i 表示考虑前 i 个数字。

• 内循环 j 从 target 向下遍历到 nums[i]，这是 0-1 背包的标准倒序写法，防止同一个物品被重复使用。

• 状态转移：dp[j] 表示当前能凑出的不超过 j 的最大和。对于数字 nums[i]，要么不选（保持 dp[j]），要么选（dp[j - nums[i]] + nums[i]），取最大值。

• 最终 dp[target] 就是背包容量为 target 时能装下的最大和。如果它恰好等于 target，说明可以装满，即存在子集和为 target。

有一个容量为 target 的背包，每个数字 nums[i] 重量和价值都是它本身，问能否恰好装满背包。

写时候的语法错误：

total += (nums[i] for i in range(len(nums)))，错，这样写不对，直接sum(nums)即可，同时sum也别做变量名比较好，SyntaxError语法错误

你的写法 sum += nums[i] for i in range(len(nums)) 在语法上是错误的，原因是：

Python 的赋值语句右侧需要是一个表达式，而 nums[i] for i in range(len(nums)) 本身是一个生成器表达式（generator expression），但它必须用圆括号括起来才能作为表达式使用。如果不加括号，Python 解析器会认为 for 关键字出现在了一个不合理的位置，从而抛出 SyntaxError。

即使你加上括号写成 sum += (nums[i] for i in range(len(nums)))，语法上虽然正确，但实际效果是将一个生成器对象（而不是所有数值的和）加到 sum 上，导致类型错误或结果不正确。因此，正确的求和方式应该是内置函数 sum(nums) 或显式循环累加。

很自然的，01，先看物品选不选，所以先遍历物品

class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if total % 2 == 1: return False target = total // 2 dp = [0] * (target + 1) for i in range(len(nums)):#物品 # 倒序更新，保证每个数字只用一次 for j in range(target,nums[i]-1,-1):# 不考虑j大于nums[i]嘛，不用，自动处理了 dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]) return True if dp[target] == target else False

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

示例 1：

输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"

感觉难就难在，状态转移难写。肯定要用栈。

很好理解，但是别忘记了遍历s时候，标记true的前提，st不能为空

class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) is_valid = [False] * n st = [] # 未配对左括号下边 # 标记配对的 for i ,ch in enumerate(s): if ch == '(': st.append(i) elif st: # 右括号，栈顶有元素，配对 is_valid[i] = is_valid[st.pop()] = True ans = cnt = 0 for b in is_valid: if b: cnt += 1 ans = max(ans,cnt) else cnt = 0 # 重置 return ans # 遍历全部，能配对的地方都标记为true，最后数一下连续的true最大是多少

多维动态规划

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

算是自己完全的写出来了，除了dp初始化搜了一下，该说不说五部曲真的，很明晰

dp = [[1]*n for _ in range(m)]

class Solution: def uniquePaths(self, m: int, n: int) -> int: # dp[i][j]为，到达ij的不同的路径数目 if m == 1 or n == 1: return 1 # dp[i][j] = dp[i-1][j] + dp[i][j-1] # return dp[m-1][n-1],dp[0][:]=1,dp[:][0]=1,如何初始化dp dp = [[1] * n for _ in range(m)] for i in range(1,m): for j in range(1,n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m-1][n-1]

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

和上一题简直一模一样啊，不过在初始化那里，第一行第一列卡了一下。还有就是当m或n等于1时候的处理。

class Solution:

def minPathSum(self, grid: [[int]]) -> int:

for i in range(len(grid)):

for j in range(len(grid[0])):

if i == j == 0: continue

elif i == 0: grid[i][j] = grid[i][j - 1] + grid[i][j]

elif j == 0: grid[i][j] = grid[i - 1][j] + grid[i][j]

else: grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]

return grid[-1][-1]

牛啊。初始化第一行第一例时候，就是i==0或j==0时候。直接在grid上写

class Solution: def minPathSum(self, grid: List[List[int]]) -> int: # dp[i][j]为，到达ij的不同的路径数目 m = len(grid) n = len(grid[0]) total = 0 if m == 1 : return sum(grid[0]) if n == 1 : for i in range(m): total += grid[i][0] return total # return dp[m-1][n-1],dp[0][:]=1,dp[:][0]=1,如何初始化dp dp = [[0] * n for _ in range(m)] # 初始化需要初始化一行一列的dp dp[0][0] = grid[0][0] for i in range(1,n):#初始化第一行dp[0][:] dp[0][i] = dp[0][i-1] + grid[0][i] for i in range(1,m):#初始化第一行dp[0][:] dp[i][0] = dp[i-1][0] + grid[i][0] for i in range(1,m): for j in range(1,n): dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j] return dp[m-1][n-1]

最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

字符串相关的，还是很欠缺

么做到奇偶分离的呢，是不是不论奇偶，两个for都要遍历？

都遍历，不过lr的初始化，一个是同一个位置，一个是两个位置。偶数的话很明显，偶数是回文中间肯定是两个一样的，

中心扩展

枚举所有可能的中心点，然后向两边扩展，直到不能扩展为止，记录最长回文。奇偶分开：

class Solution: def longestPalindrome(self, s: str) -> str: # 回文，左右和右左一样， n = len(s) ans_left = ans_right = 0 # 奇数个 for i in range(n): l = r = i while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 # 循环结束，s[l+1]-s[r-1]是会问 if r - l - 1 > ans_right - ans_left: ans_left, ans_right = l + 1, r # 偶数 for i in range(n - 1): l, r = i, i + 1 while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 if r - l - 1 > ans_right - ans_left: ans_left, ans_right = l + 1, r return s[ans_left:ans_right]

奇偶合并：

Manacher算法？

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

还是要自己先想明白，才能更好的确定下标

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: # 传统dp m = len(text1) + 1 n = len(text2) + 1 dp = [[0] * n for _ in range(m)]# m行，n列 for i in range(1,m): for j in range(1,n): if text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else : dp[i][j] = max(dp[i-1][j],dp[i][j-1]) return dp[m-1][n-1] # 这个下标弄得就很乱啊，这里的dp[i][j]是，以i-1，j-1为结尾的最长

编辑距离

常看常新啊常看常新，能这么说吗，其实就是记不住。

和上一题很像，都是i-1，j-1为结尾的，这就要弄好下标了

注意就是，删除增加算是一样的，更改的是另一样。dpij = dpi-1j-1+1，也就是在源来的前面的一眼大哥基础上加1，就一样了

class Solution: def minDistance(self, word1: str, word2: str) -> int: # 删除，添加，是一样的。改变又是一种 # dp[i][j] i-1，j-1为结尾的 # 注意初始化 dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)] for i in range(len(word1)+1): dp[i][0] = i for i in range(len(word2)+1): dp[0][i] = i for i in range(1,len(word1)+1): for j in range(1,len(word2)+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1) return dp[len(word1)][len(word2)]

技巧

只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]

输出：1

看完分析就很明确----异或

class Solution: def singleNumber(self, nums: List[int]) -> int: x = 0 for num in nums: x ^= num return x

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3] 输出：3

前k个高频元素，cnt=Counter(nums)，然后找到v最大的那个，遍历一下输出k就ok，一遍过

class Solution: def majorityElement(self, nums: List[int]) -> int: cnt = Counter(nums) #输出v最大的k_ max_cnt = max(cnt.values()) for k_, v in cnt.items(): if v == max_cnt: return k_

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

• sorted(nums) 返回一个新的已排序列表，不修改原列表。

• nums.sort() # 直接对原列表排序

• nums[:] = sorted(nums) # 将排序后的元素赋值给原列表的切片

单指针，头部元素，ono1

遍历两遍

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) ptr = 0 for i in range(n): if nums[i] == 0: nums[i], nums[ptr] = nums[ptr], nums[i] ptr += 1 for i in range(ptr,n): if nums[i] == 1: nums[i], nums[ptr] = nums[ptr], nums[i] ptr += 1

双指针

下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。

• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。

• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3] 输出：[1,3,2]

看完题目没一点思路，下一个排列怎么写？能直接比较吗按字典序？

看解析，就是，字典序

如果原数组不存在nums[i-1] < nums[i]，直接反转，否则：

从右往左，找到第一个左小于右边的数a，这个数a要和右边的某个数b交换；

某个数b是：a右边，从右到左，第一个大于a的数

交换ab

然后把b的右边的数，弄成升序（也就是反转，也就是交换对称位置上的元素）

二刷：

1. 从右向左找到第一个升序对 (i-1, i)，满足 nums[i-1] < nums[i]。

   1. 这个 i-1 就是需要被替换的位置。

2. 如果找到了这样的 i：

   1. 再从右向左找到第一个大于 nums[i-1] 的数 nums[j]。

   2. 交换 nums[i-1] 和 nums[j]。

   3. 然后将 nums[i] 到末尾的子数组反转（使其变成升序，即最小排列）。(因为i-1是第一个比i小的，所以i右侧原本肯定是倒序的)

3. 如果没找到（即整个数组是降序），则直接反转整个数组。

class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ for i in range(len(nums)-1,0,-1):# 倒遍历 if nums[i-1] < nums[i]: # 找打了，就是把i-1的位置的往后 for j in range(len(nums)-1,i-1,-1):# 到找，第一个比i-1位置大的，就是右边最小的比i-1位置大的数，这个数放在i-1位置 if nums[j] > nums[i-1]: nums[i-1],nums[j] = nums[j], nums[i-1] break for j in range((len(nums)-i+1)//2): nums[i+j],nums[len(nums)-1-j] = nums[len(nums)-1-j],nums[i+j] return nums # 反转操作需要交换对称位置上的元素 nums.reverse() # 这个是原数组是倒叙，直接返回reverse

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2] 输出：2

示例 2：

输入：nums = [3,1,3,4,2] 输出：3

直接用多数元素那个题的答案就ac了...

题解没看懂

2026.5.29终于一遍了hot100。。。

2026.6.15二刷，看了看笔记，接下来写题先不看笔记，直接写，写不出来直接背

Practices