class Solution(object):
def checkPossibility(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
def check(i):
if i >= len(nums):
return True
temp = [nums[j] for j in xrange(len(nums)) if j != i]
return all(temp[j]>=temp[j-1] for j in xrange(1, len(temp)))
i = 1
while i < len(nums) and nums[i] >= nums[i-1]:
i += 1
return check(i) or check(i-1)


class Solution(object):
def pathSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def decomp(n):
return n/100, (n/10)%10, n%10

tree = [[-1]*17 for _ in xrange(6)]
for n in nums:
d, p, v = decomp(n)
tree[d][p] = v
ans = 0
for d in xrange(1, 5):
for p in xrange(1, 17):
if tree[d][p] != -1 and tree[d+1][2*p-1] == tree[d+1][2*p] == -1:
t = d
s = p
while t > 0:
ans += tree[t][s]
t -= 1
s = (s+1) / 2
return ans


|a1-a2|, |a2-a3|, ..., |an-1-an|

class Solution(object):
def constructArray(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[int]
"""
ans = []
t = [1, n]
for i in xrange(k):
if i & 1:
ans.append(t[0])
t[0] += 1
else:
ans.append(t[1])
t[1] -= 1
temp = range(t[0], t[1]+1)
if k & 1:
temp = temp[::-1]
return ans + temp


class Solution(object):
def findKthNumber(self, m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
def divide(t, n, m):
lo = hi = 0
for i in xrange(1, n+1):
cur = min((t-1) / i, m)
lo += cur
if t % i == 0 and t/i <= m:
cur += 1
hi += cur
return lo, hi

n, m = min(n, m), max(n, m)
a = 1
b = n * m
while True:
c = (a+b)/2
lo, hi = divide(c, n, m)
if lo < k <= hi:
return c
if k <= lo:
b = c-1
else:
a = c+1