面试算法（1）

# 字符串反转'12345678' -> '67812345'
def reverseStr(_str,_from):
    _str = list(_str)
    _str[_from:]=_str[:_from-1:-1]
    _str[:_from] = _str[_from-1::-1]
    _str = _str[::-1]
    return ''.join(_str)
print reverseStr('12345678',5)

# 大数加法
def addBig(a,b):
    c,i,j = 0, len(a)-1,len(b)-1
    arr = ''
    while i>=0 or j>=0 or c!=0:
        _sum =0
        _sum += int(a[i]) if (i>=0) else 0
        _sum += int(b[j]) if (j>=0) else 0
        i,j = i-1,j-1
        arr+=str((_sum+c)%10)
        c=(_sum+c)/10
    return arr[::-1]
print addBig('99','999')

# 大数乘法
def multiply(a,b):
    res= [0]*(len(a)+len(b))
    for i,ei in enumerate(reversed(a)):
        for j,ej in enumerate(reversed(b)):
            res[i+j]+=int(ei)*int(ej)
            res[i+j+1] += res[i+j]/10
            res[i+j]%= 10
    while len(res)>1 and res[-1] ==0:
        res.pop()
    return ''.join(map(str,res[::-1]))

print multiply('123','6542')

class linkNode(object) :
    def __init__(self,_v=0):
        self._v = _v
        self._next=None

# 模拟链表部分翻转
def partReverse(listNode,_from,_to):
    cur,root = linkNode(0),listNode
    for _ in xrange(_from):
        head = listNode
        listNode = listNode._next
    cur = listNode
    listNode = listNode._next
    for _ in xrange(_to-_from+1):
        cur._next = listNode._next
        listNode._next = head._next
        head._next = listNode
        listNode._next = head._next._next
        listNode = cur._next
    return root

# 拓扑排序
import numpy as np
def topo(mat):
    res,i = [],0
    while i < (mat.shape[0]):
        if sum(mat[:,i])==0 and (i not in res):
            res.append(i)
            mat[i]=0
            i=0
        i+=1
    return res

mapMat =np.array([
    [0,1,0,1,0],
    [0,0,1,0,0],
    [0,0,0,0,0],
    [0,0,1,0,1],
    [0,0,1,0,0]
])

print(topo(mapMat))

# 最长括号匹配
def longestParentheses(s):
    stack,ans=[],0
    for i,v in enumerate(')'+s):
        if v==')' and stack and stack[-1][1]=='(':
            stack.pop()
            ans = max(ans,i-stack[-1][0])
        else:
            stack.append((i,v))
    return ans

print longestParentheses("(())()()(")

# 最短路径
G = {1:{1:0,    2:1,    3:12},
     2:{2:0,    3:9,    4:3},
     3:{3:0,    5:5},
     4:{3:4,    4:0,    5:13,   6:15},
     5:{5:0,    6:4},
     6:{6:0}}
def dijkstra(G,s):
    book,minv,INF= set(),s,9999
    dis = dict((k,INF) for k in G.keys())
    dis[s] = 0
    while len(book)<len(G):
        book.add(minv)
        for w in G[minv]:
            if dis[minv]+G[minv][w]<dis[w]:
                dis[w] =  dis[minv]+G[minv][w]
        _new = INF
        for v in dis.keys():
            if v in book:
                continue
            if dis[v]<_new:
                _new = dis[v]
                minv = v
    print dis

# dijkstra(G,1)

# 快排
def quickSort(arr):
    if len(arr)<=1:return arr
    low,pi,high = partition(arr)
    return quickSort(low)+[pi]+quickSort(high)

# 分区
def partition(arr):
    pi , arr = arr[0],arr[1:]
    low = [x for x in arr if x<=pi]
    high = [x for x in arr if x>pi]
    return low,pi,high

# MergeSort
def mergeSort(arr):
    mid = len(arr)/2
    left ,right = arr[:mid],arr[mid:]
    if len(left)>1:
        left = mergeSort(left)
    if len(right)>1:
        right = mergeSort(right)
    res = []
    while left and right:
        if left[0]>=right[0]:
            res.append(left.pop())
        else:
            res.append(right.pop())
    res.reverse()
    return (left or right)+res
arr = [4,1,2,7,6]
# print mergeSort(arr)

# 生成合法括号
def generate(l,r,s,result):
    if l==0 and r==0:
        return result.append(s)
    if l>0:
        generate(l-1,r,s+'(',result)
    if r>l:
        generate(l,r-1,s+')',result)
result = []
generate(3,3,'',result)
print result