LeetCode 第335题：路径交叉

📖 文章摘要

本文详细解析LeetCode第335题“路径交叉”，这是一道困难难度的几何问题。文章提供了数学分析的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升几何算法能力的程序员。

核心知识点： 几何、路径分析、数学推理、边界判断
难度等级： 困难
推荐人群： 具有基础算法知识，想要提升几何算法能力的程序员

题目描述

给你一个整数数组 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 <= 10^5
• 1 <= distance[i] <= 10^5

解题思路

方法：数学分析

通过分析路径交叉的可能情况，可以归纳出三种主要的交叉情况。

关键点：

• 第i步与第i-3步交叉
• 第i步与第i-4步交叉
• 第i步与第i-5步交叉
• 其他情况不可能交叉

具体步骤：

1. 处理特殊情况（长度小于4的数组）
2. 遍历数组，检查每一步
3. 判断三种交叉情况
4. 返回最终结果

时间复杂度：O(n) 空间复杂度：O(1)

图解思路

交叉情况分析表

情况	条件	示例	说明
第一种	i与i-3交叉	[2,1,1,2]	形成矩形
第二种	i与i-4交叉	[1,1,2,1,1]	形成五边形
第三种	i与i-5交叉	[1,1,2,2,1,1]	形成六边形

示例图解

第一种情况：
  ┌──┐
  │  │
  └──┘

第二种情况：
  ┌───┐
  │   │
  └─┐ │
    └─┘

第三种情况：
  ┌───┐
  │   │
  │ ┌─┘
  └─┘

代码实现

C# 实现

public class Solution {
    public bool IsSelfCrossing(int[] distance) {
        if (distance == null || distance.Length < 4) return false;
        
        for (int i = 3; i < distance.Length; i++) {
            // 第一种情况：第i步与第i-3步交叉
            if (distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3]) {
                return true;
            }
            
            // 第二种情况：第i步与第i-4步交叉
            if (i >= 4 && distance[i-1] == distance[i-3] && 
                distance[i] + distance[i-4] >= distance[i-2]) {
                return true;
            }
            
            // 第三种情况：第i步与第i-5步交叉
            if (i >= 5 && distance[i-2] >= distance[i-4] && 
                distance[i-1] <= distance[i-3] && distance[i-1] >= distance[i-3] - distance[i-5] && 
                distance[i] >= distance[i-2] - distance[i-4]) {
                return true;
            }
        }
        
        return false;
    }
}

Python 实现

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        if len(distance) < 4:
            return False
        
        for i in range(3, len(distance)):
            # 第一种情况：第i步与第i-3步交叉
            if distance[i] >= distance[i-2] and distance[i-1] <= distance[i-3]:
                return True
            
            # 第二种情况：第i步与第i-4步交叉
            if i >= 4 and distance[i-1] == distance[i-3] and \
               distance[i] + distance[i-4] >= distance[i-2]:
                return True
            
            # 第三种情况：第i步与第i-5步交叉
            if i >= 5 and distance[i-2] >= distance[i-4] and \
               distance[i-1] <= distance[i-3] and distance[i-1] >= distance[i-3] - distance[i-5] and \
               distance[i] >= distance[i-2] - distance[i-4]:
                return True
        
        return False

C++ 实现

class Solution {
public:
    bool isSelfCrossing(vector<int>& distance) {
        if (distance.size() < 4) return false;
        
        for (int i = 3; i < distance.size(); i++) {
            // 第一种情况：第i步与第i-3步交叉
            if (distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3]) {
                return true;
            }
            
            // 第二种情况：第i步与第i-4步交叉
            if (i >= 4 && distance[i-1] == distance[i-3] && 
                distance[i] + distance[i-4] >= distance[i-2]) {
                return true;
            }
            
            // 第三种情况：第i步与第i-5步交叉
            if (i >= 5 && distance[i-2] >= distance[i-4] && 
                distance[i-1] <= distance[i-3] && distance[i-1] >= distance[i-3] - distance[i-5] && 
                distance[i] >= distance[i-2] - distance[i-4]) {
                return true;
            }
        }
        
        return false;
    }
};

执行结果

C# 实现

• 执行用时：84 ms
• 内存消耗：39.8 MB

Python 实现

• 执行用时：36 ms
• 内存消耗：15.2 MB

C++ 实现

• 执行用时：0 ms
• 内存消耗：7.3 MB

性能对比

语言	执行用时	内存消耗	特点
C#	84 ms	39.8 MB	代码结构清晰
Python	36 ms	15.2 MB	实现简洁
C++	0 ms	7.3 MB	性能最优

代码亮点

1. 🎯 数学分析清晰
2. 💡 条件判断简洁
3. 🔍 边界处理完整
4. 🎨 代码结构优雅

常见错误分析

1. 🚫 忽略数组长度小于4的情况
2. 🚫 交叉条件判断不完整
3. 🚫 边界条件处理错误
4. 🚫 数组索引越界

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
数学分析	O(n)	O(1)	效率高	不直观
模拟路径	O(n)	O(n)	直观易懂	空间消耗大

相关题目

• LeetCode 149. 直线上最多的点数 - 困难
• LeetCode 223. 矩形面积 - 中等
• LeetCode 391. 完美矩形 - 困难

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第335题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！