0335. Self Crossing

题目信息

题号:

0335

难度:

Hard

主题:

平面路径、固定转向、线段相交、边界接触

原题:

LeetCode 0335

重点:

方向按北西南东循环、每段长度为正、相交包含端点接触和线段重合

题目重述

从平面原点开始,根据数组 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)。