力扣每日一题2021-10-29路径交叉

• 335.路径交叉
• • 题目描述
  • 思路：分类讨论
  • • Java实现
    • Python实现

路径交叉

首先计算distance长度，如果distance小于4，则必然不会相交，返回false；如果distance长度大于等于4，才开始分类讨论。

1. distance[i]与distance[i-3]相交：此时必定满足 d i s t a n c e [ i ] > = d i s t a n c e [ i − 2 ] distance[i]>=distance[i-2] distance[i]>=distance[i−2]，同时满足 d i s t a n c e [ i − 1 ] < = d i s t a n c e [ i − 3 ] distance[i-1]<=distance[i-3] distance[i−1]<=distance[i−3]。distance[i]不一定是向东移动的边，可以是任意方向的边，此时矩形发生旋转，但不影响相交，其他情况也同理。
2. distance[i]与distance[i-4]相交：此时必定满足 d i s t a n c e [ i − 1 ] = d i s t a n c e [ i − 3 ] distance[i-1]=distance[i-3] distance[i−1]=distance[i−3]，同时满足 d i s t a n c e [ i ] + d i s t a n c e [ i − 4 ] > = d i s t a n c e [ i − 2 ] distance[i]+distance[i-4]>=distance[i-2] distance[i]+distance[i−4]>=distance[i−2]。
3. distance[i]与distance[i-5]相交：此时必定满足 d i s t a n c e [ i ] + d i s t a n c e [ i − 4 ] > = d i s t a n c e [ i − 2 ] distance[i]+distance[i-4]>=distance[i-2] distance[i]+distance[i−4]>=distance[i−2]，同时满足 d i s t a n c e [ i − 1 ] < = d i s t a n c e [ i − 3 ] distance[i-1]<=distance[i-3] distance[i−1]<=distance[i−3]和 d i s t a n c e [ i − 2 ] > d i s t a n c e [ i − 4 ] distance[i-2]>distance[i-4] distance[i−2]>distance[i−4]以及 d i s t a n c e [ i − 1 ] + d i s t a n c e [ i − 5 ] > = d i s t a n c e [ i − 3 ] distance[i-1]+distance[i-5]>=distance[i-3] distance[i−1]+distance[i−5]>=distance[i−3]。

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

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        l = len(distance)
        if l <= 3:
            return False
        for i in range(3, l):
            if distance[i] >= distance[i-2] and distance[i-1] <= distance[i-3]:
                return True
            if i >= 4 and distance[i-1] == distance[i-3] and distance[i] + distance[i-4] >= distance[i-2]:
                return True
            if i >= 5 and distance[i-2] - distance[i-4] >= 0 and distance[i] >= distance[i-2] - distance[i-4] and distance[i-1] >= distance[i-3] - distance[i-5] and distance[i-1] <= distance[i-3]:
                return True
        return False