难度: Hard
给你一个整数数组 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 <= 1051 <= distance[i] <= 105运行时间: 36 ms
内存: 22.7 MB
class Solution:
def isSelfCrossing(self, distance: List[int]) -> bool:
n = len(distance)
# 处理第 1 种情况
i = 0
while i < n and (i < 2 or distance[i] > distance[i - 2]):
i += 1
if i == n:
return False
# 处理第 j 次移动的情况
if i == 3 and distance[i] == distance[i - 2] or i >= 4 and distance[i] >= distance[i - 2] - distance[i - 4]:
distance[i - 1] -= distance[i - 3]
i += 1
# 处理第 2 种情况
while i < n and distance[i] < distance[i - 2]:
i += 1
return i != n
这个题解的思路是模拟路径，判断是否会出现路径相交的情况。具体分为以下几步： 1. 先处理第一种情况，即一直向外扩张的螺旋路径，直到第i次移动小于等于第i-2次移动，说明开始向内收缩，有可能出现相交。 2. 再处理第i次移动和第i-3次移动组成的矩形区域。如果第i次移动距离等于第i-2次移动距离，或者大于等于第i-2次移动距离减去第i-4次移动距离，说明会与第i-3次移动路径相交。需要将第i-1次移动减去第i-3次移动。 3. 最后处理第二种情况，即处理后续的移动，看是否会出现第i次移动小于第i-2次移动的情况，如果出现则说明路径相交。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def isSelfCrossing(self, distance: List[int]) -> bool:
n = len(distance)
# 处理第 1 种情况：一直向外扩张的螺旋路径
i = 0
while i < n and (i < 2 or distance[i] > distance[i - 2]):
i += 1
if i == n:
return False
# 处理第 i 次移动的情况：判断是否与第i-3次移动相交
if i == 3 and distance[i] == distance[i - 2] or i >= 4 and distance[i] >= distance[i - 2] - distance[i - 4]:
distance[i - 1] -= distance[i - 3]
i += 1
# 处理第 2 种情况：判断后续移动是否会出现相交
while i < n and distance[i] < distance[i - 2]:
i += 1
return i != n
在解析路径交叉问题时，只考虑到第i-4次移动的原因是基于路径的走向。一个螺旋形状的路径只需要考虑最近的几次移动来判断是否会交叉。具体来说，第i次移动只可能与第i-3次移动、第i-4次移动和第i-5次移动形成的路径相交。在大多数情况下，只需要考虑到第i-4次移动，因为这能覆盖所有可能的交叉情况。更早的移动，如第i-6次或之前的移动，由于路径的螺旋特性，通常不会与第i次移动产生交叉。
判断第i次移动与第i-3次移动可能相交的情况是基于两者形成的路径的几何位置。如果第i次移动的距离至少与第i-2次移动的距离相等，且第i-2次移动的距离大于或等于第i-4次移动的距离，则第i次移动可能与第i-3次移动的路径相交。这是因为这种情况下第i次移动足够长，可以延伸到或穿过第i-3次移动形成的路径。
这个条件是基于对路径的几何分析得出的。在螺旋型移动中，第i次移动如果要与第i-3次移动相交，它的长度必须至少达到第i-2次移动的长度减去第i-4次移动的长度。这是因为第i-2次移动和第i-4次移动定义了一个外部边界，第i次移动需要足够长才能穿越这个边界并与第i-3次移动的路径相交。
代码中确实没有明确地处理数组长度小于4的情况。然而，在主循环中，如果数组长度小于4，由于足够的条件分支不会被满足（例如i >= 4），逻辑将自然流向返回`false`，表明不会有交叉。这种处理方式依赖于循环和条件语句的结构，确保在数组长度不足以形成复杂路径时，程序能够正确地判断出不存在交叉。