leetcode Self Crossing

leetcode Self Crossing

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)

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

Leetcode , , , , . permalink.

3 thoughts on “leetcode Self Crossing”

1. 我觉得这个Python版本中判断increase的条件有点问题啊，请看我做的图
https://flic.kr/p/GWVedz
。图1是增加的情况，图2是减少的情况，在两图中，t4>t2，按照Python Code中的判断，应该都是增加。这个和实际情况不符啊。还是我哪里做错了？

• 第二图属于先增加后减少的情况，一开始t2 < t4 为增加，之后 t5 + t1 - t3 < 0 就变成减少了