路径交叉Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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⁵
1 <= distance[i] <= 10⁵

# 思路

/**
参考的这篇https://leetcode-cn.com/problems/self-crossing/solution/c3ge-bu-zou-miao-jie-ci-ti-by-xiaohu9527-96n6/
考虑绕圈情况，绕圈有两种：从内向外和从外向内。通过分析可以确定，不相交的只有3种情况：
1. 从distance[0]开始从外向内绕圈，直到结束。
2. 从distance[0]开始从内向外绕圈，直到结束。
3. 从distance[0]开始从内向外绕圈，直到某个时刻开始从外向内绕圈，直到结束。这种情况两次绕圈的最外层不能相交。
从内向外绕圈是distance[i]>distance[i-2]，从外向内绕圈则是distance[i]<distance[i-2]。
*/

# 解法


class Solution {
    /**
参考的这篇https://leetcode-cn.com/problems/self-crossing/solution/c3ge-bu-zou-miao-jie-ci-ti-by-xiaohu9527-96n6/
考虑绕圈情况，绕圈有两种：从内向外和从外向内。通过分析可以确定，不相交的只有3种情况：
1. 从distance[0]开始从外向内绕圈，直到结束。
2. 从distance[0]开始从内向外绕圈，直到结束。
3. 从distance[0]开始从内向外绕圈，直到某个时刻开始从外向内绕圈，直到结束。这种情况两次绕圈的最外层不能相交。
从内向外绕圈是distance[i]>distance[i-2]，从外向内绕圈则是distance[i]<distance[i-2]。
 */
    public boolean isSelfCrossing(int[] distance) {

        int n = distance.length;
        if (n < 4) return false;
        int step = 2;
        // 第一种情况
        if (distance[step] < distance[step-2]){
            while (step < n){
                if (distance[step] >= distance[step-2]) return true;
                ++step;
            }
            return false;
        }

        // 从distance[0]开始从内向外绕圈
        while (step < n){
            if (distance[step] <= distance[step-2]) break;
            ++step;
        }
        // 第二种情况
        if (step >= n) return false;
        // 第三种情况
        boolean flag1 = distance[step]+(step >= 4 ? distance[step-4] : 0) >= distance[step-2];
        boolean flag2 = (step <=n-2 ? distance[step+1] : 0)+(step >= 3 ? distance[step-3] : 0) >= distance[step-1];
        if (flag1 && flag2) return true; // 两次绕圈的最外层相交
        ++step;
        while (step < n){
            if (distance[step] >= distance[step-2]) return true;
            ++step;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# 总结

分析出几种情况，然后分别对各个情况实现