3段值得学习的python code

Item 1:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

很简单的stack的应用，代码如下：

def item1(astr):
    #astr: a string compose of "(){}[]"
    ll=[]
    index=0
    balanced=True
    while index < len(astr) and balanced:
        ch=astr[index]
        if ch in "([{":
            ll.append(ch)
        else:
            if len(ll)==0:
                balanced=False
            else:
                top=ll.pop()
                if not matches(top,ch):
                    balanced=False
        index+=1
    if balanced and len(ll)==0:
        return True
    else:
        return False

def matches(open,close):
    opens="([{"
    closes=")]}"
    return opens.index(open)==closes.index(close)


print(item1('{{([][])}()}'));
print(item1('[{()]'));

Item 2: Additive number

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

这个我没有写出来，参照别人的来学习一下，只是把类改成了函数而已。
http://bookshadow.com/weblog/2015/11/18/leetcode-additive-number/

def isAdditiveNum(num):
    #num: a number
    k=str(num)
    n=len(k)
    for i , j in itertools.combinations(range(1,n),2):
        a,b=k[:i],k[i:j]
        if a!=str(int(a)) or b != str(int(b)):
            continue
        while j < n:
            c=str(int(a)+int(b))
            if not k.startswith(c,j):
                break
            j+=len(c)
            a,b=b,c
        if j==n:
            return True
    return False

print(isAdditiveNum(112358))
print(isAdditiveNum(199100199))

def isAdditiveNum2(num):
    #num:a number
    k=str(num)
    def isValid(astr):
        #astr: string
        return len(astr)==1 or astr[0]!='0'

    def search(a,b,c):
        d=str(int(a)+int(b))
        if not isValid(d) or not c.startswith(d):
            return False
        if c==d:
            return True
        return search(b,d,c[len(d):])

    size=len(k)
    for x in range(1,size//2+1):
        for y in range(x+1,size):
            a,b,c=k[:x],k[x:y],k[y:]
            if not isValid(a) or not isValid(b):
                continue
            if search(a,b,c):
                return True
    return False



print(isAdditiveNum2(112358))
print(isAdditiveNum2(199100199))

Item 3:

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

解法可以直接参考：

def longestIncreasingPath(matrix):
    #matrix: List[List[int]]
    #rtype: int
    if not matrix: return 0
    m,n=len(matrix),len(matrix[0])
    dis=[ [0] * n for i in range(m)]
    return max([dfs(i,j,m,n,matrix,dis) for j in range(n) for i in range(m)])

def dfs(x,y,m,n,matrix,dis):
    if dis[x][y]: return dis[x][y]
    for dx,dy in ([(1,0),(-1,0),(0,1),(0,-1)]):
        nx,ny=x+dx,y+dy
        if nx>=0 and nx<m and ny>=0 and ny<n and matrix[x][y]<matrix[nx][ny]:
            dis[x][y]=max(dis[x][y],dfs(nx,ny,m,n,matrix,dis))
    dis[x][y]+=1
    return dis[x][y]

exp1=[[9,9,4],
      [6,6,8],
      [2,1,1]]

exp2=[[3,4,5],
      [3,2,6],
      [2,2,1]]


#print(longestIncreasingPath(exp1))
#print(longestIncreasingPath(exp2))

import operator
def longestIncreasingPath2(matrix):
    #matrix: List[List[int]]
    #rtype: int
    h=len(matrix)
    if h==0 : return 0
    w=len(matrix[0])
    dp=[[1]*w for i in range(h)]
    slist=sorted([(i,j,val)
            for i,row in enumerate(matrix)
            for j,val in enumerate(row)],
            key=operator.itemgetter(2))
    for x,y,val in slist:
        for dx,dy in zip([1,0,-1,0],[0,1,0,-1]):
            nx,ny=x+dx,y+dy
            if h>nx>=0 and w>ny>=0 and matrix[nx][ny] > matrix[x][y]:
                dp[nx][ny]=max(dp[nx][ny],dp[x][y]+1)
    return max([max(x) for x in dp])

exp1=[[9,9,4],
      [6,6,8],
      [2,1,1]]

exp2=[[3,4,5],
      [3,2,6],
      [2,2,1]]


print(longestIncreasingPath2(exp1))
print(longestIncreasingPath2(exp2))