LeetCode 335. 路径交叉
题目描述
题意分析
从原点出发，按北、西、南、东循环行走，每步长度都是正数，判断新走出的线段是否碰到此前的路径。与非相邻历史线段的端点接触、共线重叠都算相交；连续两步正常共用的连接端点不算。
解法：三种几何相交判定
核心思路
[!blue]
每走一步都固定左转 $90$ 度，所以不必把当前线段与所有旧线段逐一比较。相邻边只共用连接点，隔一条的边与当前边平行且被正长度的边隔开；最早从第四条边开始才可能自交。
只考虑第一次相交之前的路径：固定左转会形成向外扩张的螺旋，或在某次转向后进入内缩。持续内缩时，最近一圈的边挡在更早路径前面，向外伸得过长会先撞到
i - 3；从外扩转入内缩的入口处，还可能接触i - 4，或越过入口碰到i - 5。若要先到达更早的边，就必须先穿过这些近处边界。因此每轮只需检查当前边与i - 3、i - 4、i - 5的三种局部关系，一旦发现便立即返回。为推导条件，把当前边及向前五条边的长度依次记作
a、b、c、d、e、f，分别对应distance[i]到distance[i - 5]。平移、旋转不改变相交关系，可以把当前边的起点放在(0, 0)，并令它向北走到(0, a)。与
i - 3垂直相交：这条旧边位于高度c，横向范围为[-b, d - b]。当前边要到达高度c，需要a >= c；旧边要覆盖横坐标 $0$，需要d - b >= 0，即b <= d。这正是代码的第一组条件。与
i - 4共线相接或重叠：这条旧边的横坐标是d - b，纵向范围是[c - e, c]。它与当前边共线要求b == d；两个纵向区间有重叠还需要a >= c - e，即a + e >= c。两者缺一不可。与
i - 5垂直相交：这条旧边位于高度c - e，横向范围为[d - b - f, d - b]。它的高度要落在当前边的[0, a]内，需要c >= e且a + e >= c；它的横向范围要包含 $0$，需要b <= d且b + f >= d。合起来就是第三组的四个条件。每组条件都在检查交点是否同时落在两条有限线段上，不能只判断它们所在的直线相交。所有比较保留等号，以覆盖端点恰好接触；第二、三组分别需要至少五条、六条边，必须先判断
i >= 4、i >= 5。
解题步骤
- 从第四条边开始扫描。
- 检查当前边与三条之前的边是否穿越。
- 边数足够时检查四条之前的共线情况。
- 边数足够时检查五条之前的内缩相交，全部未命中则继续。
代码实现
class Solution {
public boolean isSelfCrossing(int[] distance) {
for (int i = 3; i < distance.length; i++) {
// 第一类：当前边与三条之前的边垂直相交。
if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) {
return true;
}
// 第二类：当前边与四条之前的边共线接触或重叠。
if (i >= 4
&& distance[i - 1] == distance[i - 3]
&& distance[i] + distance[i - 4] >= distance[i - 2]) {
return true;
}
// 第三类：由外扩转为内缩时，检查与五条之前的边相交。
if (i >= 5
&& distance[i - 2] >= distance[i - 4]
&& distance[i] + distance[i - 4] >= distance[i - 2]
&& distance[i - 1] <= distance[i - 3]
&& distance[i - 1] + distance[i - 5] >= distance[i - 3]) {
return true;
}
}
return false;
}
}
func isSelfCrossing(distance []int) bool {
for i := 3; i < len(distance); i++ {
// 第一类：当前边与三条之前的边垂直相交。
if distance[i] >= distance[i-2] &&
distance[i-1] <= distance[i-3] {
return true
}
// 第二类：当前边与四条之前的边共线接触或重叠。
if i >= 4 &&
distance[i-1] == distance[i-3] &&
distance[i]+distance[i-4] >= distance[i-2] {
return true
}
// 第三类：由外扩转为内缩时，检查与五条之前的边相交。
if i >= 5 &&
distance[i-2] >= distance[i-4] &&
distance[i]+distance[i-4] >= distance[i-2] &&
distance[i-1] <= distance[i-3] &&
distance[i-1]+distance[i-5] >= distance[i-3] {
return true
}
}
return false
}
复杂度分析
- 时间复杂度：$O(n)$，每条边做固定次数比较。
- 空间复杂度：$O(1)$，无需记录全部坐标。
关键点总结
[!green]
- 检查的是第一次相交，此前路径尚未自交。
- 三种形态对应不同历史边，不能只保留普通穿越。
- 下标保护与各形态所需边数对应。
易错点总结
[!yellow]
- 只检查与 i-3 的关系：会漏掉共线和内缩情况。
- 共线条件放宽为不等号：两条平行边未必处在同一条直线上。
- 改为严格不等号：漏掉恰好接触。
- 未检查 i≥4、i≥5：短路径会访问不存在的历史项。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 16.03. 交点 | 困难 | 线段相交判定提供几何基础，本题还利用固定转向限制，只需关注少数相邻历史线段。 |