Problem: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)
这题做得很狼狈啊呜哇啊啊啊!
思路来得蛮快的,因为cross的情况一共就三种,4弯cross,5个弯cross和6个弯cross:
#4个弯 5个弯 6个弯 1 1 1
┌───┐ ┌───┐ ┌───┐
│2 │0 │2 │0 │ │0
└───┼> │ ↑ │2 │←┐
3 └───┘5 │ 5 │4
4 └─────┘
3
根据上图写出三种情况的判断式,这里错了好几次,第三种情况总是少了条件= - =
Code:
def isSelfCrossing(self, x):
l = (len(x))
iscross = False
if l < 4: return False
for i in range(3, l):
#情况1
if x[i-3]>=x[i-1] and x[i-2]<=x[i]:
return True
#情况2
if i>=4 and x[i-4]+x[i]>=x[i-2] and x[i-3]==x[i-1]:
return True
#情况3
if i>=5 and x[i-5]+x[i-1]>=x[i-3] and x[i-4]+x[i]>=x[i-2] and x[i-2]>=x[i-4] and x[i-2]>x[i-4] and x[i-3]>x[i-5] and x[i-1]<x[i-3]:
return True
iscross = False
return iscross
很粗暴的解法,第三种写了辣么长,不过好歹AC了。
围观别人家的代码:
①
class Solution(object):
def isSelfCrossing(self, x):
return any(d >= b > 0 and (a >= c or a >= c-e >= 0 and f >= d-b)
for a, b, c, d, e, f in ((x[i:i+6] + [0] * 6)[:6]
for i in xrange(len(x))))
②
class Solution(object):
def isSelfCrossing(self, x):
n = len(x)
x.append(0.5) # let x[-1] = 0.5
if n < 4: return False
grow = x[2] > x[0] for i in range(3,n):
if not grow and x[i] >= x[i-2]: return True
if grow and x[i] <= x[i-2]:
grow = False
if x[i] + x[i-4] >= x[i-2]:
x[i-1] -= x[i-3]
return False
对python的一些用法还是不够熟悉,毕竟第一门学的是C,写出来总是看着很繁琐。相比其他语言,python的代码都能缩到超短,多加练习啦~