[数据结构与算法]力扣每日一题2021-10-29路径交叉

335.路径交叉

题目描述

路径交叉

思路：分类讨论

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

1. distance[i]与distance[i-3]相交：此时必定满足$distance[i]>=distance[i?2]$，同时满足$distance[i?1]<=distance[i?3]$。distance[i]不一定是向东移动的边，可以是任意方向的边，此时矩形发生旋转，但不影响相交，其他情况也同理。
2. distance[i]与distance[i-4]相交：此时必定满足$distance[i?1]=distance[i?3]$，同时满足$distance[i]+distance[i?4]>=distance[i?2]$。
3. distance[i]与distance[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]$。

Java实现

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;
    }
}

Python实现

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