路径交叉
335.路径交叉
题目描述
思路：分类讨论
首先计算distance长度，如果distance小于4，则必然不会相交，返回false；如果distance长度大于等于4，才开始分类讨论。
- 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]不一定是向东移动的边，可以是任意方向的边，此时矩形发生旋转，但不影响相交，其他情况也同理。
- 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]。
- 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]。
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