Algorithm Learning

动态规划经典问题学习记录 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 （深度优先遍历）。...