算法补充题

核心思路是使用向量和直角关系判断。

常见做法：

1. 任选一个点作为顶点。
2. 计算相邻边向量。
3. 判断相邻边点积是否为 0。
4. 再结合边长关系和点是否重合做校验。

如果三组相邻边都能满足直角关系，并且四点不重合，通常就能判定为矩形。

经典做法是快慢指针（Floyd 判圈算法）：

1. 快指针每次走两步，慢指针每次走一步。
2. 如果两者相遇，说明有环。
3. 一个指针回到头结点，另一个留在相遇点。
4. 两者都每次走一步，再次相遇的位置就是环入口。

这个算法时间复杂度 O(n)，空间复杂度 O(1)。

可以用这两个条件快速判断：

1. 5 张牌不能有重复。
2. max - min == 4。

如果两者都满足，这 5 张牌就是连续的顺子。

这种方法比排序后逐项比较更简洁。

经典方法有两种：

1. 先分别求长度，长链表先走差值步数，再一起走。
2. 双指针法：A 走完走 B，B 走完走 A，最终会在公共节点相遇。

双指针法更常见，也更优雅，时间复杂度 O(m+n)，空间复杂度 O(1)。

这是典型动态规划问题。

定义状态：

• dp[i][j] 表示前 i 个元素和前 j 个元素的最长公共子序列长度。

转移规则：

• 如果当前元素相等：dp[i][j] = dp[i-1][j-1] + 1
• 如果不相等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

标准做法时间复杂度一般是 O(m*n)。

标准做法是栈。

处理过程：

1. 遇到左括号就入栈。
2. 遇到右括号就检查栈顶是否匹配。
3. 不匹配直接返回 false。
4. 遍历结束后栈为空，说明完全闭合。

这类题考的是：

• 栈结构
• 括号匹配
• 边界条件处理

如果题目是“只出现一次的元素”，最常见方法有两类：

1. 哈希表计数。
2. 如果题目条件允许“其他元素都出现两次”，可以用异或。

哈希表法更通用：

• 先统计频次。
• 再筛出频次为 1 的元素。

这是典型海量数据题，关键不在一次性读完。

常见思路：

1. 先分桶，把词按哈希拆到多个小文件。
2. 对每个小文件统计词频。
3. 用最小堆维护 Top 100。
4. 最后合并各桶结果得到全局 Top 100。

这道题主要考察：

• 外部排序/分治
• 哈希分桶
• TopK
• 内存受限处理

经典做法是射线法。

基本思路：

1. 从目标点向某一方向发出一条射线。
2. 统计它与多边形边的交点数量。
3. 交点数为奇数，通常说明点在内部。
4. 交点数为偶数，通常说明点在外部。

需要特别注意：

• 点落在边上
• 点落在顶点
• 射线恰好穿过顶点

这些边界情况要单独处理。

这三类题不要混在一起：

• 最长子串：常见用滑动窗口。
• 最长公共连续子串：常见用动态规划。
• 最长重复子串：可用后缀数组、后缀自动机或二分加哈希等方法。

面试里最重要的是先澄清：

• 是“连续”还是“不连续”
• 是“一个串内部重复”还是“两个串之间比较”

经典做法是变体二分查找。

每次取中点后，判断哪一半仍然有序：

• 如果左半有序，判断目标值是否落在左半范围内。
• 否则右半有序，再判断是否落在右半范围内。

不断缩小区间即可，平均时间复杂度通常为 O(log n)。

标准做法是队列。

过程如下：

1. 根节点入队。
2. 队列不为空时，取出队头节点。
3. 访问当前节点。
4. 把它的左右子节点依次入队。

这就是 BFS 在树结构上的典型应用。