CodingLearning

• 链表
• 数组
• DFS
• 余数
• 滑动窗口
• 动态规划
• 回溯
• BFS
• 贪心
• 分治
• 单调栈
• 二维差分数组？
  • 二维差分公式
  • 练习题目
• 计算几何
• 数值迭代
• 拓扑序
• 面试遇到过的题
  • 酷
  • 地
  • 小马
  • 文远
  • 新石器
  • 轻舟

链表

• [x] 141. 环形链表 (比较简单)
• [x] 142. 环形链表 II （需要注意Floyd判圈）
  
  fast 指针已经走完了环的 n 圈，因此它走过的总距离为

而 slow 指针只走了 a+b 的距离，因此它们在环上相遇时，fast 指针比 slow 指针多走了 $nb+nc$ 的距离。

• [x] 160. 相交链表
  方案1：直接hash，复杂度比较差
  方案2：双指针
  在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a 次之后一定会是重复节点。如果无相交就是空节点 妙啊

• [x] 19. 删除链表的倒数第 N 个结点
  方案1：两次遍历

方案2：栈

• [x] 21. 合并两个有序链表
  很简单

• [x] 23. 合并 K 个升序链表
  直接递归，但是复杂度较高
  待优化为分治或优先队列

• [x] 86. 分隔链表
  直接模拟

• [x] 876. 链表的中间结点
  很简单

数组

• [x] 167. 两数之和 II - 输入有序数组
  双指针
• [ ] 5. 最长回文子串
  这个做的不好，再看看

DFS

• [x] 797. 所有可能的路径
  直接回溯即可
• [ ]

余数

• [x] 1015. 可被 K 整除的最小整数
  本题需注意的是模运算的分配律，避免数值溢出。
  对于任意整数 a, b, c和模数 p，以下性质成立：
  分配律：(a * b + c) % p = [(a % p) * (b % p) + (c % p)] % p
  这意味着，乘法和加法的中间结果可以随时取模，而不影响最终余数。
  题目中的目标整数迭代格式为R(k) = R(k-1) * 10 + 1
  取模后等价为
  R(k) % mod = [(R(k-1) % mod) * 10 + 1] % mod
  数学归纳法可知只需要维护(mod(k-1)) * 10 + 1，这一个变量即可，避免数值溢出。
• [x] 3381. 长度可被 K 整除的子数组的最大元素和
• [x] 2435. 矩阵中和能被 K 整除的路径
  困难题之耻
• [x] 2872. 可以被 K 整除连通块的最大数目

滑动窗口

• [x] 438. 找到字符串中所有字母异位词
• [x] 567. 字符串的排列
• [x] 76. 最小覆盖子串
  做的不好
• [ ]

动态规划

• [x] 322. 零钱兑换
• [x] 509. 斐波那契数

回溯

• [x] 46. Permutations
  一点也不会
• [x] 216. 组合总和 III
  比较简单，可以记一下visited
• [x] 39. 组合总和
  也很简单，允许重复，不需要记录visited
• [x] 40. 组合总和 II
  需要去重，额外考虑一下排序然后如何去重
• [x] 47. 全排列 II
  需要考虑去重，前一个visited
• [ ] 473. 火柴拼正方形

BFS

• [x] 752. 打开转盘锁
  简易BFS
• [x] 773. 滑动谜题
  需要将二维数组字符串化

贪心

• [x] 55. 跳跃游戏
  要贪心，不要动态规划
• [x] 45. 跳跃游戏 II
  kargo面试coding原题
  记住当前跳的最远距离，每跳更新最远能跳到哪里。如果index更新到当前最远距离了，步数就必须加一

贪心还需要学习

• [x] 2654. 使数组所有元素变成 1 的最少操作次数
  不好想，核心思路是我们可以找到一个最小的区间，这个区间内所有数字的 gcd 是 1。假设这个区间长度是 minLen，那么由这些数字得到一个 1 所需的次数是 minLen−1；然后再由这个 1 使得其他数字都变为 1 所需的次数是 n−1。因此总共需要 minLen+n−2 次操作。

• [x] 455. 分发饼干
  需要注意到每个孩子只能吃一个饼干，不能多吃，多吃干死

• [x] 860. 柠檬水找零（Lemonade Change）
  不用想太多，枚举三种钱的情况即可

分治

• [x] 23. 合并K个升序链表
  直接递归也能跑。效率地点

单调栈

- [ ] 3542. 将所有元素变为 0 的最少操作次数
不会做，多看看

二维差分数组？

• [x] 2536. 子矩阵元素加 1
  不好做。暴力模拟虽然容易，但是会超时
  需要想到利用二维前缀和
  可以先用1109熟悉一下一维的前缀和
• [x] 1109. 航班预订统计
  知道差分的话比较好想。

二维差分公式

在二维中，还原（计算前缀和）的公式是： mat[x][y] = diff[x][y] + mat[x-1][y] + mat[x][y-1] - mat[x-1][y-1]

这个公式反过来告诉我们一个至关重要的信息：

二维的关键：在差分数组 diff 的 (r, c) 位置放一个 +1，在计算前缀和时，它会影响它右下方的所有元素！

也就是说，所有 (x, y) 满足 x >= r 且 y >= c 的 mat[x][y] 都会被这个 +1 影响。

res[i][j] = 差分值 + 上方和 + 左方和 - 左上方和

练习题目

• [x] LCR 013. 二维区域和检索 - 矩阵不可变
  二维前缀和即可
• [x] LeetCode 1314. 矩阵区域和
  比较套路，直接二维前缀和
• [x] LeetCode 2132. 用邮票贴满网格图
  困难题，一眼丁真，没有思路
  和AI讨论一下思路以后勉强能做，不看参考代码可以做出来

计算几何

• [x] 1232. 缀点成线
  easy

• [x] LeetCode 587. 安装栅栏 (Erect the Fence)
  如何构建最小凸包

• [x] 149. 直线上最多的点数
  需要注意除以最大公约数，便于hash

• [x] 939. 最小面积矩形

• [x] 2013. 检测正方形
  倒是不难哈

• [x] 973. 最接近原点的 K 个点
  直接按distance排序即可，不过可以熟悉一下优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//   - 第一个模板参数: 存储的类型 (pair<int, int>)
        //   - 第二个模板参数: 内部使用的容器 (vector<...>)
        //   - 第三个模板参数: 比较器 (greater<...>)，表示 "小的" 在前面
priority_queue<pair<int, int>,
            vector<pair<int, int>>,         
            greater<pair<int, int>>> min_heap; // value, index

//   - 类型: HeapEntry
        //   - 容器: vector<HeapEntry>
        //   - 比较器: less<HeapEntry> (这会创建一个大根堆)
        priority_queue<
            HeapEntry,
            vector<HeapEntry>,
            less<HeapEntry>
        > max_heap;

• [x] 812. 最大三角形面积
  crossProd即可
  可以学习一下鞋带公式
• [ ] 836. 矩形重叠
  可以练习一下分离轴定理

数值迭代

• [x] 69. x 的平方根
  练习牛顿迭代法
• [x] 367. 有效的完全平方数
  牛顿法即可
• [x] 153. 寻找旋转排序数组中的最小值
  二分法即可

拓扑序

• [x] 207. 课程表
• [x] 841. 钥匙和房间

面试遇到过的题

酷

问题： 4x4 网格从左上角到右下角的最长路径问题（每步只能向右或向下）。

地

leetcode 水果成篮
leetcode 封闭岛屿数目

小马

题目： N 天暑假，每天有 A_i, B_i, C_i 三种活动，给定每天活动的幸福度。要求最大化总幸福度，但不能连续两天做同一种活动。

题目： 一本书有N个章节，每个章节有若干个前置章节，必须读懂前置章节才能读懂该章节，每次阅读必须按顺序读，求读懂本书的最小阅读次数。

文远

• 题目：2D平面内射线与圆的交点求解
• 题目：求解无权重图中节点间最短路径
• 题目：给定一个数组，需要将其分成N段，使得所有段的和的最大值最小。

新石器

二叉树遍历

计算几何，判断一个点是否在多边形内

实现了一个模板类队列

轻舟

判断多边形是否为凸多边形

对已排序链表，删除有重复数字的节点，只留不同数字。