0335. Self Crossing¶
题目信息¶
- 题号:
0335
- 难度:
Hard
- 主题:
平面路径、固定转向、线段相交、边界接触
- 原题:
- 重点:
方向按北西南东循环、每段长度为正、相交包含端点接触和线段重合
题目重述¶
从平面原点开始,根据数组 distance 依次移动。第 0 段向北,第 1 段向西,第 2 段向南,第 3 段向东,之后继续按北、西、南、东的顺序循环;distance[i] 是第 i 段移动的正整数距离。
判断新绘制的路径是否在任意位置与此前已经走过的轨迹相交。相交不仅包括两条线段从内部穿过,也包括端点碰到旧线段以及两段路径发生重合。distance 的长度位于 [1, 10^5],每个距离位于 [1, 10^5]。
自建示例¶
回到起点也算自交:
输入:distance = [1, 1, 1, 1]
输出:true
解释:四段路径形成一个正方形,最后一段的终点回到原点,与第一段的起点接触,因此轨迹自交。
持续向外扩张:
输入:distance = [1, 2, 3, 4]
输出:false
解释:四条线段依次向北、西、南、东延伸,最后一段位于先前轨迹下方,没有接触或穿过旧线段。
按转向顺序只需检查三种首次相交形态¶
路径的方向固定为北、西、南、东。若一直没有相交,轨迹会围绕原点向外扩张;一旦第一次相交,新线段只可能碰到它前面有限的几条线段,几何关系按距离大小归纳为三类:当前段直接越过两段之前的平行段;当前段与四段之前的边接触或越过;外扩路径先收缩后回到更早的边界,当前段与五段之前的边相交。对每个新段按这三类检查,就覆盖了端点接触和重合边界。
不等式使用 >=、<= 而不是严格比较,是因为题目把恰好碰到端点也视为相交。第三种形态同时比较内侧两条边是否已经收缩到会互相穿过的范围;只要其中一个方向仍留有间隔,就不会产生交点。
C++ 实现¶
class Solution {
public:
bool isSelfCrossing(std::vector<int>& distance) {
for (int i = 3;
i < static_cast<int>(distance.size()); ++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)。