LeetCode 题解工作台
路径交叉
给你一个整数数组 distance 。 从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。 判…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
class Solution: def isSelfCrossing(self, distance: List[int]) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数数组 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
解题思路
方法一
class Solution:
def isSelfCrossing(self, distance: List[int]) -> bool:
d = distance
for i in range(3, len(d)):
if d[i] >= d[i - 2] and d[i - 1] <= d[i - 3]:
return True
if i >= 4 and d[i - 1] == d[i - 3] and d[i] + d[i - 4] >= d[i - 2]:
return True
if (
i >= 5
and d[i - 2] >= d[i - 4]
and d[i - 1] <= d[i - 3]
and d[i] >= d[i - 2] - d[i - 4]
and d[i - 1] + d[i - 5] >= d[i - 3]
):
return True
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each distance is evaluated once against a constant number of prior distances. Space complexity is O(1) using fixed variables to track previous steps instead of simulating coordinates. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you considering edge cases where the path touches but does not cross previous segments?
- question_mark
Notice if your solution handles sequences that expand then contract, creating potential intersections.
- question_mark
Can you simplify checks by using only the last few distances instead of full coordinate storage?
常见陷阱
外企场景- error
Simulating full coordinates unnecessarily increases space usage and complexity.
- error
Failing to check the fourth or fifth previous distance can miss overlapping loops.
- error
Incorrectly assuming only consecutive steps can cause crossing ignores geometric patterns.
进阶变体
外企场景- arrow_right_alt
Detect self-crossing in a 3D path with directional changes in three axes.
- arrow_right_alt
Find the first step where the path crosses itself and return its index.
- arrow_right_alt
Determine if a path is self-avoiding given a repeated move sequence of arbitrary length.