The best submission in C searching for the crossing patterns is the key


  • 41

    After drawing a few crossing cases ourselves, we can simply find out there are two basic patterns:

    • x[i-1]<=x[i-3] && x[i]>=x[i-2] the ending circle line cross the beginning circle line in one circle;
    • i>=5 && x[i-1]<=x[i-3] && x[i]>=x[i-2]-x[i-4] the second line of the next circle cross the the beginning of the previous circle between two adjacent circles;

    But still that is not over yet, how about some special cases? How about the first line of the next circle and the previous circle? Yeah, the beginning line of the next circle can overlap the the first line of the previous circle - another two adjacent circles case:

    • i>=4 && x[i-1]==x[i-3] && x[i]>=x[i-2]-x[i-4]

    Quite straightforward. Then we can test our patterns now, however soon we will find out that the second cases is not strong enough to cover all possible situations - the second line of the next circle crossing the previous circle at the its first line

    • [3,3,3,2,1,1] is an example here, so x[i-2]>=x[i-4] then must be added to our conditions;
    • [3,3,4,4,10,4,4,,3,3] is another typical example for x[i-3]<=x[i-1]+x[i-5] condition, which also should be added to make the constrained conditions stronger;

    At last, we make it! Bang! End of story with a very terse, clean and efficient code as follows.

    Updated: 2016-09-12 For better and easier reasoning, here is the thinking thread.
    Suppose i is the current line, then:

    • i and i-3 can cross
    • i and i-4 can cross
    • i and i-5 can cross

    no more or no less just exactly the right combination.

    Now it's time for us to restrict the conditions to make them just happen.

    i and i-3

    i>=i-2 && i-1<=i-3

    i and i-4

    i+i-4>=i-2 && i-1==i-3

    i and i-5

    i+i-4>=i-2 && i-2>=i-4 && i-1+i-5>=i-3 && i-1<=i-3


    In C

    bool isSelfCrossing(int* x, int size)
    {
        for(int i = 3; i < size; i++)
        {
            if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true;
            if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true;
            if(i>=5 && x[i-2]-x[i-4]>=0 && x[i]>=x[i-2]-x[i-4] && x[i-1]>=x[i-3]-x[i-5] && x[i-1]<=x[i-3]) return true;
        }
        return false;
    }
    

    In C++

    class Solution {
    public:
        bool isSelfCrossing(vector<int>& x) {
    	for(int i = 3; i < x.size(); i++) {
    		if(x[i-1]<=x[i-3] && x[i]>=x[i-2]) return true;
    		if(i>3 && x[i]+x[i-4]>=x[i-2] && x[i-1]==x[i-3]) return true;
    		if(i>4 && x[i-1]+x[i-5]>=x[i-3] && x[i-1]<=x[i-3] && x[i]+x[i-4]>=x[i-2] && x[i-4]<=x[i-2]) return true;
    	}
    	return false;
        }
    };
    

Log in to reply
 

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