题目描述：

LeetCode 335. 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)

题目大意：

给定一个包含n个正整数的数组x。从(0, 0)点出发先向北移动x[0]米，然后向西移动x[1]米，再向南移动x[2]米，再向东移动x[3]米，以此类推。换言之，每一次移动之后都逆时针旋转一次方向。

编写一个一趟遍历算法，并且只使用O(1)的额外空间来确定路径是否自相交。

测试用例如题目描述。

解题思路：

路径不相交只包含下面3种情况：

1. 路径螺旋扩增

2. 路径螺旋缩减

3. 先螺旋扩增，再螺旋缩减

可以在纸上画出草图帮助理解。

使用变量n, w, s, e维护四个方向的当前边界，expand记录路径是在扩增还是缩减，然后分方向讨论。

对于情况3，当路径由扩增转为缩减时，如果当前方向与其最近一次的同方向路径有重叠，还需要更新与其垂直的方向边界。

下面的Python代码可读性较差，不建议参考。

Python代码：

class Solution(object):
    def isSelfCrossing(self, x):
        """
        :type x: List[int]
        :rtype: bool
        """
        if len(x) < 4: return False
        n, w, s, e = x[0], -x[1], x[0] - x[2], x[3] - x[1] #range of n, w, s, e
        if s >= 0 and e >= 0: return True
        if e == 0: n = 0 #special case for e == 0
        expand = e > 0 #judge if the screw is expanding or not
        for i in range(4, len(x)):
            mod = i % 4
            if mod == 0: #North
                N = s + x[i]
                if not expand and N >= n: 
                    return True
                if expand and N <= n:
                    expand = False
                    if N >= n - x[i - 4]:
                        w = e - x[i - 1] + x[i - 3]
                n = N
            elif mod == 1: #West
                W = e - x[i]
                if not expand and W <= w:
                    return True
                if expand and W >= w:
                    expand = False
                    if W <= w + x[i - 4]:
                        s = n - x[i - 1] + x[i - 3]
                w = W
            elif mod == 2: #South
                S = n - x[i]
                if not expand and S <= s:
                    return True
                if expand and S >= s:
                    expand = False
                    if S <= s + x[i - 4]:
                        e = w + x[i - 1] - x[i - 3]
                s = S
            else: #East
                E = w + x[i]
                if not expand and E >= e:
                    return True
                if expand and E <= e:
                    expand = False
                    if E >= e - x[i - 4]:
                        n = s + x[i - 1] - x[i - 3]
                e = E
        return False

 

本文链接：http://bookshadow.com/weblog/2016/02/23/leetcode-self-crossing/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码