​LeetCode刷题实战335：路径交叉

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 路径交叉，我们先来看题面：

https://leetcode-cn.com/problems/self-crossing/

You are given an array of integers distance.

You start at point (0,0) on an X-Y plane and you move distance[0] meters to the north, then distance[1] meters to the west, distance[2] meters to the south, distance[3] meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.

Return true if your path crosses itself, and false if it does not.

给定一个含有 n 个正数的数组 x。从点 (0,0) 开始，先向北移动 x[0] 米，然后向西移动 x[1] 米，向南移动 x[2] 米，向东移动 x[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

编写一个 O(1) 空间复杂度的一趟扫描算法，判断你所经过的路径是否相交。

示例

解题

https://leetcode-cn.com/problems/self-crossing/solution/c3ge-bu-zou-miao-jie-ci-ti-by-xiaohu9527-96n6/

情况一（只有外圈）：

这种情况直接一个外圈就可以走完，也就是说我们只需要一行代码去走完这个外圈。

while(i < n && dist[i] > dist[i - 2]) ++i;

情况二（外圈加内圈）：

这里我称之为内外不重合的情况！图中红色不超过黄色！这种情况我们是不需要

调整圈值的。也就是说在情况一的基础上可以直接加一层内圈的代码。

for(++i; i < n && dist[i] < dist[i - 2]; ++i);

情况三（外圈加内圈）：

这里我将它称为重合的情况！图中的红色超过了黄色。为了不使新的内圈碰到

之前的外圈。我们要调整i-1的值. 调整的代码为，先判断是否重合，如果

重合则调整i-1，我在图中标记了几个边的位置。

if (dist[i] >= dist[i - 2] - dist[i - 4]) dist[i - 1] -= dist[i - 3];

class Solution {
public:
    bool isSelfCrossing(vector<int>& dist) {
        //避免讨论边界问题！
        dist.insert(dist.begin(), 4, 0);
        int i = 4, n = dist.size();
        //外圈，一直向外面转，走到往里走的第一个点时停止,如果走完则说明不相交
        while(i < n && dist[i] > dist[i - 2]) ++i;
        if (i == n) return false;

        //看情况调整
        if (dist[i] >= dist[i - 2] - dist[i - 4])
            dist[i - 1] -= dist[i - 3];

        //内圈，往里走，这一圈必须全部往里走并且走完，否则相交
        for(++i; i < n && dist[i] < dist[i - 2]; ++i);
        return i != n;
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。