介绍

• 对于算法题，按题型类别刷题才会更有成效，因此我这里在网上搜索并参考了下 “🔥 LeetCode 热题 HOT 100” 的题型归类，并在其基础上做了一定的完善，希望能够记录自己的刷题历程，有所收获！具体参考如下文章：
  • 【热题】LeetCode 热题 HOT 100分类+题解
  • leetcode HOT100总结
  • leetcode算法总结 —— HOT 100分类整理
    
• 我这里只做了LeetCode 热题 HOT 100中的 easy\color{green}{easy}easy 和 middle\color{orange}{middle}middle 的题，hard\color{red}{hard}hard 的题难度较大暂时都跳过了（题目上都有 删除线 标识），大部分面试也不会考察，后面有精力再做研究。
• 题目后带有 ★\color{red}{★}★ 标识的表示后续还要继续反复练习，题目可能不难，但有时可能会忽略其中的一些刷题细节而导致错误
• 每一种类型的题目，并不绝对是按照题号递增的顺序来排列的（当然大部分都是按题号大小排好序的）。
  因为有些题目其实很相似，放在一起更好，便单独对他们做了调整，比如 [647. 回文子串] 和 [5. 最长回文子串]
• 这里面的每一道题，都有相对应我自己日常整理的题解，具体可参考：我的博客-LeetCode专栏题解，在里面搜对应题号即可 ~
• 大家在浏览时，可以通过下方⬇️按题型分类汇总后的【目录】来实现快速跳转，更方便、更快捷的刷题。
  同时这篇文章我也是我花费了很长的时间，对比多篇文章来总结和编写的，希望对大家有所帮助。
  

文章目录

• • 介绍
  • 一、链表（共11题）
  • • • [2. 两数相加](https://leetcode.cn/problems/add-two-numbers/description/) ★\color{red}{★}★
      • [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/) ★\color{red}{★}★
      • [21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/?favorite=2cktkvj)
      • [23. 合并K个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/description/?favorite=2cktkvj)
      • [141. 环形链表](https://leetcode.cn/problems/linked-list-cycle/?favorite=2cktkvj)
      • [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/description/?favorite=2cktkvj)
      • [148. 排序链表](https://leetcode.cn/problems/sort-list/description/) ★\color{red}{★}★
      • [160. 相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/?favorite=2cktkvj)
      • [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/description/)
      • [234. 回文链表](https://leetcode.cn/problems/palindrome-linked-list/description/) ★\color{red}{★}★
      • ~~[406. 根据身高重建队列](https://leetcode.cn/problems/queue-reconstruction-by-height/?favorite=2cktkvj)~~（middle\color{orange}{middle}middle 题，暂时跳过）
  • 二、二叉树（共14题，含2道 hard\color{red}{hard}hard 题）
  • • • [94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/?favorite=2cktkvj)
      • [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/?favorite=2cktkvj) ★★★\color{red}{★★★}★★★
      • [101. 对称二叉树](https://leetcode.cn/problems/symmetric-tree/description/)
      • [102. 二叉树的层序遍历](https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?favorite=2cktkvj)
      • [104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/)
      • [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/) ★★★\color{red}{★★★}★★★
      • [114. 二叉树展开为链表](https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/?favorite=2cktkvj) ★★★\color{red}{★★★}★★★
      • ~~[124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • [226. 翻转二叉树](https://leetcode.cn/problems/invert-binary-tree/description/?favorite=2cktkvj)
      • [236. 二叉树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/) ★\color{red}{★}★
      • ~~[297. 二叉树的序列化与反序列化](https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • [538. 把二叉搜索树转换为累加树](https://leetcode.cn/problems/convert-bst-to-greater-tree/description/) ★\color{red}{★}★
      • [543. 二叉树的直径](https://leetcode.cn/problems/diameter-of-binary-tree/description/) ★\color{red}{★}★
      • [617. 合并二叉树](https://leetcode.cn/problems/merge-two-binary-trees/?favorite=2cktkvj)
  • 三、DFS/BFS（共6题，含3道 hard\color{red}{hard}hard 题）
  • • • [79. 单词搜索](https://leetcode.cn/problems/word-search/description/) ★\color{red}{★}★
      • ~~[85. 最大矩形](https://leetcode.cn/problems/maximal-rectangle/?favorite=2cktkvj)~~ （hard\color{red}{hard}hard 题，暂时跳过）
      • [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/description/)
      • ~~[207. 课程表](https://leetcode.cn/problems/course-schedule/?favorite=2cktkvj)~~ （hard\color{red}{hard}hard 题，暂时跳过）
      • ~~[301. 删除无效的括号](https://leetcode.cn/problems/remove-invalid-parentheses/description/?favorite=2cktkvj)~~ （hard\color{red}{hard}hard 题，暂时跳过）
      • [437. 路径总和 III](https://leetcode.cn/problems/path-sum-iii/solutions/) ★\color{red}{★}★
  • 四、递归/回溯（共6题，含1道 hard\color{red}{hard}hard 题）
  • • • [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/)
      • [22. 括号生成](https://leetcode.cn/problems/generate-parentheses/description/) ★\color{red}{★}★
      • [39. 组合总和](https://leetcode.cn/problems/combination-sum/description/) ★\color{red}{★}★
      • [46. 全排列](https://leetcode.cn/problems/permutations/?favorite=2cktkvj) ★\color{red}{★}★
      • [78. 子集](https://leetcode.cn/problems/subsets/description/) ★\color{red}{★}★
      • ~~[399. 除法求值](https://leetcode.cn/problems/evaluate-division/description/?favorite=2cktkvj)~~ （hard\color{red}{hard}hard 题，暂时跳过）
  • 五、Hash表/map（共3题）
  • • • [1. 两数之和](https://leetcode.cn/problems/two-sum/description/)
      • [49. 字母异位词分组](https://leetcode.cn/problems/group-anagrams/description/)
      • [128. 最长连续序列](https://leetcode.cn/problems/longest-consecutive-sequence/description/?favorite=2cktkvj)
  • 六、位运算（共3题）
  • • • [136. 只出现一次的数字](https://leetcode.cn/problems/single-number/description/)
      • [338. 比特位计数](https://leetcode.cn/problems/counting-bits/description/)
      • [461. 汉明距离](https://leetcode.cn/problems/hamming-distance/description/)
  • 七、数组（共5题）
  • • • ~~[15. 三数之和](https://leetcode.cn/problems/3sum/description/?favorite=2cktkvj)~~ 待研究
      • [31. 下一个排列](https://leetcode.cn/problems/next-permutation/description/) ★★★\color{red}{★★★}★★★
      • [169. 多数元素](https://leetcode.cn/problems/majority-element/description/)
      • [238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/description/) ★\color{red}{★}★
      • [448. 找到所有数组中消失的数字](https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/description/) ★\color{red}{★}★
  • 八、二分查找（共5题，含1道 hard\color{red}{hard}hard 题）
  • • • [4. 寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/description/) （hard题\color{red}{hard题}hard题）
      • [33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/description/) ★\color{red}{★}★
      • [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/)
      • [240. 搜索二维矩阵 II](https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?favorite=2cktkvj)
      • [287. 寻找重复数](https://leetcode.cn/problems/find-the-duplicate-number/description/) ★★\color{red}{★★}★★
  • 九、栈/单调栈（共6题，含2道 hard\color{red}{hard}hard 题）
  • • • [20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/description/)
      • ~~[42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/?favorite=2cktkvj)~~ （hard\color{red}{hard}hard 题，暂时跳过）
      • ~~[84. 柱状图中最大的矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram/?favorite=2cktkvj)~~ （hard\color{red}{hard}hard 题，暂时跳过）
      • [155. 最小栈](https://leetcode.cn/problems/min-stack/description/)
      • [394. 字符串解码](https://leetcode.cn/problems/decode-string/description/) ★\color{red}{★}★
      • [739. 每日温度](https://leetcode.cn/problems/daily-temperatures/description/) ★\color{red}{★}★
  • 十、排序（共4题）
  • • • [56. 合并区间](https://leetcode.cn/problems/merge-intervals/description/?favorite=2cktkvj) ★\color{red}{★}★
      • [215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/description/) ★★★\color{red}{★★★}★★★
      • [347. 前 K 个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/description/) ★\color{red}{★}★
      • ~~[581. 最短无序连续子数组](https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/description/?favorite=2cktkvj)~~（middle\color{orange}{middle}middle 题，暂时跳过）
  • 十一、前缀和（共1题）
  • • • [560. 和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/description/)
  • 十二、字典树/前缀树（共1题）
  • • • [208. 实现 Trie (前缀树)](https://leetcode.cn/problems/implement-trie-prefix-tree/description/)) ★★★\color{red}{★★★}★★★
  • 十三、LRU缓存（共1题）
  • • • [146. LRU 缓存](https://leetcode.cn/problems/lru-cache/?favorite=2cktkvj) ★★★\color{red}{★★★}★★★
  • 十四、双指针（共3题）
  • • • [11. 盛最多水的容器](https://leetcode.cn/problems/container-with-most-water/description/)
      • [75. 颜色分类](https://leetcode.cn/problems/sort-colors/description/)
      • [283. 移动零](https://leetcode.cn/problems/move-zeroes/description/) ★\color{red}{★}★
  • 十五、动态规划（共23题，含6道 hard\color{red}{hard}hard 题）
  • • • ~~[10. 正则表达式匹配](https://leetcode.cn/problems/regular-expression-matching/description/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • ~~[32. 最长有效括号](https://leetcode.cn/problems/longest-valid-parentheses/description/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/description/)
      • [62. 不同路径](https://leetcode.cn/problems/unique-paths/description/)
      • [64. 最小路径和](https://leetcode.cn/problems/minimum-path-sum/?favorite=2cktkvj)
      • [70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/description/)
      • ~~[72. 编辑距离](https://leetcode.cn/problems/edit-distance/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/description/)
      • [121. 买卖股票的最佳时机](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/)
      • [139. 单词拆分](https://leetcode.cn/problems/word-break/?favorite=2cktkvj)
      • ~~[152. 乘积最大子数组](https://leetcode.cn/problems/maximum-product-subarray/description/?favorite=2cktkvj)~~（middle\color{orange}{middle}middle 题，暂时跳过）
      • [198. 打家劫舍](https://leetcode.cn/problems/house-robber/description/)
      • ~~[337. 打家劫舍 III](https://leetcode.cn/problems/house-robber-iii/description/?favorite=2cktkvj)~~（middle\color{orange}{middle}middle 题，暂时跳过）
      • [221. 最大正方形](https://leetcode.cn/problems/maximal-square/description/)
      • [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/description/) ★\color{red}{★}★
      • [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/description/)
      • [309. 最佳买卖股票时机含冷冻期](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/?favorite=2cktkvj)
      • ~~[312. 戳气球](https://leetcode.cn/problems/burst-balloons/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • [322. 零钱兑换](https://leetcode.cn/problems/coin-change/description/) ★\color{red}{★}★
      • ~~[416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/?favorite=2cktkvj)~~（middle\color{orange}{middle}middle 题，暂时跳过）
      • [494. 目标和](https://leetcode.cn/problems/target-sum/description/) ★\color{red}{★}★
      • [647. 回文子串](https://leetcode.cn/problems/palindromic-substrings/description/?favorite=2cktkvj) ★★\color{red}{★★}★★
      • [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/description/)
  • 十六、滑动窗口（共4题，含2道 hard\color{red}{hard}hard 题）
  • • • [3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/) ★★★\color{red}{★★★}★★★
      • ~~[76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/description/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • ~~[239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/?favorite=2cktkvj)~~（hard\color{red}{hard}hard 题，暂时跳过）
      • [438. 找到字符串中所有字母异位词](https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?favorite=2cktkvj) ★\color{red}{★}★
  • 十七、贪心（共1题）
  • • • [55. 跳跃游戏](https://leetcode.cn/problems/jump-game/description/)
  • 十八、数学（共1题）
  • • • [48. 旋转图像](https://leetcode.cn/problems/rotate-image/solutions/?favorite=2cktkvj) ★\color{red}{★}★
  • 十九、其它（共2题，含1道 力扣VIP专属\color{red}{力扣VIP专属}力扣VIP专属 题）
  • • • ~~[253. 会议室 II](https://leetcode.cn/problems/meeting-rooms-ii/?favorite=2cktkvj)~~（力扣VIP专属\color{red}{力扣VIP专属}力扣VIP专属 题，暂时跳过）
      • ~~[621. 任务调度器](https://leetcode.cn/problems/task-scheduler/solutions/?favorite=2cktkvj)~~（middle\color{orange}{middle}middle 题，暂时跳过）

一、链表（共11题）

2. 两数相加 ★\color{red}{★}★

注意分别处理 【相同数位上的两数之和 val1 + val2，并加上上一轮新产生的进位值 carry：sum = val1 + val2 + carry】 与 【这一轮新产生的进位值 carry = carry / 10】。

并且当两链表 l1 和 l2 都遍历完后，记得额外处理最后的一次进位。例如：99+9=108，这里需要单独处理百位最后的1。

19. 删除链表的倒数第 N 个结点 ★\color{red}{★}★

• 注意先创建虚拟头节点 dummy ，防止删除后链表为空的情况
  • 如果我们能得到倒数第n个节点的前驱节点而不是倒数第n个节点，那么删除操作会更加方便。因此我们可以考虑在初始时将 fast和 slow两个指针指向哑节点 dummy，其余操作不变。这样一来，当 fast遍历到链表末尾时，slow的下一个节点就是我们需要删除的节点。
• 快指针先走n步，然后快指针和慢指针再每次各走一步
• 删除倒数第n个节点：slow.Next = slow.Next.Next，注意不是slow.Next = fast
• 最后返回虚拟头节点的后继节点：dummy.Next

21. 合并两个有序链表

两种方法：递归 和 迭代 。

23. 合并K个升序链表

在 21. 合并两个有序链表 的基础上，遍历链表数组即可

有两个细节需要特别注意：

• 在方法 mergeKLists()中，初始化链表时，采用如下写法：

    var res *ListNode// res := &ListNode{} // 错误写法，会初始化res为0值，导致结果集多一个0值for i := 0; i < len(lists); i++ {res = mergeTwoLists(res, lists[i])}

• 而在方法 mergeTwoLists()中，初始化虚拟节点 head时，则为：

	// var head *ListNode // 错误写法 会空指针异常head := &ListNode{}cur := head...return head.Next

141. 环形链表

判断快慢指针是否相遇（快指针两步，慢指针一步）

142. 环形链表 II

先判断快慢指针是否相遇（快指针两步，慢指针一步），若相遇则将快指针重置到头结点，然后快慢指针每次各走一步，直至相遇

148. 排序链表 ★\color{red}{★}★

题目要求时间复杂度为：O(NlogN)，故采用归并排序的思想（拆分→排序→合并）

• 先通过快慢指针找到链表中点，并切割为前后两部分
• 不断递归上述过程，直至最终将链表切割为多个长度为1的链表
• 最后不断合并这多个长度为1的链表

160. 相交链表

用双指针pA 、pB分别遍历两个链表，pA对链表A遍历结束后就去遍历链表B，pB对链表B遍历结束后就遍历链表A。当 pA == pB 时，相遇节点即为交点，因为两个指针分别移动的步数是一样的。

206. 反转链表

注意go中要用该方式初始化 var pre, mid, end *ListNode = nil, head, nil，而不是 pre, mid, end := &ListNode{}, head, &ListNode{}，否则会在反转后的尾节点添加值为0的 “空节点”，导致错误

234. 回文链表 ★\color{red}{★}★

先找链表中点，划分为前半部分和后半部分；再反转后半部分链表；最后将两部分链表的节点逐个比较

406. 根据身高重建队列（middle\color{orange}{middle}middle 题，暂时跳过）

二、二叉树（共14题，含2道 hard\color{red}{hard}hard 题）

94. 二叉树的中序遍历

• 递归 or 迭代（利用栈的先进后出特性），必会

98. 验证二叉搜索树 ★★★\color{red}{★★★}★★★

利用二叉搜索树的中序遍历为升序序列这一性质，来递归验证。

方法一：官方题解 通过限制每个子树中的上下界（lower和upper）来判断，需额外引入常量：math.MinInt64, math.MaxInt64，不推荐，也没必要。

方法二：双指针比较法（pre和node），参考 B站视频题解，不需额外引入常量，而只需通过一个pre指针，在向上回溯的过程中，不断保存之前的节点用于比较。

• 首先【不断向左子树递归】直至最后空节点：left := dfs(node.Left)
• 然后再自底向上【回溯】的过程中，pre每次保存的都是之前上一层栈空间中的根节点，并不断将当前node节点和pre节点的值做比较：if pre != nil && node.Val <= pre.Val { return false }
  • 当 node = root 时，pre = root.Left，pre的值应永远小于node的值（满足二叉搜索树中，左子节点值 < 根节点值）
  • 当 node = root.Right时，pre = root，pre的值应永远小于node的值（满足二叉搜索树中，根节点值 < 右子节点值）
• 保存当前节点node到pre中，用于下层递归中做比较
• 然后不断向右子树递归：right := dfs(node.Right)
• 最后返回：return left && right，判断当前节点的左右子树是否分别是二叉搜索树

101. 对称二叉树

递归判断：

• if 左节点和右节点均为空，说明遍历完了，返回 true
• 否则说明左右两个节点并非同时为空，那么判断：if 左节点和右节点其中一个为空（也就是一个为空，一个非空，那肯定不对称），或者左节点值不等于右节点值（不对称），返回 false

最后继续递归下探：
return recur(左节点的左子节点，右节点的右子节点) && recur(左节点的右子节点，右节点的左子节点)

关于递归，看到该题讨论区有一个评论，对于递归的理解很有帮助，特意截图留念。

102. 二叉树的层序遍历

BFS层序遍历使用 queue 队列（先进先出）

• 初始化队列，并将根节点 root入队
• 判断队列大小是否非零，非零则进入外层for循环

  • 由于需要按层返回二维数组结果集，因此要提前缓存当前这一层的节点数 length := len(queue)，并创建用于保存这一层结果的临时数组 subRes。

    进入内循环 for i := 0; i < length; i++ {

    • 获取队头节点 root = queue[0]，将其 root.Val值保存到临时数组 subRes中，再将该节点出队（它的使命已完成）
    • 将 root的非空左子节点 root.Left和非空右子节点 root.Right入队

  • 将保存当前这一层结果集的临时数组 subRes追加到二维数组 res中

• 返回保存最终结果集的二维数组 res

104. 二叉树的最大深度

105. 从前序与中序遍历序列构造二叉树 ★★★\color{red}{★★★}★★★

推荐掌握递归法，迭代法比较难理解，不过都需要作图理解和推敲：左右子树分别在 前序/中序 遍历中的左右边界。具体代码可参考：我的题解

递归法：
先通过遍历inorder数组，找到根节点（值为preorder[0]）位于中序遍历中的下标位置 i。然后，根据中序遍历中根节点的下标位置 i，分别构建root的左右子树 …

• 1 分别确定"左子树"在前序和中序遍历中的左右边界
  • 1.1 确定前序遍历中左子树的左右边界：
    • root = preorder[0]是根节点，所以前序遍历中左子树的左边界是1；
    • 然后根据根节点在中序遍历中的下标 i，可知【中序遍历中左子树的范围是0~ i】，由此可确定中序遍历中左子树的长度是len(inorder[:i])，又因为前序遍历中左子树的左边界为1，所以可得前序遍历中左子树的右边界为：len(inorder[:i])+1
  • 确定中序遍历中左子树的左右边界：由上面的分析中的【中序遍历中左子树的范围是0~ i】可得：inorder[:i]

最后可得：root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])

• 2 分别确定"右子树"在前序和中序遍历中的左右边界
  • 2.1 确定前序遍历中右子树的左右边界：
    • 由 1.1 可知当前左子树的长度是len(inorder[:i])，且根节点也占一个位置，因此可得前序遍历中右子树的左边界为：len(inorder[:i])+1，右子树右边界一直到preorder末尾
  • 2.2 确定中序遍历中右子树的左右边界：
    由于之前已经找出根节点位于中序遍历中的下标位置是 i，所以 i+1就是中序遍历中右子树的左边界，右边界一直到inorder末尾

最后可得：root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])

迭代法：
preorder第一个元素为root，在inorder里面找到root，在它之前的为左子树（长l1），之后为右子树（长l2）。preorder[1]到preorder[l1]为左子树,之后为右子树，分别递归。

主要难点在于需要分别确定前序遍历和中序遍历中的左右子树的左右边界对应关系。。。

114. 二叉树展开为链表 ★★★\color{red}{★★★}★★★

• 方法1：先前序遍历 获得各节点被访问到的顺序，然后更新每个节点的左右子节点的信息，将二叉树展开为单链表。
• 方法2：没理解这个递归逻辑，继续研究

124. 二叉树中的最大路径和（hard\color{red}{hard}hard 题，暂时跳过）

226. 翻转二叉树

236. 二叉树的最近公共祖先 ★\color{red}{★}★

求最小公共祖先，需要从底向上遍历。那么二叉树 只能通过后序遍历（即：回溯）实现从底向上的遍历方式。附上一个LeetCode评论区大佬图解，方便理解：

297. 二叉树的序列化与反序列化（hard\color{red}{hard}hard 题，暂时跳过）

538. 把二叉搜索树转换为累加树 ★\color{red}{★}★

以 反中序遍历（右中左）的方式不断累加并更新每个节点值即可

543. 二叉树的直径 ★\color{red}{★}★

【前序遍历】思想：任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

617. 合并二叉树

可用两种方式操作树：原地修改 or 新建树，可参考：我的题解

三、DFS/BFS（共6题，含3道 hard\color{red}{hard}hard 题）

部分二叉树相关题目也包含DFS/BFS

79. 单词搜索 ★\color{red}{★}★

遍历二维数组，在过程中遍历过的格子标记为空格 ' '，但要记得，在最后回溯时将之前被标记过的格子恢复为原字符，避免当前递归结果影响到其他递归过程。

该题与 剑指 Offer 12. 矩阵中的路径 相同

85. 最大矩形 （hard\color{red}{hard}hard 题，暂时跳过）

200. 岛屿数量

遍历二维数组，以 grid[i][j] == 1的格子为起点，开始向其 上下左右 dfs遍历，并在遍历过程中将遍历过为1的格子标记为 ‘0’，避免重复遍历。

注意 79题和200题很相似，都需遍历二维数组的网格：

• 但是上面第79题中，每个网格中的字符是可以复用的，用于组成新的单词。所以需要将被标记过的网格进行回溯处理，恢复为标记前的值，避免当前递归结果影响到其他递归过程。
• 而该题则略有不同，这里每个网格在遍历完后，标记为 ‘0’（水），由于仅统计连接的陆地数，后续不会再复用，因此无需进行回溯的恢复处理。

207. 课程表 （hard\color{red}{hard}hard 题，暂时跳过）

301. 删除无效的括号 （hard\color{red}{hard}hard 题，暂时跳过）

437. 路径总和 III ★\color{red}{★}★

dfs递归，将每个节点都当做起始的根节点对待

• 该题可以通过在子函数中增加额外入参 【sum累加和】来做加法，通过比较【当前累加和】是否和【目标和】相等： if sum + node.Val == targetSum
• 也可以通过对已有入参 targetSum做减法，来比较【当前节点值】是否和【不断消减的目标和】相等： if node.Val == target

注意：处理中间层逻辑时，即使找到了一条目标路径，也不立即 return，继续找。因为 Node.val 有可能为负数，后续有可能再减为目标和 targetSum。

var res intfunc pathSum(root *TreeNode, targetSum int) int {res = 0 // 务必初始化。多个测试用例时，避免当前结果被后续测试用例的结果覆盖if root == nil {return 0}return dfs(root, targetSum, 0) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}func dfs(node *TreeNode, targetSum, sum int) int {if node == nil {return 0}sum += node.Valif sum == targetSum {res++}dfs(node.Left, targetSum, sum)dfs(node.Right, targetSum, sum)return res
}
// 更多不同种的递归形式，可跳转 CSDN-我的题解 部分（最开始介绍部分有链接）

四、递归/回溯（共6题，含1道 hard\color{red}{hard}hard 题）

17. 电话号码的字母组合

使用map保存按键数字和对应字母的映射关系，然后利用递归去追加各种字母…

22. 括号生成 ★\color{red}{★}★

• 方式1 递归，尝试对括号数做减法。left：【剩余】左括号数；right：【剩余】右括号数
• 方式2 递归，尝试对括号数做加法。left：【已使用】左括号数；right：【已使用】右括号数

可参考：我的题解

39. 组合总和 ★\color{red}{★}★

46. 全排列 ★\color{red}{★}★

• 将每个元素分别都固定一次到首位置上
• 以 p+1为起点，q 为终点的新子数组，再次进行下一层新子数组的递归
  

78. 子集 ★\color{red}{★}★

单看每个元素，都有两种选择：【选入子集】，或【不选入子集】。
考察当前枚举的数，基于选它而继续，是一个递归分支；基于不选它而继续，又是一个分支。
比如[1,2,3]，先看1，选1或不选1，都会再看2，选2或不选2，以此类推…

399. 除法求值 （hard\color{red}{hard}hard 题，暂时跳过）

五、Hash表/map（共3题）

1. 两数之和

49. 字母异位词分组

创建一个map，key为string类型，val为string类型数组。

对给定字符串数组strs中的每个字符串排序，将其排序结果统一作为map的key。并将原本未排序的字符串追加到map的val数组中。目的是通过排序后的key来将字符串数组strs中的字符串str做归类。

128. 最长连续序列

• 首先，将 nums 数组初始化到map中，以便于在O(1)时间内查找元素
• 其次，遍历 nums 数组，判断当前 num 是否能够作为某个连续序列的首元素（也就是 num-1 不存在）
  • 如果当前 num 能作为某个连续序列的首元素：
    那就继续找以当前 num 为首的后续连续序列，并累加当前连续序列的长度 length，并更新最长连续序列的长度 maxLength。
  • 如果当前 num 不能作为某个连续序列的首元素：
    直接跳过，继续找 …
• 返回最长连续序列的长度 maxLength

六、位运算（共3题）

136. 只出现一次的数字

对数组所有元素进行异或^的值就是最终结果。
注：两个值不同，则异或结果为1；两个值相同，异或结果为0。

338. 比特位计数

461. 汉明距离

在x与y 异或 后的二进制结果中，不断右移并判断对应二进制位为1的个数。

七、数组（共5题）

15. 三数之和 待研究

31. 下一个排列 ★★★\color{red}{★★★}★★★

LeetCode题解，评论区一个大佬的解释很通俗易懂，我摘抄了过来。先看下举例，再结合代码可能更容易理解解题思路

一直觉得排列的题目很有趣，终于想通了根据当前排列计算出下一个排列的方法，在这里记录一下。 例如 2, 6, 3, 5, 4, 1 这个排列， 我们想要找到下一个刚好比他大的排列，于是可以从后往前看 我们先看后两位 4, 1 能否组成更大的排列，答案是不可以，同理 5, 4, 1也不可以 直到3, 5, 4, 1这个排列，因为 3 < 5， 我们可以通过重新排列这一段数字，来得到下一个排列 因为我们需要使得新的排列尽量小，所以我们从后往前找第一个比3更大的数字，发现是4 然后，我们调换3和4的位置，得到4, 5, 3, 1这个数列 因为我们需要使得新生成的数列尽量小，于是我们可以对5, 3, 1进行排序，可以发现在这个算法中，我们得到的末尾数字一定是倒序排列的，于是我们只需要把它反转即可 最终，我们得到了4, 1, 3, 5这个数列 完整的数列则是2, 6, 4, 1, 3, 5

首先，这里应该针对 nums数组可能出现的情况分开讨论：

• 第一种 从左至右不包含递增序列的数组（也就是纯递减数组），例如：
  [3, 2, 1]的下一个排列是 [1, 2, 3]，因为 [3, 2, 1] 不存在一个字典序更大的排列。
• 第二种 从左至右包含递增序列的数组，细分的话有三种情况，但我们只关心 下一个更大的排列，这里逻辑上实则可以合并无需细分处理，分别举几个示例：
  • 从左至右一直递增的数组，[1,2,3]的下一个排列是 [1,3,2]
  • 先递增后递减的数组，[2,3,1]的下一个排列是 [3,1,2]
  • 先递减后递增的数组，[3,1,2]的下一个排列是 [3,2,1]

这里需要对以上两种可能出现的数组分情况处理：

• 第一步：从后向前 循环遍历数组，找到第一个满足条件 nums[i] < nums[j]的下标 i，j。
  注：当然对于第一种从左至右不包含递增序列的数组（也就是纯递减数组），是找不到题目要求的 下一个更大的排列 的。因为类似 [3,2,1] 这种本身就是字典序最大的排列，是不存在一个字典序更大的排列的。
  因此这里只能在第二种 从左至右包含递增序列的数组 中找到满足条件的下标 i，j了。
  • 继续，若在上述第二种情况中找到了满足条件 nums[i] < nums[j]的下标 i，j（也表明 此时 nums[i]的值是要小于其右边的任意一个数的），那么再次从数组尾元素开始，从后向前找到比当前 nums[i]大的倒数第一个数 nums[k]。交换 nums[i]和 nums[k]的值。
• 第二步：经过上面 第一步 【找到第一个满足条件 nums[i] < nums[j]的下标 i，j】后，此时的 nums[j:len(nums)]这后一段子数组其实是降序的。
  因为在第一步中，跳出第一个for循环之前，一直都是满足条件 nums[i] > nums[j]的，也就是前一个数大于后一个数，为降序。
• 第三步：将上面降序的 后一段子数组 进行反转使其升序，即可得到 下一个排列 ~

具体Golang版代码示例如下：

func nextPermutation(nums []int) {if len(nums) <= 1 {return}i, j, k := len(nums)-2, len(nums)-1, len(nums)-1// 第一步：从后向前 循环遍历数组，试图找到第一个满足条件 nums[i] < nums[j]的下标 i，j// 如果是[3 2 1]这种纯递减数组，i会一直减到-1，就进不去下面的if判断逻辑// 注意：在跳出该for循环前 nums[i] >= nums[j]，就已经能保证nums[j:len(nums)]后半段子数组为【降序】for i >= 0 && nums[i] >= nums[j] {i--j--}// i >= 0 保证不是纯降序排列，避免越界// 再次从数组尾元素开始，从后向前找到比当前 nums[i]大的倒数第一个数 nums[k]，并交换值if i >= 0 {for nums[k] <= nums[i] && k > j {k--}nums[i], nums[k] = nums[k], nums[i]}// 将 “后半段【降序】的子数组” 反转使其升序，即可得到 下一个排列 ~for a, b := j, len(nums)-1; a < b; a, b = a+1, b-1 {nums[a], nums[b] = nums[b], nums[a]}
}

169. 多数元素

常规的 hash表（空间复杂度为O(n)）和 排序算法（时间复杂度为O(nlogn)），都不满足题目的进阶要求：时间复杂度为 O(n)、空间复杂度为 O(1) ，这里不做展开，具体可以参考LeetCode官方题解。

这里学到一种新的算法 摩尔投票法，具体思路如下图，也可以看 我的题解

238. 除自身以外数组的乘积 ★\color{red}{★}★

思路：除自身以外数组的乘积 = 自身的左侧数组 * 自身的右侧数组

题目进阶要求：在 O(1) 的额外空间复杂度内完成这个题目，因此复用待返回的res数组即可

• 初始化 左侧/右侧 数组：res[0], res[len(nums)-1] = 1, 1
• 处理左侧数组乘积：res[i] = res[i-1] * nums[i-1]
• 处理右侧数组乘积：用一个变量 r 来跟踪右边元素的乘积，并初始化为1。然后内部循环中不断更新 res 和 r 的值：res[i] = res[i] * r ，r *= nums[i]

此外，注意边界条件的处理即可。

448. 找到所有数组中消失的数字 ★\color{red}{★}★

题目进阶要求：在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题。

因此这里不考虑使用 hash表 来统计次数的方法，而是使用数组元素标记法，具体如下：
本质上是把原数组上对应index的值取负来标识某个值是否出现过，最后再次遍历标识过的数组找出其中非负的元素，其对应 【下标+1】 即为消失的数字。

八、二分查找（共5题，含1道 hard\color{red}{hard}hard 题）

4. 寻找两个正序数组的中位数 （hard题\color{red}{hard题}hard题）

• 方法1 先将两个数组有序合并至新数组中，然后根据奇偶情况返回中位数。较简单，但时间复杂度不满足题目要求的 O(log (m+n))。
  时间复杂度 O(m+n)，空间复杂度 O(m+n)
• 方法2 先找到中位数可能的下标值 left 和 right，然后遍历数组得到nums[left], nums[right]，再根据奇偶情况返回中位数。较复杂，对于奇偶情况的判断逻辑容易出错，且时间复杂度不满足题目要求的 O(log (m+n))。
  时间复杂度 O(m+n)，空间复杂度：O(1)
• 方法3 二分法 待研究\color{red}{待研究}待研究
  时间复杂度 O(log (m+n))，空间复杂度：O(1)

33. 搜索旋转排序数组 ★\color{red}{★}★

此题运用二分法的特殊变种情况来区分：

• if nums[mid] == target
• if nums[left] <= nums[mid]，mid的左侧是单调递增区间
  • if nums[left] <= target && target < nums[mid]
    • right = mid - 1
  • else
    • left = mid + 1
• else /*if nums[left] > nums[mid]*/，mid的左侧不是单调递增区间，说明右侧是单调递增区间
  • if nums[mid] < target && target <= nums[right]
    • left = mid + 1
  • else
    • right = mid - 1

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

如果在nums中找到了一个target，则继续在此基础上有两种处理方式：

• 方式1：通过左右滑动指针，来找到符合题意的区间
• 方式2（推荐）：继续用二分法分别查找左右边界，而不是用左右滑动指针来逐个遍历

240. 搜索二维矩阵 II

题目给出 m x n 矩阵从左到右升序排列，从上到下升序排列。

因此以矩阵右上角的元素 nums[i][j)]为起点，若target小于当前值，则j--，若target大于当前值则i++。
时间复杂度O(m+n)：i 最多能被增加 m 次，j 最多能被减少 n 次，总搜索次数为 m+n

另外此题的更优解是 二分法查找 …

287. 寻找重复数 ★★\color{red}{★★}★★

二分法查找：
每一次找中间值，考虑到1-n之间的数一定都会出现，如果非重复情况下每个数只会出现一次，故我们判断小于等于中间值元素个数如果超过了中间值则说明重复的数在左半边，否则去右半边找。（注意：这里的左半边和右半边，是指非重复情况下的有序数组的左右两侧）

具体可参考：我的题解

九、栈/单调栈（共6题，含2道 hard\color{red}{hard}hard 题）

20. 有效的括号

创建辅助栈，利用 栈 先进后出的特性来对每组括号进行匹配

42. 接雨水 （hard\color{red}{hard}hard 题，暂时跳过）

84. 柱状图中最大的矩形 （hard\color{red}{hard}hard 题，暂时跳过）

155. 最小栈

空间换时间的思想，分别构建 数据栈 stack 和 最小栈 minStack（辅助栈），使得能在常数时间内检索到最小元素的栈。

主要注意push操作即可。

394. 字符串解码 ★\color{red}{★}★

外层的解码需要等待内层解码的结果。先扫描的字符还用不上，但不能忘了它们。
我们准备由内到外，层层解决[ ]，需要保持对字符的记忆，于是用栈。

需要两个栈来记录外层字符串的状态：倍数栈 numStack、字符串栈 strStack
创建几个变量：result不断追加每一层新得到的子串，str保存每一层的子串，num保存每一层的倍数

遍历字符串s，每次得到的字符c存在以下几种情况：

• c >= ‘0’ && c <= ‘9’：处理当前层倍数
  获取每一层子串要重复的倍数：例如 12[ab]，那么就需要获取到12(1*10+2)这个完整的数字
• c == ‘[’：分别保存外层 倍数 及 子串 到栈中，准备进入下一层
  将上一层的 result和 num分别入栈保存，并清空对应记录，避免干扰下一层 result和 num的统计
• c == ‘]’：内外层拼接
  处理完当前层，获取栈顶数据，并将外层及当前层字符串相拼接
• c >= ‘a’ && c <= ‘z’：处理当前层子串
  不断追加每层的 result结果：例如ab[…]，那么就要拼接获取到这一层ab这个完整的字符串

739. 每日温度 ★\color{red}{★}★

思路 参考LeetCode视频题解 - 单调栈 ：

• 创建单调栈（递减）
• 外部for循环，遍历 temperatures数组
  • ① 内部for循环：
    若栈非空len(stack) > 0，且【当前第 i天的温度 temperatures[i]> 栈顶第 stack[len(stack)-1]天所对应的温度 temperatures[stack[len(stack)-1]】，直接求出二者的下标差（天数差值）就可得到 下一个更高温度出现在几天后，将结果保存到结果数组res中：res[stack[len(stack)-1]] = i - stack[len(stack)-1]，并将栈顶元素出栈。
    循环处理该过程，继续看新的栈顶元素，直到不满足上述条件时而退出内部for循环。因为当前温度 temperature[i]可能大于之前早已入栈的多个温度，需逐个处理…
  • ② 若由于不满足上述条件而退出内部for循环，则表示 当前栈为空 或 当前温度 temperatures[i]<= 栈顶第 stack[len(stack)-1]天所对应温度 temperatures[stack[len(stack)-1]]，那么直接将当天的下标 i入栈。

注意：①②两种情况并不是互斥关系，无需 if-else 处理，直接写逻辑即可。

这样就可以一直保持单调递减栈，且每个元素和后面第一个大于它的元素的距离天数也可以算出来。

十、排序（共4题）

56. 合并区间 ★\color{red}{★}★

• 先对二维数组下的所有一维数组的首元素（左边界）进行升序排序，使每个一维子数组的左边界为升序排列：
  sort.Slice(intervals, func(i, j int) bool {
  return intervals[i][0] < intervals[j][0]
})
  避免后面合并时出现无序的 intervals数组，例如：[[1,4],[0,4]]，导致合并结果出错为：[1,4]而非[0,4]
• 遍历题目给定的二维数组 for i := 1; i < len(intervals); i++ {，然后合并区间（经过上面排序后，此时每个一维子数组的左边界都已是升序排列。在此前提下，我们只需再比较每个一维子数组的右边界并判断是否能合并即可）：
  • 可合并：若前一个区间右边界 >= 后一个区间左边界，则可将前一个区间 intervals[i-1]合并到当前区间 intervals[i]中。另外，还要注意比较并选择前后区间中较大的右边界作为合并后 intervals[i]的右边界。
    当前新合并后的区间将继续作为下一轮遍历中的 前一个区间 。
  • 无法合并：若前一个区间右边界 < 后一个区间左边界，则无法合并，直接追加【前一个区间】到结果集 res中
• 最后，要追加 intervals的最后一个元素到结果集 res中：因为在之前每次的循环中，append的是前一个区间，导致 intervals的最后一个区间一直没来得及添加到结果集数组 res中

215. 数组中的第K个最大元素 ★★★\color{red}{★★★}★★★

利用快排 或 堆排（小顶堆时间复杂度更优），具体参考 我的题解

347. 前 K 个高频元素 ★\color{red}{★}★

方法1 内置排序法：

• 利用map统计每个元素出现频次：key = num, val = cnt
• 将map中的key加入新数组 res 中，也就是对nums去重后的数组集
• 根据map中【出现频次cnt】对【去重后的res数组】排序，返回前k个

 sort.Slice(res, func(i, j int) bool {return m[res[i]] > m[res[j]]})

方法2 小顶堆：

前面对元素出现频次的统计和上面方法1一样。
接下来是利用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

那为什么不能用大顶堆呢？
你想啊，如果定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把当前最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。

581. 最短无序连续子数组（middle\color{orange}{middle}middle 题，暂时跳过）

十一、前缀和（共1题）

560. 和为 K 的子数组

双层循环计算累加值。

注意：即使当前累加值与目标值相等（sum == k），也不能提前break退出循环，因为测试用例可能给出负数。
比如：nums = [1,-1,0]，k = 0，有三种符合的子数组：[1, -1]、[0]、[1,-1,0]，注意最后一种 1 + (-1) + 0 = 0 也是满足题目要求的子数组，因此不能提前break结束循环。

十二、字典树/前缀树（共1题）

208. 实现 Trie (前缀树)) ★★★\color{red}{★★★}★★★

前缀树：

• 功能优点：用于高效地存储和检索字符串数据集中的键
• 应用场景：搜索引擎、自动补全、拼写检查、Golang Gin web框架。

前缀树节点的结构体类型：

type Trie struct {child  [26]*Trie // 26叉树，注意是指针类型isEnd bool       // 标记当前节点是否是一个完整单词的末尾位置
}

每个方法中，都有一个对应的 this指针，通过移动这个 this指针，可以实现对 新字符串的插入 与 旧字符串的查找。

另外注意：
Search(word string)和 StartsWith(prefix string)方法虽然类似，但是也有区别。

• Search()方法是用于查找完整 word 单词的，所以最后需要额外判断下 this.isEnd是否为 true。
• 而 StartsWith()只要匹配到 prefix 前缀即可，不需要是完整的单词，所以不需要额外判断 this.isEnd是否为 true。

十三、LRU缓存（共1题）

146. LRU 缓存 ★★★\color{red}{★★★}★★★

// LRUCache缓存结构体类型
type LRUCache struct {cap        inthead, tail *Nodem          map[int]*Node
}

先解释下结构体 LRUCache 的各个字段：

• 创建 head和 tail（这两个虚拟节点不存真实数据）原因：
  仅用于标记双向链表的首尾位置，使得在【加入新节点】和【删除旧节点】可通过 head和 tail更方便操作
• 使用map原因：
  • Get()和 Put()需要根据入参key，从map中查找和更新对应节点信息，且以 O(1) 平均时间复杂度运行
  • map的另一个作用是避免加入重复的key到链表中去，可以对key去重

另外 补充一点：将一个活跃节点移动到链表头部可以拆分为两步：moveToHead()=deleteNodeFromList()+addNodeToHead()

十四、双指针（共3题）

11. 盛最多水的容器

设置双指针 i， j 分别位于容器壁两端。那么为了获取到更大的面积，i 和 j 中较短的一边向中间靠拢（才有可能获取到更大的面积），直至 i 和 j 相遇。

75. 颜色分类

荷兰国旗 问题：0（红），1（白），2（蓝） 排序。
起初 left和 right分别指向数组的首尾元素，遍历数组 for i <= right。
注意循环条件：原本是 i <= len(nums)，但 right 指针右侧已经都是2了，没必要继续寻找。因此以越过右指针为终止条件，减少查找次数。
继续判断 nums[i]的值：

• 若是 0，则移动到表头：swap(nums[i], nums[left])，left++，i++
• 若是 2，则移动到表尾：swap(nums[i], nums[right])，right--。
  注意：这里不用 i++，因为 nums[right])交换到 nums[i]上的数还没有验证（有可能是0或2），所以 i 不用右移。
• 若是 1 则继续：i++

283. 移动零 ★\color{red}{★}★

定义 双指针 left，right。left左侧的数都是非零值，而right则不断的右移以跟踪0值。
如果nums[right] != 0 则left和right都右移，并且left和right对应值交换；反之则仅仅right右移即可。

十五、动态规划（共23题，含6道 hard\color{red}{hard}hard 题）

10. 正则表达式匹配（hard\color{red}{hard}hard 题，暂时跳过）

32. 最长有效括号（hard\color{red}{hard}hard 题，暂时跳过）

53. 最大子数组和

• 动态规划 方式1：
  判断 dp[i] = dp[i-1] + nums[i]中，dp[i-1]是起到 正向作用还是负向作用
  也就是判断 nums[i]是否要加上之前的前缀和 dp[i-1]，有两种情况：

  • 当 dp[i-1] > 0 对最大子数组和起正向作用时，则可以加上之前的dp[i-1]；
  • 反之 当 dp[i-1] < 0 对最大子数组和起负向作用时，则不加

• 动态规划 方式2（方式1的优化版）：
  其实上述方式并不是最优的，因为每次遍历我只需要判断之前的 dp[i-1]的正负即可，所以可以用一个变量 pre来代替和复用，并不需要额外构造dp数组。这样空间复杂度可降至O(1)。

62. 不同路径

创建长宽分别为 m+1，n+1 的dp数组用于记录不同的路径数
注意初始化时以下任意方式都ok：

• dp[0][1] = 1，从上到下，dp[0][1] → dp[1][1]
• 或者 dp[1][0] = 1，从左到右，dp[1][0] → dp[1][1]

其中，dp[1][1]对应原有矩阵的 [0][0] 位置，也就是机器人的起始位置
从 dp[1][1]起始位置出发，机器人每次只能向下或者向右移动一步，可得到递推方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

64. 最小路径和

搜索的做法仅仅在数据规模比较小的时候才考虑使用，因为复杂度较高，所以采用dp。由于每个元素对应的最小路径和与其相邻元素（当前点的上面或左面）对应的最小路径和有关，因此可以使用动态规划求解。

在原有grid数组上进行原地修改，空间复杂度为 O(1)

• 当 i == 0 && j == 0，即位于 原点(0,0) 时，不做任何处理
• 当 i == 0时，即当前点位于 最上边一行 时：只能从原点向右移动，从"左"边过来
• 当 j == 0时，即当前点位于 最左边一列 时：只能从原点向下移动，从"上"边过来
• 其余情况，当前点既不在最上面一行，也不在最左边一列，此时选取其上或其左位置点中的较小值
• 最终返回 dp[m-1][n-1]

此题也可以采用递归处理，可以参考 我的题解，不过相比dp更复杂和难以理解。

70. 爬楼梯

三种方法，劣 → 优：

• 方法1 递归法：时间复杂度较高，不推荐
• 方法2 动态规划：时间复杂度O(n)，空间复杂度：O(n)
• 方法3 动态规划 优化版：在动态规划的基础上进行优化，空间复杂度：O(1)
  由于当前结果只跟 n-1 和 n-2 项有关，故只需缓存这两个变量即可，不需要使用方法2的dp数组缓存整个遍历结果

72. 编辑距离（hard\color{red}{hard}hard 题，暂时跳过）

96. 不同的二叉搜索树

动态规划

• 创建dp数组，初始化：
  dp[0] = 1（空树）, dp[1] = 1（单节点树）
• 双层循环
  • i表示当前想要表示的节点总数，从 2 递增至 n
  • j表示当前一共有 i个节点时，其左子树可能的节点数
    • 递推方程：dp[i] += dp[j]*[i-1-j]，前一项 dp[j]是左子树可能出现的种数，后一项 dp[i-j-1]是右子树可能出现的种数，注意 根节点也占 1 个数量
• 返回 dp[n]即可

121. 买卖股票的最佳时机

此题可以看做一种动态规划，只不过对空间复杂度进行了优化。

考虑每次如何获取最大收益？第 i 天的最大收益只需要知道前 i 天的最低点就可以算出来了。而第 i 天以前（包括第i天）的最低点和 i - 1 天的最低点有关，至此我们的动态方程就出来了：dp[i] = min(d[i-1], prices[i])。

其中 dp[0] = prices[0]，然后动态计算之后的就可以了。 得到了前 i 天的最低点以后，只需要维护一个 max 用来保存最大收益就可以了。 这个时候是空间复杂度 O(n) 的动态规划，代码如下：

// 动态规划 版本1（优化前，空间复杂度：O(n)）
func maxProfit(prices []int) int {n, maxProfitVal := len(prices), 0// dp[i]表示截止到第 i 天，股票价格的最低点是多少 // dp[i] = min(dp[i-1], nums[i])dp := make([]int, n)dp[0] = prices[0]for i := 1; i < n; i++ {dp[i] = min(dp[i - 1], prices[i])maxProfitVal = max(maxProfitVal, prices[i] - dp[i])}return maxProfitVal
}

接着考虑优化空间，仔细观察动态规划的辅助数组，其每一次只用到了 dp[i - 1] 这一个空间，因此可以把数组改成单个变量 dp 来存储截止到第 i 天的价格最低点。优化后的代码如下：

// 动态规划 版本2（版本1基础上优化后）
// 使用变量 minPrice 保存当前遍历过的股价最低价格，替代之前的dp数组，空间复杂度：O(1)
func maxProfit(prices []int) int {minPrice, maxProfitVal := prices[0], 0 // 股价最低价格，最大利润for i := 1; i < len(prices); i++ {maxProfitVal = max(maxProfitVal, prices[i] - minPrice)minPrice = min(minPrice, prices[i])}return maxProfitVal
}

139. 单词拆分

借助 map 来实现在 O(1) 时间复杂度内判断当前子串是否在字典 wordDict 中。
通过 j，i下标来标记当前遍历到的子串的左右边界，得到当前的子串 subStr = s[j:i]。

判断该子串是否在字典 wordDict 中出现，并且在这之前以 j结尾的子串 dp[j]是否也为 true。同时满足这两个条件，则表明当前遍历到的子串 subStr = s[j:i]是可以正常进行单词拆分的，记为 true。

具体示例代码如下：

func wordBreak(s string, wordDict []string) bool {// 初始化单词map，用于判断当前遍历到的子串是否在wordDict中出现过wordMap := make(map[string]bool)for _, word := range wordDict {wordMap[word] = true}n := len(s)dp := make([]bool, n + 1)dp[0] = true // 边界条件，dp[0]=true 表示空串且合法// i表示子串的结束位置for i := 1; i <= n; i++ {// j表示子串的开始位置for j := 0; j <= i/*j < i*/; j++ {subStr := s[j:i]if wordMap[subStr] && dp[j] {dp[i] = true// break}}}return dp[n]
}

152. 乘积最大子数组（middle\color{orange}{middle}middle 题，暂时跳过）

198. 打家劫舍

• 动态规划 方法1：优化前 空间复杂度 O(n)
  初始化：dp[0], dp[1] = nums[0], max(nums[0], nums[1])
  递推方程：i从2开始，dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
  返回值：dp[len(nums) - 1]
• 动态规划 方法2：优化后 空间复杂度 O(1)
  上述方法用数组存储结果，考虑到每间房屋的最高总金额只和【该房屋的前两间房屋】的最高总金额相关，因此可以使用滚动数组。在每个时刻只用存储前两间房屋的最高总金额即可，无需额外保存更早的记录。
  初始化：prepre, pre := nums[0], max(nums[0], nums[1])
  递推方程：i从2开始，prepre, pre = pre, max(prepre + nums[i], pre)
  返回值：pre

337. 打家劫舍 III（middle\color{orange}{middle}middle 题，暂时跳过）

221. 最大正方形

遍历二维数组：
先判断当前matrix[i][j]值是否为1

• 若当前格子值为字符 ‘1’，
  • 且位于 第0行/第0列：则将 dp[i][j]初始化为1（注意这里的边界条件处理）
  • 非 第0行/第0列 时：处理递推方程，
    首先，d[i][j]代表的是 以坐标点 (i,j) 为右下角的正方形最大边长
    由于 以坐标点(i,j) 为【右下角】的正方形最大边长 = min(左, 上, 左上) + 1，故可得递推方程：dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1。这里的 +1：表示右下角的格子本身的边长，也要算上，也参与到组成的最大正方形中。
• 若当前格子值为字符 ‘0’，跳过不作处理

关于此题递推公式的通俗解释：
若某个格子值为 ‘1’，则在以此格为右下角的正方形中，其最大边长为：上方正方形、左方正方形、左上方正方形 中最小的那条边长，最后再加上右下角格子本身的边长 1。

279. 完全平方数 ★\color{red}{★}★

找到 n 之前最大的一个完全平方数 j（j×j<=n），记为一个个数；那么 还剩 n-j×j 需要继续拼凑。也就是说只要将 n-j×j 的解 dp[n-j×j] 加上上面 j×j 所占的那个1，就是n的解，这就是最短的。
注意：此题和【322. 零钱兑换】类似，在初始化时都需要将dp数组所有元素初始化为 n+1，这样递推方程 dp[i] 在取较小值 min 时，才能获取到和为 n 的完全平方数的最少数量 。

300. 最长递增子序列

动态规划 主要逻辑：

• 初始化：子序列一定都是至少包含 nums[i]本身，占一个长度
• 双层循环：外循环控制每轮遍历中的结尾位置为nums[i]，内循环则是不断寻找 i到 j区间内最大的递增子序列长度。
  注意：在内循环（j=0 → j=i）的过程中，dp[i]的值是不断变化的，我们要取的就是这一过程中dp[i]的最大值。
  • 递推方程：dp[i] = max(dp[i], dp[j] + 1)，其中 dp[i]表示：以 nums[i]为结尾的最长递增子序列的长度，且 nums[i]本身也占一个长度，因此加上1。
• 返回值：注意最后不能返回 dp[n-1]，因为最长递增子序列不一定就包含最末尾的元素，而是需要在循环中不断比较并保存在res结果遍量中的。

309. 最佳买卖股票时机含冷冻期

这道题可以参考我博客中的题解，状态比较多，比较容易出错。

312. 戳气球（hard\color{red}{hard}hard 题，暂时跳过）

322. 零钱兑换 ★\color{red}{★}★

双层循环，外循环表示待拼凑的 amount 数，内层循环表示可选的硬币数（两层循环倒过来也ok，反正是求最少的硬币个数，并不是硬币的 无序组合 或 有序排列）。

注意，由于递推方程是求最小值min，所以初始dp数组时应该将其中所有元素初始化为大于amout的任意数字，比如：amount + 1，这样才能获取到凑成当前amount的最小硬币数。

 if i >= coins[j] {// +1：代表coins[j]自身所占的一个硬币数dp[i] = min(dp[i], dp[i - coins[j]] + 1)}

416. 分割等和子集（middle\color{orange}{middle}middle 题，暂时跳过）

494. 目标和 ★\color{red}{★}★

这道题用回溯属于easy 难度，用dp得有 hard 难度。
虽然这道题用动态规划来解，时间复杂度和空间复杂度上会更优，但是我没太能理解，所以暂时用的回溯法来做。

回溯法 关键代码：

func dfs(nums []int, target, sum, i int) {// 因为要用到nums数组中的每个元素来构造表达式，因此i最终会等于nums数组的长度// 注意是与len(nums)比较，而不是len(nums) - 1if i >= len(nums) && sum == target { // res++return} else if i >= len(nums) && sum != target {return}dfs(nums, target, sum + nums[k], k+1) // 加一个数dfs(nums, target, sum - nums[k], k+1) // 减一个数
}

647. 回文子串 ★★\color{red}{★★}★★

参考 LeetCode大佬题解

因为回文串是中心对称的，我们可以先枚举子串的中心，然后从中心处向两边探测，直到发现两端字符不相等或者到达字符串边缘。

• s长度为 奇数，中心是单个字符，以 s[i]为中心向两边扩展
• s长度为 偶数，中心是两个字符，以 s[i]、s[i+1]为中心向两边扩展
  
  当然该题也有 动态规划 的方法，但是个人认为以下代码更清晰明了。且因为该题比较具有技巧性，所以加上代码示例，以供参考：

func countSubstrings(s string) int {cnt, length := 0, len(s) for i := 0; i < length; i++ {// 回文串s长度为"奇数"：l, r := i, i // s长度为奇数，中心是单个字符，以s[i]为中心向两边扩展for l >= 0 && r < length && s[l] == s[r] {l--r++cnt++}// 回文串s长度为"偶数"：l, r = i, i + 1 // s长度为偶数，中心是两个字符，以s[i]、s[i+1]为中心向两边扩展for l >= 0 && r < length && s[l] == s[r] {l-- r++cnt++}}return cnt
}

5. 最长回文子串

中心拓展法（个人认为该方法相对于动态规划来讲，更加清晰明了，便于理解）

注：此题可以在上面的 [647. 回文子串] 题的基础上，加上对最长回文子串的逻辑判断 即可。示例代码如下：

func longestPalindrome(s string) string {sLength, maxLength, maxStr := len(s), 0, ""// s长度为奇数，中心是单个字符，以s[i]为中心向两边扩展for i := 0; i < sLength; i++ {l, r := i, i for l >= 0 && r < sLength && s[l] == s[r] {// 通过比较找出更长的最长回文子串tmpLength := r - l + 1if tmpLength > maxLength {maxLength = tmpLengthmaxStr = s[l:r+1]}l--r++}// s长度为偶数，中心是两个字符，以s[i]、s[i+1]为中心向两边扩展l, r = i, i + 1 for l >= 0 && r < sLength && s[l] == s[r] {// 通过比较找出更长的最长回文子串tmpLength := r - l + 1if tmpLength > maxLength {maxLength = tmpLengthmaxStr = s[l:r+1]}l-- r++}}return maxStr
}

十六、滑动窗口（共4题，含2道 hard\color{red}{hard}hard 题）

3. 无重复字符的最长子串 ★★★\color{red}{★★★}★★★

参考 LeetCode视频题解

• 创建左右两个指针，start和 end，end下标不断向右移动。
• 内循环 每次判断当前遍历到的新的 s[end]是否在之前已出现过（即是否重复出现）。
  若出现过，则将 start下标指向之前出现位置的下一个位置，并更新当前不重复子串长度 length = end - start (这里本来应该是 length = end -start + 1，但被合并到了内循环外面的 length++中)。
  这一过程是其实是为了跳过之前的重复字符（比如 abbbc，最终会跳过中间的 bbb）。
• 更新右指针下标 end++和 maxLength = max(maxLength, length)子串的最大长度，且 length++使得不重复子串长度加1。

具体代码如下：

// 方法1-滑动窗口 利用map优化前：
// 时间复杂度：O(n^2)，空间复杂度：O(1)
func lengthOfLongestSubstring(s string) int {// start：不含重复子串的起点；end：不含重复子串的终点；length：当前已匹配不重复子串长度；maxLength：目前已匹配最长子串长度start, end, length, maxLength, sLength := 0, 0, 0, 0, len(s)for end < sLength {cmpChar := s[end]// 过滤重复字符：将cmpChar与s[start:end)的字符逐个比较。比如abbbc，最终会跳过中间的bbbfor i := start; i < end; i++ {if s[i] == cmpChar {start = i + 1        // 若出现重复字符，start跳过重复字符，指向重复字符的下一位置length = end - start // 计算length时外循环中会对length++，所以这里暂时无需+1操作break                // s[start:end]中已经存在相同字符，break退出进行下一轮外循环}}length++ end++ // 扩展右边界maxLength = max(maxLength, length)}return maxLength
}/******************************************************************/// 方法2-滑动窗口 利用map优化后（判断tmpStr在s[start,end)中之前是否已经重复出现过）：
// 时间复杂度：O(n)，空间复杂度：O(n)
func lengthOfLongestSubstring(s string) int {// start：不含重复子串的起点；end：不含重复子串的终点；length：当前已匹配不重复子串长度；maxLength：目前已匹配最长子串长度start, end, length, maxLength, sLength := 0, 0, 0, 0, len(s)lastIndexMap := make(map[byte]int) // 存储已遍历过的字符最后出现的下标位置for end < sLength {cmpChar := s[end]// 仅当当前要遍历的 s[start,end) 中已存在 cmpChar = s[end] 时更新startif lastIndex, ok := lastIndexMap[cmpChar]; ok && lastIndex >= start { start = lastIndex + 1length = end - start} lastIndexMap[cmpChar] = endlength++ end++ // 扩展右边界maxLength = max(maxLength, length)}return maxLength
}func max(a, b int) int {if a > b {return a}return b
}

76. 最小覆盖子串（hard\color{red}{hard}hard 题，暂时跳过）

239. 滑动窗口最大值（hard\color{red}{hard}hard 题，暂时跳过）

438. 找到字符串中所有字母异位词 ★\color{red}{★}★

利用长度为p大小的滑动窗口进行比较

• 首先，获取 sLen = len(s)和 pLen = len(p)，如果 sLen < pLen，直接返回空结果集。
• 然后，创建两个长度为 26 的 int 类型数组 sCntArr和 pCntArr，用作比较【长度为pLen，在字符串s中不断向右滑动的滑动窗口中对应子串】与【给定字符串p】是否是字母异位词。
  初始化这两个数组，并进行 首次比较 ，若相同则向结果集中追加当前滑动窗口的起始位置 0。

	// 初始化这两个数组// 分别统计【在s中滑动的滑动窗口】和【被比较字符串p】中字母出现的次数for i := 0; i < len(p); i++ {pCntArr[p[i] - 'a'] += 1sCntArr[s[i] - 'a'] += 1}// 首次比较if sCntArr == pCntArr {// 字符串s[:pLen]为p的字母异位词res = append(res, 0)}

• 在 后续比较 中，滑动窗口每次从左边滑出一个扫描过的旧字符，从右边滑进一个未扫描过的新字符。然后比较两个数组 sCntArr和 pCntArr是否相同，若相同则向结果集中追加当前滑动窗口的起始位置 i+1。

	for i := 0; i < sLen - pLen; i++ {// 左边滑出一个扫描过的旧字符sCntArr[s[i] - 'a'] -= 1 // 右边滑进一个未扫描过的新字符sCntArr[s[i+pLen] - 'a'] += 1if sCntArr == pCntArr {res = append(res, i+1)}}

• 最后返回结果集

十七、贪心（共1题）

55. 跳跃游戏

• 贪心法-1 【从左向右】，参考 LeetCode题解
  • 定义一个 maxJump = 0，表示从头开始能跳到的最大覆盖范围，每次都只向右跳一格
  • 更新 maxJump 范围 maxJump = max(maxJump, i + nums[i])，在 “上一次索引能覆盖的范围” 和 “当前索引能覆盖的范围” 中取一个较大值，作为当前能跳跃到的的最远距离
  • 每次循环都判断：当 目前能跳跃的最大范围 maxJump >= 数组最后一个索引 时，返回true，否则返回false。
• 贪心法 2：【从右向左】，参考 B站视频题解 最后面讲解的贪心法
  • 起初定义一个 maxJump = len(nums) - 1，表示最终要跳到数组最后一个下标位置
  • 从倒数第二个下标位置开始判断 能否到达最后一个下标位置：若满足【当前下标位置i + 当前可跳跃最大长度nums[i] >= 这一轮循环中要到达的目标位置 maxJump】，则表示从当前下标位置可以到达它右侧的目标位置 maxJump。
  • 其实就是判断 倒数第二个位置 是否能到达 倒数第一个位置 。若能到达，则继续判断 倒数第三个位置 是否能到达 倒数第二个位置，以此类推 … 最终到给定数组nums的首位置（下标为0）

十八、数学（共1题）

48. 旋转图像 ★\color{red}{★}★

此题比较有技巧性，分为以下两步：

• 主对角线（左上至右下）翻转翻转
• 水平翻转

func rotate(matrix [][]int)  {// 因为题目说是n*n的矩阵，所以这里实际上m=nm, n := len(matrix), len(matrix[0])// 对角线翻转（左上至右下）for i := 0; i < m; i++ {for j := 0; j < i; j++ { // 注意：这里j < imatrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]}}// 水平翻转for i := 0; i < m; i++ {for j := 0; j < n/2; j++ {matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]}}
}

补充一道类似技巧性的非 HOT100🔥 的高频题

189. 轮转数组
假设数组长度为：n = len(nums)
先整体翻转：0 ~ n-1
再翻转前 k 个：0 ~ k-1
最后翻转后 n - k 个： k ~ n

十九、其它（共2题，含1道 力扣VIP专属\color{red}{力扣VIP专属}力扣VIP专属 题）

253. 会议室 II（力扣VIP专属\color{red}{力扣VIP专属}力扣VIP专属 题，暂时跳过）

621. 任务调度器（middle\color{orange}{middle}middle 题，暂时跳过）

以下middle\color{orange}{middle}middle 题目我暂时跳过了，后面有精力再研究：

406. 根据身高重建队列
152. 乘积最大子数组
416. 分割等和子集
337. 打家劫舍 III
581. 最短无序连续子数组
253. 会议室 II
621. 任务调度器