Algorithm Learning

70.爬楼梯 1 2 3 4 5 6 7 8 9 10 func climbStairs(n int) int { cache := make([]int, n+1) cache[0], cache[1] = 1, 1 for i := 2; i <= n; i++ { cache[i] = cache[i-1] + cache[i-2] } return cache[n] } 最简单的一维 DP 题，遇见属于白给，最标准的没有套路的 DP，完全不需要解释。 198.打家劫舍 1 2 3 4 5 6 7 8 9 10 func rob(nums []int) int { cache := make([]int, len(nums)+1) cache[0], cache[1] = 0, nums[0] for i := 2; i <= len(nums); i++ { cache[i] = max(nums[i-1]+cache[i-2], cache[i-1]) } return cache[len(nums)] } 经典打家劫舍，难度同样属于白给。...

回溯算法本质上是一种深度优先搜索（DFS），通过递归来模拟“探索所有可能性”的过程。它的核心思想可以总结为三个步骤： 选择 (Choose): 在当前状态下，从所有可能的选择中，选择一个。 探索 (Explore): 基于这个选择，进入下一层决策，即调用递归函数。 撤销选择 (Unchoose): 当下一层的探索全部结束后（无论是找到了解还是走到了死路），退回到当前状态，撤销刚才的选择，然后尝试下一个可用的选择。 几乎所有的回溯问题，都可以用下面这个伪代码模板来解决： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 result = [] // 存放最终结果 path = [] // 存放当前路径 func backtrack(参数列表) { // 1. 终止条件：判断是否找到了一个可行的解 if (满足结束条件) { // 将当前路径的一个副本加入结果集 result.add(path.clone()) return } // 2. 遍历所有可能的选择 for choice in (当前状态下的所有选择) { // 剪枝：如果这个选择不合法，则跳过 if (isPruned(choice)) { continue } // 3....

200. 岛屿数量 - 力扣（LeetCode） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 func numIslands(grid [][]byte) int { m, n := len(grid), len(grid[0]) var dfs func(x, y int) ans := 0 dfs = func(x, y int) { if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] !...

236. 二叉树的最近公共祖先 - 力扣（LeetCode） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { // 跳出递归 if root == nil { return nil } // 祖先可能是 p,q if root == p || root == q { return root } // 祖先不是 p,q ，在左右子树上再次寻找 left := lowestCommonAncestor(root....

LRU 缓存到底要做什么？ 在动手写代码之前，最重要的一步是明确我们的目标。LRU 缓存机制的核心是：当缓存满了以后，优先淘汰最久没有被使用过的数据。 我们来分解一下 LRUCache 需要实现的功能： Constructor(capacity int): 初始化一个固定容量的缓存。 Get(key int): 如果 key 存在，返回对应的 value。 关键点：这次访问使得该 key 成为了“最近使用的”，所以需要更新它的位置。 如果 key 不存在，返回 -1。 Put(key int, value int): 如果 key 存在，更新 value。 关键点：这次更新也使得该 key 成为了“最近使用的”，需要更新它的位置。 如果 key 不存在，插入这个新的键值对。 关键点：插入后，如果缓存的尺寸超过了 capacity，则必须淘汰“最久未使用的”那个元素。 总结一下，我们需要一个数据结构，它必须同时满足以下几个要求： 快速查找：Get 和 Put 都需要快速地判断一个 key 是否存在。 有序存储：需要一种机制来记录所有 key 的“新旧”顺序，方便我们找到“最久未使用的”那个。 快速增删：当一个 key 被访问（Get 或 Put）时，我们要能快速地将它移动到“最新”的位置。当缓存满了，也要能快速地删除“最旧”的那个。 哈希表 + 双向链表 这是本题的核心套路。没有任何单一的基础数据结构能同时满足上述所有要求，所以需要组合。 为什么需要哈希表 (map)？ 为了实现 O(1) 复杂度的快速查找。我们可以用 map[int]*Node 来存储 key 到链表节点的映射。 为什么需要链表？ 为了维护元素的“新旧”顺序。链表天然有序。我们可以规定，越靠近链表头部的元素，就是“最近使用”的；越靠近链表尾部的，就是“最久未使用”的。 为什么必须是双向链表，而不是单向？ 因为我们需要 O(1) 复杂度的删除操作。想象一下，当我们要删除一个节点（比如缓存满了要淘汰尾部节点，或者 Get 了一个中间节点要把它移动到头部），我们需要修改这个节点前面那个节点的 Next 指针。在单向链表中，找到前驱节点需要从头遍历，时间复杂度是 O(n)。而双向链表每个节点都存了 Pre 和 Next 指针，使得我们可以在 O(1) 的时间内完成任意节点的删除。 结论：哈希表 (map) + 双向链表 (Doubly Linked List) 是解决此问题的完美组合。...

变量名称定义 在开始反转链表套路学习前，先定义一组变量，这组变量会贯穿全部的题型： cur：指向当前正在进行反转的节点和反转完成后的下一个待反转链表的头部； pre：指向已完成反转链表的头部（头插法的缘故），初始值为nil（仅在 206 中是这样，其他情况下都是pre := &ListNode{}进行定义）。； next：指向cur的下一个节点。 后面还会根据不同的题型有不同的变量引入。 206. 反转链表 - 力扣（LeetCode） 1 2 3 4 5 6 7 8 9 10 11 12 13 func reverseList(head *ListNode) *ListNode { var pre *ListNode // 需要注意，不要写成 pre := *ListNode{}，这样就完成了初始化、值不是 nil 了 cur := head for cur != nil { next := cur.Next // 保存 next，防止丢失 cur.Next = pre // 断 cur 尾，使其指向反转链表头部 pre = cur // 更新 pre，让其移动到 cur 的位置，此时 cur 成为新头部，pre 符合其定义仍然指向反转链表的头部 cur = next // cur 移动，指向下一个待反转节点 } return pre } 循环中的这 4 步：...

动态规划经典问题学习记录 0-1 背包 问题描述 有 $n$ 个物品，第 $i$ 个物品的体积为 $w[i]$ ，价值为 $v[i]$ ，每个物品最多选一次，求体积和不超过 $capacity$ 时的最大价值和。 通过回溯去思考解题思路 先去思考当前的操作，即枚举第 $i$ 个物品选与不选： 不选，剩余容量不变。 选，剩余容量减少 $w[i]$ 。 递归到子问题，在剩余容量为 $c$ 时，从前 $i$ 个物品中得到的最大价值和。 下一个递归子问题： 不选，在剩余容量为 $c$ 时，从前 $i-1$ 个物品中得到的最大价值和。 选，在剩余容量为 $c-w[i]$ 时，从前 $i-1$ 个物品中得到的最大价值和。 最终得到的递归公式：$dfs(i,c) = max(dfs(i-1, c),dfs(i-1, c-w[i])+v[i])$ 对应的代码就是： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def zero_one_backpack(capacity: int, w: List[int], v: List[int]) -> int: n = len(w) @cache # 记忆化搜索数组 def dfs(i: int, c: int) -> int: # 跳出递归条件 if i < 0: return 0 # 容量不足时 if c < w[i]: return dfs(i-1, c) # 将问题进一步分解 return max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i]) return dfs(n-1, capacity) 以上就是 0-1 背包的“至多装 capacity”的递归+记忆化搜索形式，其实也可以写成递推式：$dp[i][c] = max(dp[i-1][c],dp[i-1] [c-w[i]]+v[i])$...

Leetcode-75 总结 代码链接：KurongTohsaka/my-lc75-go Array&String 151 反转字符串中的单词：双指针。 238 除自身以外数组的乘积：线性 DP 。 334 递增的三元子序列：双指针。 345 反转字符串中的元音字母：双指针。 443 压缩字符串：双指针。 605 种花问题：列出三种种花情况，依次进行处理即可。 1071 字符串的最大公因式：根据特殊的 str1 + str2 == str2 + str1 公式和辗转相除法解题。 1431 拥有最多糖果的孩子：先找最大值，然后进行比较。 1768 交替合并字符串：取较小长度最为切割位置，然后交替合并，最后处理剩余部分。 DoublePointers 11 接水问题：双指针的首尾指针。 283 移动零：双指针的快慢指针。 392 判断子序列：双指针的快慢指针。 1679 K 和数对的最大数目：解法与两数之和相似，使用哈希表记录为匹配数组次数，然后更新 hashMap[k-v] 的数值。 SlidingWindow 643 子数组最大平均数-1 ：定长滑动窗口，应用通用解法，即新元素进入、更新统计量、right-left+1 元素离开三步。 1004 最大连续1的个数-2 ：变长滑动窗口，通过快慢指针实现。 1456 定长子串中元音的最大数目：定长滑动窗口，通用解法。 1493 删掉一个元素后全为1的最长子数组：变长滑动窗口，解法与 1004 高度相似。 PrefixSum 724 寻找数组的中心下标：双指针可解，不过还是推导出的公式更快。 1732 找到最高海拔：很简单，直接秒。 HashMap 1207 独一无二的出现次数：用了两个哈希，第一个是对数组中所有元素进行计数，第二个是对第一个哈希元素的出现次数进行计数，目的是得到独一无二的出现次数。 1657 确定两个字符串是否接近：操作 1 和 2 能实现的大前提是两个字符串的长度一致，操作 1 只要两个字符串对应的字母的计数一致就成立，操作 2 则进一步要求每个“次数”一致。 2215 找出两数组的不同：双哈希表记录每个元素出现次数，然后分别进行比较。 2352 相等行列对：一个哈希表解决。先行遍历，把每一行作为键存储，然后记录相同的行出现的次数。再列遍历，把每列作为键去查询，然后把次数加上相同的行的个数。 Stack 394 字符串解码： 本题要点在于只要遇到右括号就开始处理栈内元素： 先处理直到左括号内的所有元素，拼接后再反转（顺序是反的🐎），然后别忘记让左括号出栈。 之后统计出现次数，此时注意数字可能为两位数。在处理完成后，就开始按照次数重复拼接子串，然后再把该子串入栈（处理嵌套字符串的方式）。 735 小行星碰撞：只有当栈顶向右（正）且当前行星向左（负）时才处理碰撞，使用循环处理可能的多次碰撞，直到当前行星被摧毁或无法继续碰撞。 2390 从字符串中移除星号：常规栈解法，很简单。 Queue 649 Dota2 参议院：使用两个队列存储每位参议院出现的位置，通过比较位序来选择被淘汰的议员，同时保证每轮必有两名议员被踢出队列。 933 最近的请求次数：维护一个队列，本题想要的结果就是最终的队列长度。超出时间范围的请求出队、新请求进队。 LinkedList 206 反转链表：经典操作，三指针反转链表，属于基本功了。 328 奇偶链表：用两个变量记录奇偶两个链表的头节点，再用两个变量作为构建奇偶链表的指针。然后遍历整个链表去构建奇偶链表，最后把奇链表的指针指向偶链表的头部。 2095 删除链表中的中间节点：通过快慢指针找到中间节点，同时记录慢指针的前一个节点方便后续删除操作。 2130 链表最大孪生和：本题属于缝合题，先是快慢指针找中间节点，再是反转后半部分链表，最后又是一个双指针遍历。 Tree - DFS 所有题都是。DFS （深度优先遍历）。...