细语呢喃

技术改变生活

0%

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int n = x.size();
        if(n < 4) return false;
        int t1 = 0,t2 = x[0],t3 = x[1],t4 = x[2],t5;
        bool increase = t4 > t2? true:false;
        for(int i=3;i<n;i++){
            t5 = x[i];
            if(increase && t3 >= t5){
                if(t5 + t1 <t3  i + 1 <n && x[i+1] + t2 < t4)
                    increase = false;
                else if (i + 1 <n)
                    return true;
            }
            else if(!increase && t3 <= t5)
                return true;
            t1 = t2;
            t2 = t3;
            t3 = t4;
            t4 = t5;
        }
        return false;
    }
};

 

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean isSelfCrossing(int[] x) {
        int n = x.length;
		if (n < 4) return false;
		int t1 = 0, t2 = x[0], t3 = x[1], t4 = x[2], t5;
		boolean increase = t4 > t2 ? true : false;
		for (int i = 3; i < n; i++) {
			t5 = x[i];
			if (increase && t3 >= t5) {
				if (t5 + t1 < t3 || i + 1 < n && x[i + 1] + t2 < t4)
					increase = false;
				else if (i + 1 < n)
					return true;
			}
			else if (!increase && t3 <= t5)
				return true;
			t1 = t2;
			t2 = t3;
			t3 = t4;
			t4 = t5;
		}
		return false;
    }
}

 

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def isSelfCrossing(self, x):
        """
        :type x: List[int]
        :rtype: bool
        """
        n = len(x)
        if n < 4: return False
        t1, (t2, t3, t4) = 0, x[:3]
        increase = True if t2 < t4 else False
        for i in xrange(3, n):
            t5 = x[i]
            if increase and t3 >= t5:
                if t5 + t1 - t3 < 0 or i + 1 < n and x[i + 1] + t2 - t4 < 0:
                    increase = False
                elif i + 1 < n:
                    return True
            elif not increase and t3 <= t5:
                return True
            t1, t2, t3, t4 = t2, t3, t4, t5
        return False

 

更漂亮的解法：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        for(int i=3, l=x.size(); i<l; i++) {
            // Case 1: current line crosses the line 3 steps ahead of it
            if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true;  
            // Case 2: current line crosses the line 4 steps ahead of it
            else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true; 
            // Case 3: current line crosses the line 6 steps ahead of it
            else if(i>=5 && x[i-2]>=x[i-4] && x[i]+x[i-4]>=x[i-2] && x[i-1]<=x[i-3] && x[i-1]+x[i-5]>=x[i-3]) return true;  
        }
        return false;
    }

/*               i-2
    case 1 : i-1┌─┐
                └─┼─>i
                 i-3

                    i-2
    case 2 : i-1 ┌────┐
                 └─══>┘i-3
                 i  i-4      (i overlapped i-4)

    case 3 :    i-4
               ┌──┐ 
               │i<┼─┐
            i-3│ i-5│i-1
               └────┘
                i-2

*/
};

 

本题是leetcode 335 Self Crossing 题解，

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

请我喝杯咖啡吧~