LC 335. 路径交叉

题目描述

这是 LeetCode 上的 335. 路径交叉 ，难度为 困难。

给你一个整数数组 distance 。

从 X-Y 平面上的点 $(0,0)$ 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false。

示例 1：

输入：distance = [2,1,1,2]

输出：true

示例 2：

输入：distance = [1,2,3,4]

输出：false

示例 3：

输入：distance = [1,1,1,1]

输出：true

提示：

• $1 <= distance.length <= 10^5$
• $1 <= distance[i] <= 10^5$

---

找规律 + 分情况讨论

这是一道画图找规律的题目。

首先显然的是，至少需要 $4$ 条边才 可能 存在相交路径，如果 $distance$ 的长度小于 $4$，可直接返回 False，同时这引导我们如果某条边 $distance[i]$ 发生相交，不可能是与 $distance[i - 1]$ 或 $distance[i - 2]$ 之间发生的（基于条件 $1 <= distance[i] <= 10^5$）。

为了方便，我们分别使用 $a$、$b$、$c$ 和 $d$ 来分别代指「往上」、「往左」、「往下」和「往右」的四类方向边。

然后对可能相交情况进行分情况讨论，假设当前枚举到的边为 $distance[i]$（下面使用 $d[i]$ 代指 $distance[i]$）：

1. $d[i]$ 与 $d[i - 3]$ 发生相交：此时满足 $d[i] >= d[i - 2]$，同时 $d[i - 1] <= d[i - 3]$；

需要注意的时候 $d[i]$ 不一定是 $d$ 类边，而可以是 $abcd$ 任意类的边，此时只是矩形发生旋转，并不会影响路径相交的事实，其余分情况讨论也是同理。

1. $d[i]$ 与 $d[i - 4]$ 发生相交：此时满足 $d[i - 1] = d[i - 3]$，同时 $d[i] + d[i - 4] >= d[i - 2]$；

1. $d[i]$ 与 $d[i - 5]$ 发生相交：此时满足$d[i - 1] <= d[i - 3]$，同时 $d[i - 2] > d[i - 4]$，同时 $d[i] + d[i - 4] >= d[i - 2]$，同时 $d[i - 1] + d[i - 5] >= d[i - 3]$。

综上，$d[i]$ 不会与 $d[i - 1]$ 和 $d[i - 2]$ 发生相交，而 $d[i]$ 与 $d[i - 3]$、$d[i - 4]$ 和 $d[i - 5]$ 的相交条件如上述讨论。并且 $d[i]$ 不会与 $d[i - x]$ $(x > 5)$ 发生相交的同时，不与 $d[i - y]$ $(3 <= y <= 5)$ 发生相交。即 $d[i]$ 与 $d[i - x]$ $(x > 5)$ 发生相交前，必然与 $d[i - y]$ $(3 <= y <= 5)$ 发生相交。

代码：

class Solution {
    public boolean isSelfCrossing(int[] d) {
        int n = d.length;
        if (n < 4) return false;
        for (int i = 3; i < n; i++) {
            if (d[i] >= d[i - 2] && d[i - 1] <= d[i - 3]) return true;
            if (i >= 4 && d[i - 1] == d[i - 3] && d[i] + d[i - 4] >= d[i - 2]) return true;
            if (i >= 5 && d[i - 1] <= d[i - 3] && d[i - 2] > d[i - 4] && d[i] + d[i - 4] >= d[i - 2] && d[i - 1] + d[i - 5] >= d[i - 3]) return true;
        }
        return false;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.335 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。