题单来源https://leetcode.cn/studyplan/top-100-liked/类别题目解题思路哈希表1.两数之和简单49.字母异位词分组中等128.最长连续序列中等①以每个item为开端且item-1不在set里面②while循环 1遍历即可双指针283.移动零简单fast, slow 0, 0while fast n:if nums[fast] ! 0:nums[slow], nums[fast] 交换26. 删除有序数组中的重复项简单增加slow, fast 1, 1while fast n:ifnums[slow - 1] ! nums[fast]: nums[slow] nums[fast] 重写80. 删除有序数组中的重复项 II中等增加slow, fast 2, 2while fast n:ifnums[slow - 2] ! nums[fast]:11.盛最多水的容器中等1.左右指针从两头往中间靠拢2.谁小谁先算面积3.然后移动指针15.三数之和中等1.先排序2.确定第一个值和第二值3.第三个值从最后往前找16. 最接近的三数之和中等增加1.先排序2.前三个最小3.从i开始双指针判断18. 四数之和中等新增1.先排序42.接雨水困难①从左到右求一个数组②从右到左求一个数组③遍历值累加求和即可407. 接雨水 II (困难)增加658. 找到 K 个最接近的元素(中等)增加while right - left 1 k: # 缩区间到只剩k个元素if abs(arr[left] - x) abs(arr[right] - x): # 左右移动滑动窗口3.无重复字符的最长子串中等①滑动窗口每次向右边滑动一下②while循环扩展右边界③更新最长子串rk ④滑动窗口用set()删除用remove(元素)438.找到字符串中所有字母异位词中等winds[ord(s[i]) - ord(‘a’)] - 1winds[ord(s[ilen_p]) - ord(‘a’)] 1if windp winds:209. 长度最小的子数组中等(新增)核心思想①滑动窗口②要求子序列是连续的③求和达到一个target的情况下就开始收缩左边界子串560.和为 K 的子数组中等前缀和,presum_dict collections.defaultdict(int)解法①先累加②求resdict[和-k],③字典[和]1239.滑动窗口最大值困难from collections import deque使用队列1.while循环删除小个子2.依次进队列3.判断窗口是否溢出并q.popleft()4.从k个位置开始输出76.最小覆盖子串困难count collections.Counter(t)miss len(t)if miss 0: # 满足一个窗口时while循环开始收缩左边界普通数组53.最大子数组和中等dp[i] max(dp[i-1]nums[i], nums[i])56.合并区间中等intervals sorted(intervals,keylambda x:x[0], reverseFalse)189.轮转数组中等k k % nnums[::] nums[n-k:] nums[:n-k]238.除了自身以外数组的乘积中等41.缺失的第一个正数困难v nums[i] - 1if 0 v n and nums[i] ! nums[v]: # 交换数据nums[i], nums[v] nums[v], nums[i]else:i 1 # 不符合条件进行1矩阵73.矩阵置零中等54.螺旋矩阵中等48.旋转图像中等matrix[::] zip(*matrix[::-1]),1.水平翻转2.主对角线反转如果逆时针则先1.左右翻转2.主对角线反转74. 搜索二维矩阵中等左下角为开始240.搜索二维矩阵 II中等转化为一维数字链表160.相交链表简单206.反转链表简单头插法234.回文链表简单141.环形链表简单同下142.环形链表 II中等快慢指针# 解法两阶段先找入口在找交点# 找入口快慢指针找交点都是单步slow, fast head, head287. 寻找重复数中等增加快慢指针# 解法两阶段先找入口在找交点# 找入口快慢指针找交点都是单步slow nums[slow]fast nums[nums[fast]]21.合并两个有序链表简单2.两数相加中等19.删除链表的倒数第 N 个结点中等24.两两交换链表中的节点中等25.K 个一组翻转链表困难138.随机链表的复制中等148.排序链表中等23.合并 K 个升序链表困难146.LRU 缓存中等83. 删除排序链表中的重复元素简单增加82. 删除排序链表中的重复元素 II中等增加二叉树94.二叉树的中序遍历简单104.二叉树的最大深度简单226.翻转二叉树简单101.对称二叉树简单def f(p, q):543.二叉树的直径简单self.maxlen max(self.maxlen, leftright1)102.二叉树的层序遍历中等108.将有序数组转换为二叉搜索树简单98.验证二叉搜索树中等230.二叉搜索树中第 K 小的元素中等199.二叉树的右视图中等队列即可114.二叉树展开为链表中等105.从前序与中序遍历序列构造二叉树中等node.left self.buildTree(preorder[1:idx1], inorder[:idx])node.right self.buildTree(preorder[idx1:], inorder[idx1:])106. 从中序与后序遍历序列构造二叉树中等增加root.left self.buildTree(inorder[:idx], postorder[:idx])root.right self.buildTree(inorder[idx1:],postorder[idx:-1]) # [idx:-1] 截止 倒数第二个数112. 路径总和简单增加return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)113. 路径总和 II中等增加dfs(root.left, targetSum-root.val)dfs(root.right, targetSum-root.val)path.pop() # 回溯法前一个入坑的需要撤回437.路径总和 III中等sumlist [v root.val for v in sumlist] [root.val]特别注意①初始化[]②追加的[root.val]return sumlist.count(targetSum) f(root.right, sumlist) f(root.left, sumlist)前缀和解法特别注意初始化defaultdict(int)01①先累加②求resdict[和-k],③字典[和]1④递归结束后需要字典[和] - 1236.二叉树的最近公共祖先中等if not root or root p or root q: return root # 情况1 找到一个就上报left self.lowestCommonAncestor(root.left, p, q) # 情况2 找不到就左右递归right self.lowestCommonAncestor(root.right, p, q)124.二叉树中的最大路径和困难left max(dfs(root.left), 0) # 特别注意 负数的情况right max(dfs(root.right), 0)self.maxsum max(self.maxsum, leftrightroot.val)return max(left, right) root.val图论200.岛屿数量中等找到一个入口深度优先探查即可994.腐烂的橘子中等队列先把腐烂的入队然后出队列入队时间1207.课程表中等邻接矩阵判断是否有环261. 以图判树中等增加并查集208.实现 Trie (前缀树)中等回溯46.全排列中等注意用分层的思想方法47. 全排列 II中等增加if i 0 and nums[i-1] nums[i]:continuedfs(nums[:i]nums[i1:], path[nums[i]])78.子集中等res res [ v [item] for v in res]90. 子集 II中等增加1.先排序2.for循环下 :①去重i index and nums[i] nums[i -1]②dfs(nums, i 1, path[nums[i]])17.电话号码的字母组合中等39.组合总和中等可以无限重复取先排序分层递归40. 组合总和 II中等增加先排序判断重复问题22.括号生成中等79.单词搜索中等从每个位置出发深度优先探索即可131.分割回文串中等每层“切一点”并验证是否是回文串51.N 皇后困难52. N 皇后 II困难增加if q[i] j or abs(q[i]-j) abs(i-k): # 不同列不同斜线93. 复原 IP 地址中等增加二分查找35.搜索插入位置简单把代码跑起来就知道resmid 放到那里了74.搜索二维矩阵中等34.在排序数组中查找元素的第一个和最后一个位置中等33.搜索旋转排序数组中等81. 搜索旋转排序数组 II中等增加153.寻找旋转排序数组中的最小值中等154. 寻找旋转排序数组中的最小值 II困难增加4.寻找两个正序数组的中位数困难378. 有序矩阵中第 K 小的元素中等增加1.核心思想值域二分法2.total bisect.bisect_right(row, x)410. 分割数组的最大值困难增加1.核心思想值域二分法left, right max(nums), sum(nums) # 确定上下界658. 找到 K 个最接近的元素中等增加162. 寻找峰值中等增加if nums[mid] nums[mid 1]:特别注意# 大于右边栈20.有效的括号简单155.最小栈中等394.字符串解码中等# 核心思想 1.遇到左号进栈2.遇到右号出栈 3.遇到数字积攒 4.字符串就拼接726. 原子的数量困难增加739.每日温度中等# 核心思路①while踢出小个子的并登记②进栈84.柱状图中最大的矩形困难# 核心思想①while踢出高个子并计算一次面积特别注意stack [-1], 尾巴append(0)85. 最大矩形困难增加# 核心思想踢出高个子并计算一次面积特别注意stack [-1]32.最长有效括号困难增加特别注意stack [-1]堆215.数组中的第K个最大元素中等347.前 K 个高频元素中等295.数据流的中位数困难贪心算法121.买卖股票的最佳时机简单记录的是最小值55.跳跃游戏中等45.跳跃游戏 II中等核心 if next_max index: next_max max(next_max, itemindex)763.划分字母区间中等135. 分发糖果困难增加动态规划122. 买卖股票的最佳时机 II中等增加可以买卖多次求梯度和即可123. 买卖股票的最佳时机 III困难hold [float(‘-inf’)] * (k1) # 持有股票时的状态 - 剩余的钱或者手里的钱sold [0] * (k1) # 已经销售时的状态 - 剩余的钱或者手里的钱188. 买卖股票的最佳时机 IV困难增加hold[j] max(hold[j], sold[j-1] - price)sold[j] max(sold[j], hold[j] price)hold[j] # 物理含义当前你持有股票的时你有多少钱显然上一个状态不持有股票买入就减去sold[j] # 物理含义当你不持有股票的时你有多少钱显然上一个持有股票卖出去就是加上312. 戳气球困难增加dp [[0] * n for _ in range(n)] # 初始化dp 头尾[1]把0都删除dp[left][right] max(dp[left][right], nums[left] * nums[i] * nums[right] dp[left][i] dp[i][right])887. 鸡蛋掉落困难增加1.dp[m][k] 拥有k个鸡蛋最多允许尝试m次操作最坏情况下能够保证测出临界点的最大楼层数量。鸡蛋碎了:dp[m - 1][k - 1],鸡蛋没碎:dp[m-1][k],当前层1dp[m][k] dp[m - 1][k - 1] dp[m - 1][k] 11000. 合并石头的最低成本困难增加70.爬楼梯简单118.杨辉三角简单row.append(res[i-1][j] res[i-1][j-1])198.打家劫舍中等dp[i] max(dp[i-2] nums[i], dp[i-1])213. 打家劫舍 II中等增加279.完全平方数中等对于每个 i从 1 到 n遍历所有小于等于 i 的完全平方数 j²则 f[i] min(f[i - j²]) 11 表示加上当前的 j² 这个数for i in range(1, n 1):for j in range(1, int(i ** 0.5) 1):dp[i] min(dp[i], dp[i - j * j] 1)322.零钱兑换中等核心思想可以理解为爬楼梯题目有多少个路径可以通向终点上一个状态是什么if i - coin 0: dp[i] min(dp[i], dp[i-coin] 1)518. 零钱兑换 II中等增加for coin in coinsfor i in range(amount1):if i - coin 0:dp[i] dp[i-coin]139.单词拆分中等if dp[j] and s[j:i] in wordDict: dp[i] True300.最长递增子序列中等if nums[i] nums[j]: dp[i] max(dp[i], dp[j]1) # 特别注意 判断条件152.乘积最大子数组中等dpmax[i] max(nums[i], nums[i]*dpmin[i-1], nums[i]*dpmax[i-1])dpmin[i] min(nums[i], nums[i]*dpmin[i-1], nums[i]*dpmax[i-1])416.分割等和子集中等for num in nums: # 遍历每个数字每个数只能选一次for j in range(target, num - 1, -1): # 倒序遍历防止重复选取同一数字dp[j] dp[j] or dp[j - num] # 不选当前数 / 选当前数满足其一即可32.最长有效括号困难多维动态规划62.不同路径中等64.最小路径和中等5.最长回文子串中等718. 最长重复子数组中等(增加)if A[i-1] B[j-1]: dp[i][j] dp[i-1][j-1] 11143.最长公共子序列中等# dp[i][j] text1[i] text2[j] -- dp[i-1][j-1] 1# 不相等时dp[i][j] max(dp[i-1][j], dp[i][j-1])72.编辑距离中等if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1技巧136.只出现一次的数字简单return reduce(lambda x,y:x^y, nums)169.多数元素简单75.颜色分类中等31.下一个排列中等画图理解即可287.寻找重复数中等快慢双指针找环其他263. 丑数简单for p in [2, 3, 5]:while num % p 0 and num 0:num num // p264. 丑数 II中等while ugly[i2] * 2 ugly[-1]