Easy to understand 0MS C++ solution without obscure tricks


  • 2
    X

    Consider the last three vertical segments of the path: let's assume that the pattern of them is ↑, ↓, ↑(the other pattern(↓, ↑, ↓) is just the same if we put the path upside down), now we're going to check whether next horizontal segment will intersect with any segments on the path, then we got 2 possible situations in which the current horizontal segment have no chance of intersecting with other segments except for the last three vertical ones, that is to say we just need to keep the last three ones and check them one by one when we deal with the current horizontal segment. As for the vertical situation, all the conclusions are similar.

    My C++ code:

    class Solution {
        struct Seg {
            int start[2], end[2];
            Seg(int a[], int b[]) {
                start[0] = a[0];
                start[1] = a[1];
                end[0] = b[0];
                end[1] = b[1];
            }
            bool Intersect(Seg &other) {
                if (this->start[0] == this->end[0]) return other.Intersect(*this);
                int left = this->start[0], right = this->end[0];
                if (left > right) swap(left, right);
                int up = other.start[1], down = other.end[1];
                if (up < down) swap(up, down);
                return this->start[1] >= down && this->start[1] <= up &&
                       other.start[0] >= left && other.start[0] <= right;
            }
        };
    public:
        bool isSelfCrossing(vector<int>& x) {
            deque<Seg> segs[2];
            int cur[2] = {0, 0};
            int direction = 0;
            int move[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
            for (int step: x) {
                int next[2];
                next[0] = cur[0] + step * move[direction][0];
                next[1] = cur[1] + step * move[direction][1];
                if (next[0] == next[1] && next[1] == 0) return true;
                Seg seg(cur, next);
                if (segs[1-(direction%2)].size() >= 2 && seg.Intersect(segs[1-(direction%2)][0])) return true;
                if (segs[1-(direction%2)].size() >= 3 && seg.Intersect(segs[1-(direction%2)][1])) return true;
                segs[direction%2].push_back(seg);
                if (segs[direction%2].size() > 3) segs[direction%2].pop_front();
                direction = (direction + 1) % 4;
                cur[0] = next[0];
                cur[1] = next[1];
            }
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.