160: 相交链表（简单）
我的思路：每个链表从头指针开始，交替向前推进，每步推进作一次判断是否指向同一个节点。
手写代码：
class Node:
def __init__(self, val):
self.val = val
self.next: Node
def IntersectionNode(A: Node, B: Node):
alter = 0
while notsame(A, B):
if alter == 0:
A = A.next
alter = 1
elif alter == 1:
B = B.next
alter = 0
return A答案：思路是错的，因为可能会错过
我的思路2：暴力遍历，对每个A节点，遍历一遍B
答案：可以，但是不推荐
推荐解法：
- 双指针法：不够直观，我想不出来；
- 哈希算法减少复杂度：先遍历一个链表，用字典存起来，再用另一个去查。可以想得到，但我当时没这么想。
236: 二叉树的最近公共祖先（中等）
我的思路：从根节点 DFS，判断每个节点的子孙包含几个指定的节点，存起来，然后按BFS的顺序遍历，找第一个为2的
手写代码：
dict = {}
def DFS(T):
count = 0
if T.val == a or b:
count += 1
count += DFS(T.left)
count += DFS(T.right)
dict[T] = count
return count
def BFS(T):
stack = []
stack.push(T)
while stack != []:
t = stack.pop()
stack.push(t.left, t.right)
if dict[t] == 2:
return t
def Answer(T, a, b):
DFS(T)
return BFS(T)
答案：思路没问题，但是不够优雅
推荐答案：直接定义“公共祖先”函数DFS递归
234. 回文链表（简单）
思路：直接用栈，如果和顶上一样，就消掉，不一样就push，看看最后是不是正好能消掉
手写代码：
def Answer(head):
stack = Stack()
l = head
while l != None:
if l.val != stack.top():
stack.push(l.val)
elif l.val == stack.top():
stack.pop()
l = l.next
return stack.empty()答案：思路错误，与“相邻对称抵消”问题混淆。
思路2: 先遍历一遍确定长度，还是用栈，左半边一直push，右半边一直pop，看看能不能顺利进行
答案：思路正确，但有些细节待优化
推荐答案：
- 在思路2中，遍历一遍之后就可以把链表变成数组了，访问更快，但付出了\(O(n)\)的空间代价。
- 快慢指针，一个指针一倍速，一个指针两倍速，找到中点，然后就好操作了
739: 每日温度（中等）
思路：先遍历一遍，把波峰波谷的值和位置记下来，往上升的全都是1， 往下降的每一段（山谷），一点点往谷底夹击：先判断波峰如果左大，则找下一个波峰，一直到没有；然后左波峰往下走一个位置，继续判断，如果在最近的波峰右大，则右波峰往左走一个位置。
答案：思路正确，但太麻烦
推荐答案：单调栈，但我看都没看懂，自然不可能想到
226. 翻转二叉树（简单）
思路：DFS遍历每个节点，调换他们的左右子树
手写代码：
def reverse(T):
temp = T.left
T.right = temp
T.left = self.right
reverse(T.left)
reverse(T.right)答案：简单，秒了
221. 最大正方形（中等）
思路：想了20分钟，没法用动态规划，设计规则也不好设计
答案：可以用动态规划，但转移方程我不能理解
215. 数组中的第K个最大元素（中等）
思路：遍历构造最大堆，然后删除K次根节点
手写代码：
class MaxHeap:
def __init__(self, elements):
self.h = [nan] * len(elements)
self.len = 0
for e in elements:
self.insert(e)
self.len += 1
def insert(self, e):
self.h.append(e)
self.len += 1
if self.h[self.len // 2] < e:
temp = self.h[self.len // 2]
self.h[self.len // 2] = self.h[self.len]
self.h[self.len] = temp
def delete(self, index):
self.h[index] = self.h[self.len-1]
self.h[self.len-1]
self.len -= 1
t = index
while t < self.len:
if self.h[2t - 1] > self.h[t]:
if self.h[2t] > self.h[2t - 1]:
temp = self.h[t]
self.h[t] = self.h[2t]
self.h[2t] = temp
t = 2t
else:
temp = self.h[t]
self.h[t] = self.h[2t-1]
self.h[2t-1] = temp
t = 2t -1
def Kth(nums, k):
h = MaxHeap(nums)
for i in range(k):
h.delete(index=0)
return h.h[0]
答案：记住堆就秒了
208. 实现 Trie (前缀树)（中等）
207. 课程表（中等）
思路：就是判断是否是有向无环图。从任意节点DFS，看看能不能重复到自己，如果能则不行；DFS完了之后，再从课程表里选还没DFS访问过的，继续DFS。
def DFS(course, prerequisites, one_round_visited, visited):
one_round_visited[course] = True
visited[course] = True
for i in prerequisites:
if prerequisites[i][0] == course:
if one_round_visited[prerequisites[i][1]] == True: return False
DFS(prerequisites[i][0])
return True
def canFinish(numCourses, prerequisites):
visited = [False] * numCourses
for course in range(numCourses):
one_round_visited = [False] * numCourses
if visited[course] == False:
ring_exists = DFS(course, prerequisites, one_round_visited, visited)
if ring_exists:
return False
return True答案：完全正确，秒了
206. 反转链表（简单）
思路：从左往右一个个把箭头反过来
答案：完全正确，秒了
200. 岛屿数量（中等）
思路：从任意节点DFS，岛屿里的点被标记已访问，完了之后岛屿数量+1；再继续从未访问的节点DFS，直到全部访问。
答案：完全正确，秒了
198. 打家劫舍（中等）
思路：动态规划
MaxStolen[n] = max(MaxStolen[n-1], MaxStolen[n-2] + Amount[n]) MaxStolen[1] = Amount[1] MaxStolen[2] = max(Amount[1], Amount[2])
答案：完全正确，标准动态规划题，秒了
169. 多数元素（简单）
思路：这种限定条件的一定是存在某个性质，判断这个特殊的性质即可，但是我想不出来
评价：完全不会，自己也想不出来
推荐答案：Boyer–Moore 投票算法，选择一个candidate，然后拿其他的跟他碰，如果不一样就抵消了-1，一样就加上+1。减到负数换candidate
238. 除自身以外数组的乘积（中等）
思路：回溯法，从不完全的一个因子也没有开始，一点点加因子，试探，找一个列表存这些部分乘积，如果与前面算重复了，就不探索。算到目标（n缺第i乘积的）的时候，就存到answer[i]里面。因为可以剪枝，所以是 \(O(n)\)。
评价：完全错误，回溯法没法降到 \(O(n)\)
推荐答案：左右两部分，1到i-1，i+1到n。前缀积从左往右扫一遍算完，后缀积从右往左扫一遍算完，最后i从1到n扫一遍拼接
155. 最小栈（中等）
152. 乘积最大子数组（中等）
思路：动态规划，写不出来
推荐答案：一个变量如果扯到另一个变动的因素，就设两个变量
148. 排序链表（中等）
思路：先变成数组，再用任意 \(O(nlogn)\) 时间复杂度的排序算法，如快速排序、归并排序，最后还原为链表。
评价：可以，但不是最优结果
推荐答案：链表可以原地归并排序！
146. LRU 缓存（中等）
142. 环形链表 II（中等）
思路：我只能用标记来判断有没有重新访问过，像 DFS 那样。不标记的办法想不出来
推荐答案：快慢指针（我发现很多链表题都是这么干的），注意：快慢指针相遇的点正好是环入点，可以算出来
141. 环形链表（简单）
同上，环形链表 II（中等）的退化版本
139. 单词拆分（中等）
思路：先观察字典里的词有没有包含关系，如果有，则先考虑最小子词。 如果是都互不包含，则按照KMP算法，并行地匹配字典中的所有能匹配的词。如果不能匹配断掉了，则false，如果能撑到最后，则true。
评价：搞麻烦了。
推荐答案：动态规划，dp[i]表示s的前i个字符能否拆分成字典中的词。转移方程：dp[i] = dp[j] and (s[j:i] in wordDict) for j in [0, i)。这个转移方程很有意思，它是之前所有的dp值的函数，所以这样的动态规划是存在可行的。不要一看很麻烦就觉得不是动态规划，仔细想想。
136. 只出现一次的数字（简单）
思路：完全没有思路
推荐答案：异或，a^a=0, a^0=a。请注意，这个题限制了整数数组，所以就可以用到位运算。
647. 回文子串（中等）
思路：动态规划
num[i] = num[i - 1] + 1 +if(i-1~i是不是回文) + … + if(1~i是不是回文)
评价：一维DP不常见吧，这样相当于暴力求解？
推荐做法：两头是不固定的，而且回文串所以是二维DP。很奇怪，仔细看看。
128. 最长连续序列（中等）
思路：构造一个堆，然后依次吐出来，如果连续就count+1，保存最大count。
评价：这就是堆排序，复杂度是\(O(nlogn)\)呀
思路：动态规划，肯定不能一维DP，则设置两个变量：最长的头，最长的尾。还是弄不出来
评价：不可能是动态规划，因为要求\(O(n)\)
推荐思路：哈希表，字典或集合都行（推荐集合），按值查找。因为只需要看它后面有没有，所以查找一次不麻烦。
124. 二叉树中的最大路径和（困难）
思路：当作一个图，在图上做动态规划
评价：这是特殊的图，还是要利用二叉树的结构
推荐思路：就是简单的递归，有点像求depth一样，二叉树一般没有其他办法
322. 零钱兑换（中等）
思路：贪心法，先找最大面额凑，再找次之的
评价：不对！面额有问题，只挑最大的可能凑不出来
推荐思路：动态规划，转移方程的step和面额有关系：
minCoin[amount] = min (coin coins, if amount-coin > 0 )(minCoin[amount-coin]) + 1
这是道经典的DP题，不应该不会
494. 目标和（中等）
思路：和322很像，动态规划：
SumWays[amount, n] = max(SumWays[amount-nums[n], n-1], SumWays[amount+nums[n], n-1])
(n表示nums取前n个)
评价：完全正确！有更简化的版本（转化为背包问题），但思路一致
461. 汉明距离（简单）
思路：转化成二进制数组，然后作比较
评价：正确
推荐思路：直接异或，数1的个数
448. 找到所有数组中消失的数字（简单）
思路：构造集合（哈希表），然后用1-n的值一个个访问集合看有没有，如果没有，则加入到结果中
def disappear(nums):
nums_set = set(nums)
results = []
for i in range(1,n+1):
if i in nums_set:
results.append(i)
return results评价：完全正确。所谓的进阶版本，原地标记，说是不使用额外空间，但是把输入数组给修改了，还是占空间。
438. 找到字符串中所有字母异位词（中等）
思路：所谓的异位词就是字符统计个数相同的。那就滑动窗口，一次一格，看看新来的字母和划过的字母是否一样，如果一样，本来是异位词，现在肯定也是；不是的，也不是，如果不一样，本来是异位词可以直接推出下一个不是异位词，本来不是异位词，那就判断一下是不是异位词
评价：完全正确，秒了
437. 路径总和 III（中等）
思路：二叉树肯定是要递归遍历的。我写了一个最暴力的解法，直接统计从每个节点出发的符合条件的路径数目，然后全加起来。每个节点出发的路径数目，用回溯法，但是不带剪枝。
def DFS(T):
count_left = DFS(T.left)
count_right = DFS(T.right)
count_itself = count_begin(T, value =0)
count = count_left + count_right + count_itself
return count
def count_begin(T, value):
count = 0
value += T.value
if value == target:
count += 1
count += count_begin(T.left, value)
count += count_begin(T.right, value)
return count
result = DFS(T)评价：完全正确，只是说这个题是比较麻烦的，而且就该用麻烦的办法做
416. 分割等和子集（中等）
思路：先排个序，先从最右边取一个数，然后在左边叠加，如果用完了还没叠到右边那个数，就false，如果正好，则继续从右边取；如果多了，也是从右边取，最后看看会不会剩余，如果正好不剩，则true
评价：可以，但容易超时。
推荐做法：首先每个子集元素和一定是知道的（如果能分割），是sum(nums)/2。如果sum(nums)是奇数，直接false。然后相当于背包问题了，使用动态规划来求解。
406. 根据身高重建序列（中等）
思路：先从大到小排序，再从大到小依次插入重建
评价：完全正确！但我没有意识到是贪心法
399. 除法求值（中等）
思路：是一个带权的无向图。query是不定长的，所以应该是独立的，只考虑一个query怎么求就行。先遍历一遍获得所有定义的变量列表。先看有没有直接连接的，有就直接输出，没有再考虑中间插一个除他俩之外的变量，遍历一遍，没有再继续查，递归地进行。这是个回溯法。
手写代码：（待写，值得写）
评价：完全正确
394. 字符串解码（中等）
思路：这道题应该是栈的应用。递归函数，从左往右扫，碰到数字，就开启匹配括号模式，碰到数字入栈，继续扫碰到右中括号出栈，直到栈空，就匹配到了它的括号，先递归进去处理里面的，递归出来之后（应该是里面都拆完了），把它按数字拆出来。
评价：思路正确，步骤有点麻烦
347. 前K个高频元素（中等）
思路：哈希表，遍历一遍把词数存字典，最后取值前k大的。前k大的可以\(O(n)\) 用锦标赛算法，而不用排序
评价：对取前k大元素理解不到位。锦标赛算法貌似不是很常见，不太好写。可以用最小堆，限制它最长为k，遇到k以上就弹出去最小值，能让操作到\(O(nlogk)\)。快速选择算法，是快速排序的缩水版，每次只递归一边，一遍 partition 之后右边如果大于k个，则递归右边，如果小于k个，则递归左边（但是k减掉了右边的个数），等于k个就结束。partition的过程和快速排序是一样的，都是左右两边指针往中间逼近，与partition交换，区别只在递归
338. 比特位计数（简单）
思路：简单遍历，每次和一个log2 i 异或。对于 \(O(n)\) 的算法，应该是有某种固定规律（递推公式），比较麻烦，不愿意想
评价：思路完全正确
337. 打家劫舍 III （中等）
思路：一定是动态规划，但不会在树上搞
推荐思路：框架还是递归遍历！动态规划也是在这框架下的，因为它本质上也是个递归。可以在节点上定义变量，根节点就相当于一维里的n，左右子树，你可以简单理解为 n-1,n-2这些。这道题是在节点上定义了2个变量（偷根的最高金额，不偷根的最高金额）
121. 买卖股票的最佳时机（简单）
思路：单调栈，在中间增量式记录单调序列的极差
评价：正确，但这题可以贪心，但我想不到
推荐思路：在遍历途中维护一个史低价，随时计算当前价格和史低价的差值，更新最大利润。
312. 戳气球（困难）
思路：一定是动态规划
MaxCoins[1,…, n] = max(MaxCoins[1, …, n 去掉1], …, MaxCoins[1, …, n 去掉n])
评价：是动态规划，但是区间DP
dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
这个公式非常难想到，到现在我也没搞明白
309. 买卖股票的最佳时机含冷冻期（中等）
思路：先遍历一遍把各个局部最低值找出来（贪心），然后从每个局部最低值开始算它上升区间和赚的钱。如果上升区间紧挨着，则比较左边峰值下降一个和右边最低值上升一个哪个变化更大，修改相应区间。
评价：ChatGPT说我这种方法不是最优
推荐思路：动态规划，设置三个一维变量
- 第 i 天结束时，手里持有股票 的情况下的最大利润
- 第 i 天结束时，刚卖出股票 的情况下的最大利润
- 第 i 天结束时，既没有股票，也没卖出 的情况下的最大利润
让我想是完全不可能想到
301. 删除无效的括号（困难）
思路：括号匹配问题用栈，遇到左括号push，右括号就与栈顶抵消，抵消不了，标记出来待删，最后把栈里剩下的全都标记删除
评价：没仔细读题，它要求所有情况，还要最少数量
思路：只能用回溯法，先统计需要删几个，确定树的深度，每删一次就用括号匹配栈来判断，如果不行，那在其基础上继续删也不行（就不是最少的了），就剪枝
评价：完全正确
300. 最长递增子序列（中等）
思路：动态规划，因为是递增序列，所以一维DP，所以设置两个变量
lengthOfLIS[n] = lengthOfLIS[n-1] + 1 if maxval[n-1]< a[n] else maxval[n] = a[n] if lengthOfLIS[n] > lengthOfLIS[n-1] else maxval[n-1]
评价：公式错了。一维DP不一定是两个变量，也有可能是多个step。
推荐思路：设以 a[n] 为结尾的最长递增子序列长度为 L[n]，则 L[n] = 1 + max(L[j]) (j在n前面且a[j]比a[n]小)。最后取L[i]的max
297. 二叉树的序列化与反序列化（困难）
287. 寻找重复数（中等）
思路：快慢指针？试了试，不太行。我能想到的只能是两两比较，暴力求解。
评价：没有看清题目，数字都是1-n范围内
推荐思路：就是说它的值就可以当下标来引用。这样数组就构成了环，检测是不是环形链表以及环形链表的入点可以用快慢指针
283. 移动零（简单）
思路：往后堆，碰到一个非0的数就与第一个0交换
评价：完全正确，秒了。这道题某种程度上也可以认为是双指针
279. 完全平方数（中等）
思路：典型动态规划，有点像找零钱，只不过零钱是完全平方数
MinSum[n] = min(MinSum[n-1], MinSum[n-4], … +MinSum[n-M(n)] ) + 1，M(n)是不超过n的最大的完全平方数
评价：完全正确，秒了
253. 会议室 II（中等）
思路：贪心法。先从开始时间最早的开始安排，安排之后再安排开始时间离它的结束时间最近的下一个，直到没有。然后再启动新的会议室安排。
评价：是贪心法，但不是这么贪的。会议室要平行地启动。
推荐思路：从开始时间最早的开始安排，安排一个会议室，然后安排下一个开始时间的，如果没有合适的会议室，就开新的，如果有，就放到那里面。
240. 搜索二维矩阵 II（中等）
思路：从左上角开始，斜着一排排扫。(1,1)-(2,1),(1,2)- (3,1) (2,2) (1,3)
评价：这比暴力遍历好一点，但最坏情况还是 \(O(m*n)\)
推荐思路：从右上角或左下角开始。一行、一列那样跳。这个思路非常清奇，一般想不到。
239. 滑动窗口最大值（困难）
思路：一开始先找出最大值的位置，用指针指出来。每次滑动，先看最大值位置是不是在窗口最左边，如果是，则直接求一遍新窗口的最大值；如果不是，让新来的和上一个窗口最大值比较，看看是否要更新指针和最大值。
评价：这比暴力遍历好一点，但最坏情况还是 \(O(n*k)\)
推荐思路：双端单调队列，队头元素如果滑出窗口 → 弹出队头 2. 新元素加入时 → 弹出所有比它小的队尾元素 3. 队头即为当前窗口最大值
22. 括号生成（中等）
思路：回溯法。从一个括号开始，尝试在每个半括号的间隔处插入括号对，如果没存过，则存下来，如果存了，则剪枝。
评价：是回溯法，但这个回溯几乎等于暴力遍历。
推荐思路：回溯法，每次的step是append一个半括号，可以是左，也可以是右，如果左括号或右括号满了（超过要求的k），则只能append另一种括号
49. 字母异位词分组（中等）
思路：异位词就是词频相等的。这些元素可以定义相等关系，问题转化为怎么把一个数组的元素分组。这应该是退化的排序算法？可以暴力统计。
评价：思路对，不过分组可以用哈希分组。
推荐思路：哈希分组，用字典，没有的话自动创建，可以每次 \(O(1)\) 查找键，值就是要存的组员（包括键自己）。
48. 旋转图像（中等）
思路：旋转相当于水平+对角线反转，翻转就是数值交换，一个temp就够了
评价：完全正确，秒了
46. 全排列（中等）
思路：暴力回溯（因为要求返回所有叶子结点）
手写代码：
def DFS(case, nums, results):
if len(case) == len(nums):
results.append()
return
else:
for n in nums and not in case:
DFS(case+[n], nums, results)
def permute(nums):
results = []
DFS([], nums, results)
return results
评价：完全正确，秒了
42. 接雨水（困难）
思路：从左到右遍历，第一次出现往下降的趋势时，开启接水模式（flag），记录左高度，统计与左高度的差，加到结果里。直到出现比左高度还高的右高度，关闭接水模式，继续往后，直到再次出现下降的趋势
评价：不能处理局部最高
思路：从左到右遍历，第一次出现往下降的趋势时，开启接水模式（flag），记录左高度，在这个过程中开一个队列，记录下降的信息，直到开始上升时，开始统计接雨水加到结果里，直到1.再次下降/或者2.比队列头高或持平。对第1种情况，把从队列pop到这个右高度，然后把剩下的统计加起来作为接到的雨水；对第2种情况，直接统计整个队列的雨水。关闭接水模式，直到再次下降。
评价：思路完全正确，这个队列属于单调队列，但是用栈，从低到高统计雨水方便一点
39. 组合总和（中等）
思路：暴力回溯法，从target开始减，叶子结点是target减到0
评价：非常简单，秒了
543. 二叉树的直径（简单）
思路：有点像动态规划，但应该不算。先定义根节点左边、右边最长路径，这个东西可以递归算下去，左边最长路径等于左节点左边和右边最长路径的最大值 + 1，同理右节点。叶子结点为0。最后每个节点左右最长路径加起来，取最大
评价：完全正确，虽然但是为什么这是简单题？
34. 在排序数组中查找元素的第一个和最后一个位置（中等）
思路：二分查找，找到之后向左右扩展看能走多远，加起来
评价：最坏情况，全是target，左右扩展需要 \(O(n)\)
推荐思路：二分查找可以查第一个比xx大/小的元素，只要不找到就return就行！
33. 搜索旋转排序数组（中等）
思路：我只能想到先找到最小点，然后二分查找（平移坐标）。但是找最小点最坏情况是\(O(n)\)。如果这个整数数组就是从0开始+1+1的，那我们可以直接访问a[a[0]]=0。
评价：很抱歉，这个题证书数组不是这个意思
推荐思路：类似二分查找的思路，可以找这种旋转数组的最小点，因为右边一定比左边小。如果mid比右边大，说明最小值应该在右半边。
32. 最长有效括号（困难）
思路：用栈，看看它最长能连续多少步不会让右括号触底。右括号触底了就跳过，统计归零。
评价：完全正确，秒了
31. 下一个排列（中等）
思路：从右往左找，看看第一个上升的，如果第一对就是上升，直接交换；如果第二对，看看从右往左第3个和最后一个比较，要么这个第3个放到后面去，要么最后一个放到前面。如果第三对，也就是前两对一直连续下降，。。。很多规则，
评价：方向没问题，就是有点麻烦，需要仔细找找规律
538. 把二叉搜索树转换为累加树（中等）
思路：暴力解法是遍历每一个节点，把它和右子树都加起来。但这里面肯定可以共用一些东西。
GreaterSum[T] = T.val + Sum[T.right] Sum[T] = Sum[T.left] + T.val + Sum[T.right]
顺序是先递归算Sum存下来，再遍历算GreaterSum
评价：做法没问题，但有更简单的
推荐思路：可以先算右边的，再算左边的，就不需要记了，一遍算出来（只有右子树的Sum即GreaterSum）。逆中序遍历
23. 合并K个升序链表（困难）
思路：难道不是K次归并吗？
推荐思路：归并这件事也可以两两来做，或者并行来做
560. 和为K的子数组（中等）
思路：和39.组合总和（中等）很像，但这里要求连续了，用回溯还不如暴力遍历。
推荐思路：记下来0-i 的和，sum[i..j] = 0-j - 0-i =k，所以对每个0-i，反推出来0-j=k+0-i，然后硬查这个数是出现的次数。 这个题没掌握
21. 合并两个有序链表（简单）
思路：归并排序的归并步骤
评价：简单，秒了
20. 有效的括号（简单）
思路：直接用栈括号匹配
评价：简单，秒了
19. 删除链表的倒数第N个节点（中等）
思路：双指针，先提前跑n个，然后一块往后扫描，提前跑的指针到头的时候，就可以删除了。
评价：简单，秒了
17. 电话号码的字母组合（中等）
思路：要列举所有的情况，暴力回溯
评价：简单，秒了
15. 三数之和（中等）
思路：暴力回溯，深度是3
评价：不是最优解
思路：哈希一下，本来三数等于0，可以转换为两数等于负的第三数，暴力搜索两个数字的组合，然后在哈希表中查找第三个数的负数（要求不与两数重复）。这样能降到 \(O(n^2)\).
评价：完全正确
推荐做法：这个题可以先排序的，也是一种简化的办法。然后遍历就可以去掉某些情况，也能降到 \(O(n^2)\).
11. 盛最多水的容器（中等）
思路：看起来要用单调栈，但实际上，单调栈可能只管连续的。暴力解法是遍历柱子组合，所以就是要找比 \(O(n^2)\) 小的。我想到了从最大值往下找，但这样最坏情况也是 \(O(n^2)\)（设想单调递减）。
评价：不是最优解
推荐做法：可以从两边夹逼来贪心
10. 正则表达式匹配（困难）
思路：最难的就是匹配 .*。所以可以先搜索有没有它。匹配夹在这些点星中间的。
评价：很麻烦，而且不一定有效
推荐做法：动态规划，设 IsMatch[i][j] 是原串前i个和模式串前j个是否匹配。
5. 最长回文子串（中等）
思路：动态规划。设IsPalindrome[i][j]是它是不是回文子串，则它与i-1，j-1是不是回文子串一致（两头相等），或者两头不相等，它肯定不是回文子串。最后找最长的时候，先从1-n最大的找，再从1-n-1，2-n这种。找到就返回
评价：完全正确，秒了
4. 寻找两个正序数组的中位数（困难）
思路：看这个题目要求的复杂度，应该是两个同时做二分查找。但我不会
评价：是这样的
推荐思路：看不懂
3. 无重复字符的最长子串（中等）
思路：用两个指针维护当前考虑的子串，一个集合（哈希表）存，如果不重复，就加进来，如果重复，就把后面的指针往后找到这个重复的位置，中间经过的位置从集合中踢掉。在其中监控集合的count，标记最大值。
评价：完全正确，秒了（可能有概率想不到）
2. 两数相加（中等）
思路：变成数加起来再变回链表。
评价：非常简单，秒了
79. 单词搜索（中等）
思路：图上的回溯法，先找到起点，找下一个点，下一个点允许的分支情况是四周+没有被占过的点，如果没有就剪枝。如果有了，直接返回。
评价：完全正确，秒了
114. 二叉树展开成链表（中等）
思路：这道题直接考察先序遍历，如果没有其他要求，秒了，但是它要求原地。这应该就是，在递归的时候连接+断开指针，设计规则。
手写代码：
试试！
621. 任务调度器（中等）
思路：贪心法，先统计不同的个数，然后每次穿一整遍所有剩下的，实在不行就插间隔
评价：完全正确
617. 合并二叉树（简单）
思路：非常直接，同步遍历两个二叉树，以一个为基准，如果没有另一个的左子树或右子树，则指过去或者copy一份（copy也是递归的）。返回这个基准的树。
手写代码：
def mergeTrees(root1, root2):
root1.val += root2.val
if root1.left == None:
root1.left = root2.left
else:
mergeTrees(root1.left, root2.left)
if root1.right == None:
root1.right = root2.right
else:
mergeTrees(root1.right, root2.right)评价：写法有点问题，再看看
105. 从前序与中序遍历序列构造二叉树（中等）
思路：从先序遍历为基础，一步步构造，如有不确定，参照中序遍历的信息。可以递归。
手写代码：
def DFS(preorder, inorder):
if preorder == []:
return None
val = preorder[0]
T = Node(val, None, None)
id = inorder.index(val)
N = len(preorder)
left_length = id
right_length = N -left_length - 1
T.left = DFS(preorder[1:left_length], inorder[:id-1])
T.right = DFS(preorder[left_length+1, :], inorder[id+1:])
return T评价：完全正确，有点麻烦，但是比较模版化
104. 二叉树的最大深度（简单）
思路：递归求深度
手写代码：
def depth(T):
if T == None:
return 0
return 1+ max(depth(T.left), depth(T.right))评价：简单直接，秒了
102. 二叉树的层序遍历（中等）
思路：BFS，用队列
手写代码：
def leveltraverse(T):
queue = Queue()
if T == None:
return []
results = []
queue.push(T)
while not queue.empty():
t = queue.pop()
results.append(t)
if t.left:
queue.push(t.left)
if t.right:
queue.push(t.right)
return results评价：简单正确，但请注意要求返回层次信息。可以提前预判在每一层有多少个（在queue.push()的时候统计）。
101. 对称二叉树（简单）
思路：检查根节点的左右子树是不是相反的。
手写代码：
def isSymmetric(root):
if root == None or (root.left == None and root.right == None):
return True
return isReverse(root.left, root_right)
def isReverse(root1, root2):
if root1 == None and root2 == None:
return True
if (root1 == None and root != None) or (root1 != None and root == None):
return False
if root1.val != root2.val:
return False
return isReverse(root1.left, root2.right) and isReverse(root1.right, root2.left)评价：完全正确，秒了
98. 验证二叉搜索树（中等）
思路：递归定义，所以递归遍历
手写代码：
def isValidBST(root, ):
if root.left is None and root.right is None:
return True
if root.left:
if root.left >= root.val:
return false
if root.right:
if root.right <= root.val:
return false
return isValidBST(root.left) and isValidBST(root.right)
评价：只比较了局部的左右孩子，没有比较全部的
重新手写代码：
def isValidBST(root, minval=-inf, maxval=inf):
left_maxval = min(root.val, maxval)
right_minval = max(root.val, minval)
if root.left is None and root.right is None:
return True
if root.left:
if root.left >=left_maxval:
return false
if root.right:
if root.right <= right_minval:
return false
return isValidBST(root.left, maxval=left_maxval) and isValidBST(root.right, minval=right_minval)
isValidBST(root, minval=-inf, maxval=inf)
评价：完全正确
96. 不同的二叉搜索树（中等）
思路：暴力回溯，剪枝的策略是如果不满足它应该的minval和maxval，就剪枝。
评价：题目只让输出数目。
推荐思路：动态规划。设n有G(n)种情况，可以选择不同的根节点i，左节点有G(i-1)种，右节点有G(n-i)种，乘起来。G(n)的通项公式是卡特兰数。
94. 二叉树的中序遍历（简单）
思路：直接递归中序遍历
手写代码：
def inorder(T, results):
if T.left:
inorder(T.left, results)
results.append(T.val)
if T.right:
inorder(T.right, results)
inorder(T, [])评价：简单直接，秒了
85. 最大矩形（困难）
思路：和最大正方形类似，应该也是动态规划，但我不会
评价：如果每行统计1，可以看作84. 柱形图中的最大正方形
84. 柱形图中的最大正方形（困难）
思路：维护一个最大矩形面积，单调栈（注意要记录它的下标）寻找答案。在开始增加的时候，记住矩形的左边，如果增加一个元素，push进去，比较此时矩形与左边的矩形大小，看看左边需不需要移动过来，更新最大矩形面积，如果降低的话，一直pop到能push。
评价：完全正确
1. 两数之和（简单）
思路：用字典反存下标（哈希），按值搜索 \(O(1)\)
手写代码：
def twoSum(nums, target):
hash_dict = {}
for i, num in enumerate(nums):
hash_dict[num] = i
for i, num in enumerate(nums):
if target - num in hash_dict:
return [i, hash_dict[target - num]] 评价：思路正确，不过这里有个问题，字典的键不能重复。
推荐思路：可以边查边存，不会出现遗漏的，因为它是配对，用前面的查后面找不到，但过后一定有后面查前面，一定能找到，所以不会漏。这样也能解决存到字典里重复的问题，因为是先查再存。
78. 子集（中等）
思路：这是暴力回溯的例题
手写代码：
def DFS(current, nums, results):
results.append(current)
for i in nums:
if i not in current:
DFS(current+[i], nums, results)
DFS([], nums, [])评价：思路正确，代码与一般写法稍有不同
76. 最小覆盖子串（困难）
思路：只需统计词频，中间无关的字符可以用用个数替代。然后就不会做了
评价：我好像感觉到了要用滑动窗口，但是没有想下去
推荐思路：滑动窗口
75. 颜色分类（中等）
思路：是一个极强限制条件的排序。2就应该在最后面，0就应该在最前面。两遍夹逼，右边遇到0就直接换到最左边，左边遇到2就直接换到最右边。
评价：方向是对的，但其实一遍扫描，把0放最前面，把2放最后面就行了
72. 编辑距离（中等）
思路：动态规划
设word1[1..i]到word2[1..j] 的编辑距离是 D[i][j]
D[i][j] = D[i-1][j-1] if a[i] == a[j] = min(D[i][j-1] +1, D[i-1][j] + 1, D[i-1][j-1]+1) if a[i] !=a[j] D[i][0] = i D[0][j] = j
评价：完全正确，就是想起来非常费劲
手写代码：
def minDistance(word1, word2):
m = len(word1)
n = len(word2)
D = [[] * n] * m
for i in range(m):
D[i][0] = i
for j in range(n):
D[0][j] = j
for k in range(1, m + n +1):
for i in range(1, k):
j = k - i
if a[i] == a[j]:
D[i][j] = D[i-1][j-1]
else:
D[i][j] = min(D[i][j-1] +1, D[i-1][j] + 1, D[i-1][j-1]+1)
return D[m][n]70. 爬楼梯（简单）
思路：动态规划
climb[n] = max(climb[n-1], climb[n-2]) climb[0] = 0 climb[1] = 1 climb[2] = 2
评价：应该是求和，没注意看。0没必要定义
581. 最短无序连续子数组（中等）
思路：既然题目要用 \(O(n)\) 复杂度，我猜就是哈希了。用有序字典，建好之后，把第k个的值不等于k的挑出来即可。
评价：没问题，但有序字典涉及排序，是 \(O(nlogn)\)
推荐思路：因为是连续的，所以找到左右边界即可。两遍夹逼
64. 最小路径和（中等）
思路：很明显的动态规划题
D[i][j] = min(D[i-1][j], D[i][j-1]) + a[i][j] D[i][0] = a[0][0] + … + a[i][0] D[0][j] = a[0][0] +… + a[0][j]
在动态规划的时候记录每次取min的哪个
手写代码：
def minPathSum(a, m, n):
D = [[0] for _ in range(n)] for _ in range(m)
path = [[0] for _ in range(n)] for _ in range(m)
for i in range(m):
D[i][0] += a[i][0]
path[i][0] = "left"
for j in range(n):
D[0][j] += a[0][j]
path[i][0] = "up"
for i in range(1, m):
for j in range(1,n):
if D[i-1][j] < D[i][j-1]:
D[i][j] = D[i-1][j] + a[i][j]
path[i][j] = "left"
else:
D[i][j] = D[i][j-1] + a[i][j]
path[i][j] = "right"
i = m, j= n
results = [D[m][n]]
while i != 0 or j = 0:
if path[i][j] == "left":
i = i -1
if path[i][j] == "up":
j = j -1
results.append[D[i][j]]
results = results.reverse()评价：完全正确，秒了
62. 不同路径（中等）
思路：二维动态规划
DP[i][j] = DP[i-1][j] + DP[i][j-1] DP[i][0] = 1 DP[0][j] = 1
评价：完全正确，秒了
56. 合并区间（中等）
思路：贪心法，先按照开始时间排序，从小到大，目标区间先设为1，第2个合到1里，能合则合（1存合并结果，2空），不能合则目标区间设为2，看3能不能合。最后把空的删掉
评价：完全正确，秒了
55. 跳跃游戏（中等）
思路：动态规划
canJump[n] = (canJump[n-1] and nums[n-1] > 1) or … or (canJump[n-nums[n]] and nums[n-nums[n]] > nums[n]) canJump[n] = false if nums[n] == 0 canJump[1] = true
评价：公式写错了
53. 最大子数组和（中等）
思路：双指针，从每次出现的第一个正数开始，碰到负数看看跨不跨过去到下一个正数区间末尾，一直往前拱，直到不能再增长为止；这时候尾指针往前跟到下一个正数区间的开始。中间记录最大和和指针位置
评价：可行，但比较麻烦
推荐思路：动态规划
DP[i] = max(DP[i-1] + a[i], a[i]) DP[0] = a[0]
不懂，为什么？