【LeetCode每日一题】（内卷难题）335. 路径交叉

【LeetCode每日一题】（内卷难题）335. 路径交叉

文章目录

题目

一、解题思路

二、结果

1.注意点

2.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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/self-crossing

一、解题思路

1. 首先我们要了解到不相交的情况只有：外卷、内卷、外卷转内卷
2. 要理解从 i 条开始， 相交的情况只出现在 (i)  和 （i-3）(i -4) (i-5)  之间， 且如果 i 和  i - 3 - 4*k 相交的话，那么必然先与 i - 3 相交，确保 i 与 i -3 不相交，那么可以保证整个不交叉 
3. 这样理解很抽象，可以看下图，情况的分类：

 

二、结果
1.注意点

• 运用到了数学归纳法
• 6条之后，相交便呈现规律性变化
• 4条的相交情况可以和5条的一种相交情况合并

2.C++代码

代码如下（示例）：

class Solution {
public:
    bool isSelfCrossing(vector& x) {
        if(x.size() < 4) return false;//少于四条绝对不相交
        if(x[2] <= x[0] && x[3] >= x[1])
            return true;//四条情况下，第四条与第一条相交
        if(x.size() > 4 && x[3] <= x[1] && x[4] >= x[2])
            return true;//五条情况下，最后一条与第二条相交
        if(x.size() > 4 && x[3] == x[1] && x[4] + x[0] >= x[2])
            return true;//五条情况下，最后一条与第一条重合相交
        for(int i = 5;i < x.size();i++){//多于五条之后，相交便呈现规律性变化
            if(x[i - 1] <= x[i - 3] && x[i] >= x[i - 2])
                return true;
            if(x[i - 1] <= x[i - 3] && x[i - 4] <= x[i - 2] && x[i] + x[i - 4] >= x[i - 2] && x[i - 5] + x[i - 1] >= x[i - 3])
                return true;
        }
        return false;
    }
};

---

总结

运用了数学归纳法，来寻找规律，内卷的题目紧跟实时，哈哈哈哈！！！！

打开第三天，坚持坚持 加油加油！！！！！