In this Leetcode Self Crossing problem solution, 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.
Problem solution in Python.
class Solution: def isSelfCrossing(self, x): """ :type x: List[int] :rtype: bool """ if len(x) < 4: return False x.append(0) x.append(0) for i in range(2,len(x)-2): if x[i] <= x[i-2]: tmp = x[i-2] - x[i-4] if tmp > 0: if x[i]>=tmp: if x[i+1] != 0 and x[i+1] >= x[i-1]-x[i-3]: return True else: if x[i+1] >= x[i-1]: return True else: if x[i+1] >= x[i-1]: return True return False
Problem solution in Java.
public boolean isSelfCrossingExpand(int[] x, int start){ for (int i=start;i x[i-2]){ continue; } else { int bar = (i>=4) ? x[i-4] : 0; if (x[i] <= x[i-2] && x[i] >= (x[i-2] - bar)){ if ( i+1 == x.length){ return false; } if (x[i+1] >= (x[i-1] - x[i-3])){ return true; } return isSelfCrossingShrink(x,i+2); } else { return isSelfCrossingShrink(x,i+1); } } } return false; } public boolean isSelfCrossingShrink(int[] x, int start){ for (int i=start; i= x[i-2]) return true; } return false; } public boolean isSelfCrossing(int[] x) { if (x.length<=3) return false; if (x[2] <= x[0]) return isSelfCrossingShrink(x,3); return isSelfCrossingExpand(x,3); } }
Problem solution in C++.
class Solution { public: bool isSelfCrossing(vector<int>& x) { if(x.size() < 4) return false; for(int i = 3; i < x.size(); i++) { if(x[i] >= x[i-2] and x[i-1] <= x[i-3]) return true; if(i >= 4) { if(x[i-1] == x[i-3] and x[i] >= x[i-2]-x[i-4]) return true; } if(i >= 5) { if(x[i-2]-x[i-4] >= 0 and x[i] >= x[i-2]-x[i-4] and x[i-1] >= x[i-3]-x[i-5] and x[i-1] <= x[i-3]) return true; } } return false; } };
Problem solution in C.
bool isSelfCrossing(int* x, int xSize) { int i; for (i = 2; i < xSize && x[i] > x[i-2]; i++); if ((++i < xSize) && ((i > 4 && x[i-1]+x[i-5]>=x[i-3]) || (i==4 && x[i-1]==x[i-3])) && x[i]+x[i-4] >= x[i-2]) return true; for (; i < xSize && x[i] < x[i-2]; i++); return (i < xSize); }