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)

题目地址:leetcode Self Crossing

题意:

给定一个数组x,代表行走的距离,最初的方向是北,每走一次就按逆时针顺序变化方向(北、西、南、东)

要求只遍历一次x并且用O(1)的存储空间 判断走过的路径是否交叉。

思路:

感觉有点像海龟作图→_→

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 335 Self Crossing 题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Self Crossing
本文地址:https://www.hrwhisper.me/leetcode-self-crossing/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

3 thoughts on “leetcode Self Crossing

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

Leave a Reply

Your email address will not be published. Required fields are marked *