You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
Example 1:
Given x = [2, 1, 1, 2],
┌───┐
│ │
└───┼──>
│
Return true (self crossing)
Example 2:
Given x = [1, 2, 3, 4],
┌──────┐
│ │
│
│
└────────────>
Return false (not self crossing)
Example 3:
Given x =[1, 1, 1, 1], ┌───┐ │ │ └───┼> Return true (self crossing)
思路：如果相交，必定是经过同一点，记录所有点，比较即可。
int a = 0,b = 0,len = x.length; HashSet<String> recodePoint = new HashSet<String>(); recodePoint.add(a + "-" + b);//start point if(len == 0) return false; for (int i = 0; i < len; i++) { if(i % 4 == 0){ for(int j = 0;j < x[i]; j++){ String point = a+"-"+ ++b; if(recodePoint.contains(point)) return true; else recodePoint.add(point); } } if(i % 4 == 1) for(int j = 0;j < x[i]; j++){ String point = --a+"-"+b; if(recodePoint.contains(point)) return true; else recodePoint.add(point); } if(i % 4 == 2) for(int j = 0;j < x[i]; j++){ String point = a+"-"+ --b; if(recodePoint.contains(point)) return true; else recodePoint.add(point); } if(i % 4 == 3) for(int j = 0;j < x[i]; j++){ String point = ++a+"-"+ b; if(recodePoint.contains(point)) return true; else recodePoint.add(point); } } return false;
原文：http://www.cnblogs.com/zhaihua/p/5554986.html