My Java solution. Straight forward


  • 0
    Z

    The intersect happens only in 2 cases.

    case 1: if go up, it may intersect the last top or the second last bottom. the same goes for go left and go down and go right.You have to keep track the last 8 segments.

    case 2: this is tricky. It only happens in the fifth step. Going up and go through the (0,0).

    public class Solution {
        public boolean isSelfCrossing(int[] x) {
            // older 
            int[] top0 = null;
            int[] left0 = null;
            int[] bottom0 = null;
            int[] right0 = null;
            // neweast 
            int[] top1 = null;
            int[] left1 = null;
            int[] bottom1 = null;
            int[] right1 = null;
            
            int[] cur = new int[4];
            for(int i=0;i<x.length;i++) {
                int[] tmp = new int[4];
                int v = x[i];
                switch(i%4){
                    case 0:
                        setVec(tmp,cur,0,v);
                        if(top1 != null && isIntersect(top1,tmp) || bottom0 != null && isIntersect(bottom0,tmp)
                            // sepecial case: line go though (0,0)
                            || tmp[0] == 0 && tmp[1] <0 && tmp[2] == 0 && tmp[3] >= 0) {
                            return true;
                        }
                        cur = tmp;
                        right0 = right1;
                        right1 = cur;
                        break;
                    case 1:
                        setVec(tmp,cur,-v,0);
                        if(left1 != null && isIntersect(left1,tmp) || right0 != null && isIntersect(right0,tmp)) {
                            return true;
                        }
                        cur = tmp;
                        top0 = top1;
                        top1 = cur;
                        break;
                    case 2:
                        setVec(tmp,cur,0,-v);
                        if(bottom1 != null && isIntersect(bottom1,tmp) || top0 != null && isIntersect(top0,tmp)) {
                            return true;
                        }
                        cur = tmp;
                        left0 = left1;
                        left1 = cur;
                        break;
                    case 3:
                        setVec(tmp,cur,v,0);
                        if(right1 != null && isIntersect(right1,tmp) || left0 != null && isIntersect(left0,tmp) ) {
                            return true;
                        }
                        cur = tmp;
                        bottom0 = bottom1;
                        bottom1 = cur;
                        break;
                }
            }
            return false;
        }
        private void setVec(int[] dest, int[] source,int x,int y) {
            dest[0] = source[2];
            dest[1] = source[3];
            dest[2] = source[2] + x;
            dest[3] = source[3] + y;
        }
        private boolean isIntersect(int[] a,int[] b) {
    
            if(a[0] == a[2]) {
                return b[1] >= Math.min(a[1],a[3]) && b[1] <= Math.max(a[1],a[3]) && 
                     a[0] >= Math.min(b[0],b[2]) && a[0] <= Math.max(b[0],b[2]);
            }
            return isIntersect(b,a);
        }
    }

Log in to reply
 

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