每日一题：4.路径交叉（C++）

每日一题：4.路径交叉（C++）

每日一题：4.路径交叉（C++）

题目：
给你一个整数数组 distance 。
从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。

解题思路：
本题难点在于找到判断相交的方法
在自己思索不出后参考了大佬的思路写了以下代码
采取了反向思考，从不相交情况下手判断是否出现相交

解题方法：
找到所有不相交可能，有三种，逆时针外卷、逆时针内卷、逆时针外卷到逆时针内卷。

1. 首先判断移动次数是否达到相交条件，移动次数小于3必不可能相交
2. 接着假设移动为逆时针外卷，若不成立或移动多次后不成立则转为内卷，这其中找到关键位置，将内外卷部分切割。
3. 若要外卷转内卷，则移动次数必定大于4，此时还存在一种可能即闭环，首尾相交（总移动次数为5），故移动次数为5时是关键位置

class Solution {
public:
    bool isSelfCrossing(vector& distance) {
        int all_step = distance.size() ,current_step = 0; //定义整型all_step、current_step记录总移动次数和当前移动次数

        if(all_step < 4) return false;                    //判断是否移动次数大于3

        current_step = 2;                                 //接下来判断外、内卷过程是否相交，将当前步数设置为2（移动了三次，从0开始计算）

        while(current_step < all_step && distance[current_step] > distance[current_step - 2]) current_step ++;//利用while循环判断外卷，当前移动次数小于总次数时且当前移动长度大于上次最新与之平行的移动时执行循环，此时不会有相交
        if(current_step == all_step) return false;        //判断移动次数是否和总次数相等，因为current_step ++会多执行一次，所以在全部移动完成后，数值上current_step能与all_step相等

        if(distance[current_step] >= distance[current_step - 2] - (current_step > 3 ? distance[current_step - 4] : 0))//当移动次数大于4判断当前移动的长度，是否要大于或等于上个最新一次平行移动减去再上一次的平行移动长度，如果小于，就不用考虑分割外、内卷，因为内卷判断成立的话，外卷不会有与内卷过程有相交的可能,否则就要将外、内卷分割以判断内卷；若移动次数小于等于4，则只考虑移动是否造成了闭环。
        distance[current_step - 1] -= current_step > 2 ? distance[current_step - 3] : 0;//当移动次数大于3且当前移动长度大于上次最新与之平行的移动时，外卷停止，开始了内卷（或闭环），将前一次移动长度减去与之平行的最新一次移动长度，分割外卷，保留内卷进行判断。若当前移动次数为3即current_step == 2,说明3次移动距离相等，没有分割必要。
        current_step ++;                                   //移动次数加一，上一个外卷判断停止，没有进行移动，为了下面判断，移动一次

        while(current_step < all_step && distance[current_step] < distance[current_step - 2]) current_step ++;//利用while循环进行内卷判断，与外卷判断同理，如果判断停止说明移动次数耗尽或者出现相交情况

        return current_step != all_step;                   //利用当前移动次数和总次数的相等比较，判断是否出现相交状况，如果值相等说明已经走完了全程且没有相交，如果值不相等说明没有走完成全程说明出现了相交。
    }
};

作者：yi-si-cb（倚肆）
链接：https://leetcode-cn.com/problems/next-greater-element-i/solution/xie-shi-bao-li-suan-fa-by-yi-si-cb-dsk2/