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