🌕🌕 335. 路径交叉

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public boolean isSelfCrossing(int[] distance) {
        // 思路：
        // 数学归纳法 - 找规律
        // 发现只有 3 种情况会出现相交的情况
        // 1) 如 例1 所示 
        // == > [i - 1] <= [i - 3] && [i] >= [i - 2]
        // 2) 如 例2 中，将第四条线截止 纵坐标 0，第五步继续往上与 (0, 0) 重合
        // ==> [i - 1] == [i - 3] && [i] + [i - 4] >= [i - 2]
        // 3) 如 例3 中，继续往上走，走不到 1 然后 左转
        // ==> [i - 1] + [i - 5] >= [i - 3] && [i - 4] + [i] >= [i - 2]
        // 向右 & 向上 方向为正，前面符合为 +；向下 & 向左方向为负，符合 -
        int len = distance.length;
        if(len < 4) {
            return false;
        }
        // len >= 4
        for(int i = 3; i < len; i ++) {
            if(distance[i - 1] <= distance[i - 3] 
                && distance[i] >= distance[i - 2]) {
                    // System.out.println("aa  " + i);
                return true;
            }
            if(i >= 4 
                && distance[i - 1] == distance[i - 3] 
                && distance[i] + distance[i - 4] >= distance[i - 2]) {
                    // System.out.println("bb  " + i);
                return true;
            }
            if(i >= 5 
                && distance[i - 1] + distance[i - 5] >= distance[i - 3] 
                && distance[i - 5] <= distance[i - 3] 
                && distance[i - 1] <= distance[i - 3]) {
                if(distance[i] + distance[i - 4] >= distance[i - 2] && distance[i - 2] >= distance[i - 4]) {
                    // System.out.println("cc  " + i);
                    return true;
                }
                if(distance[i] >= distance[i - 2] && distance[i - 2] <= distance[i - 4]) {
                    // System.out.println("dd  " + i);
                    return true;
                }
            }
        }
        return false;
    }
}

---

输出