0%

### leetcode Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x metres to the north, then x metres to the west,x metres to the south, x 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) 题目地址：leetcode Self Crossing

There are only 3 scenarios where it won't cross itself.

1. The distances of the moves parallel to each other keeps going up (growing spiral).
2. The distances of the moves parallel to each other keeps going down (shrinking spiral).
3. The distances of the moves parallel to each other first keeps going up, then keeps going down (shrinking spiral inside of the growing spiral), and never goes up.

from  https://leetcode.com/discuss/88038/java-o-n-o-1-0ms-solution-with-explanation

• 平行移动的距离是不断的增加的（螺旋形上升）
• 平行移动的距离是不断的减少的（螺旋形下降）
• 平行移动的距离先增加后减少，并且再也不增加。

C++

Java

Python

from: https://leetcode.com/discuss/88054/java-oms-with-explanation