class Solution(object):
def findUnsortedSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
sn = sorted(nums)
i = 0
while i < len(nums) and nums[i] == sn[i]:
i += 1
if i == len(nums):
return 0
j = len(nums) - 1
while j >= 0 and nums[j] == sn[j]:
j -= 1
return j-i+1


class Solution(object):
def killProcess(self, pid, ppid, kill):
"""
:type pid: List[int]
:type ppid: List[int]
:type kill: int
:rtype: List[int]
"""
mp = {}
for c, p in zip(pid, ppid):
if p not in mp:
mp[p] = []
mp[p].append(c)
visited = {kill}
ans = [kill]
p = 0
while p < len(ans):
for c in mp.get(ans[p], []):
if c not in visited:
ans.append(c)
p += 1
return ans


f(i, j) = 1 + f(i+1, j+1)

f(i, j) = max(f(i, j+1), f(i+1, j))

class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
if not word1 or not word2:
return len(word1)+len(word2)
n = len(word1)
m = len(word2)
dp = [[0]*m for _ in xrange(n)]
if word1[n-1] == word2[m-1]:
dp[n-1][m-1] = 1
ml = dp[n-1][m-1]
for i in xrange(m-2, -1, -1):
if word1[n-1]==word2[i]:
dp[n-1][i] = 1
else:
dp[n-1][i] = dp[n-1][i+1]
ml = max(ml, dp[n-1][i])
for i in xrange(n-2, -1, -1):
if word1[i]==word2[m-1]:
dp[i][m-1] = 1
else:
dp[i][m-1] = dp[i+1][m-1]
ml = max(ml, dp[i][m-1])
for j in xrange(m-2, -1, -1):
for i in xrange(n-2, -1, -1):
if word1[i]==word2[j]:
dp[i][j] = 1+dp[i+1][j+1]
else:
dp[i][j] = max(dp[i][j+1], dp[i+1][j])
ml = max(ml, dp[i][j])
return n+m-2*ml


class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
n, m = len(word1), len(word2)
dp = [[0]*(m+1) for _ in xrange(n+1)]
ml = 0
for j in xrange(m-1, -1, -1):
for i in xrange(n-1, -1, -1):
if word1[i]==word2[j]:
dp[i][j] = 1+dp[i+1][j+1]
else:
dp[i][j] = max(dp[i][j+1], dp[i+1][j])
ml = max(ml, dp[i][j])
return n+m-2*ml


# Definition for a point.
# class Point(object):
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b

class ConvexHull(object):

def __init__(self, points):
self.pts = points
self.hull = []

def get(self):
if len(self.hull) > 0:
return self.hull

pts, hull = self.pts, self.hull
is_turn_right = self.is_turn_right
pts.sort(key=lambda p: (p.x, p.y))

def calc_hull(pts):
ret = []
for p in pts:
if len(ret) < 2:
ret.append(p)
continue
while len(ret) > 1 and not is_turn_right(ret, p):
ret.pop()
ret.append(p)
return ret

# calculate upper hull
upper = calc_hull(pts)

# calculate lower hull
lower = calc_hull(reversed(pts))

hull = upper + lower[1:-1]

return list(set(hull))

def is_turn_right(self, pts, r):
p, q = pts[-2], pts[-1]
u = (q.x - p.x, q.y - p.y)
v = (r.x - p.x, r.y - p.y)
return u[0] * v[1] - u[1] * v[0] <= 0

class Solution(object):
def outerTrees(self, points):
"""
:type points: List[Point]
:rtype: List[Point]
"""
ch = ConvexHull(points)
return ch.get()