编程题

fib = lambda n: n if n <= 2 else fib(n - 1) + fib(n - 2)

def memo(func):    cache = {}    def wrap(*args):        if args not in cache:            cache[args] = func(*args)        return cache[args]    return wrap@memodef fib(i):    if i < 2:        return 1    return fib(i-1) + fib(i-2)

def fib(n):    a, b = 0, 1    for _ in xrange(n):        a, b = b, a + b    return b

fib = lambda n: n if n < 2 else 2 * fib(n - 1)

f = lambda n: 1 if n < 2 else f(n - 1) + f(n - 2)

def get_value(l, r, c):    return l[r][c]def find(l, x):    m = len(l) - 1    n = len(l[0]) - 1    r = 0    c = n    while c >= 0 and r <= m:        value = get_value(l, r, c)        if value == x:            return True        elif value > x:            c = c - 1        elif value < x:            r = r + 1    return False

list(set(l))

l1 = [‘b‘,‘c‘,‘d‘,‘b‘,‘c‘,‘a‘,‘a‘]l2 = {}.fromkeys(l1).keys()print l2

l1 = [‘b‘,‘c‘,‘d‘,‘b‘,‘c‘,‘a‘,‘a‘]l2 = list(set(l1))l2.sort(key=l1.index)print l2

l1 = [‘b‘,‘c‘,‘d‘,‘b‘,‘c‘,‘a‘,‘a‘]l2 = [][l2.append(i) for i in l1 if not i in l2]

class ListNode:    def __init__(self, x):        self.val = x        self.next = Noneclass Solution:    # @param a ListNode    # @return a ListNode    def swapPairs(self, head):        if head != None and head.next != None:            next = head.next            head.next = self.swapPairs(next.next)            next.next = head            return next        return head

dict = {‘name‘:‘earth‘, ‘port‘:‘80‘}

items=[(‘name‘,‘earth‘),(‘port‘,‘80‘)]dict2=dict(items)dict1=dict(([‘name‘,‘earth‘],[‘port‘,‘80‘]))

dict1={}.fromkeys((‘x‘,‘y‘),-1)dict={‘x‘:-1,‘y‘:-1}dict2={}.fromkeys((‘x‘,‘y‘))dict2={‘x‘:None, ‘y‘:None}

def _recursion_merge_sort2(l1, l2, tmp):    if len(l1) == 0 or len(l2) == 0:        tmp.extend(l1)        tmp.extend(l2)        return tmp    else:        if l1[0] < l2[0]:            tmp.append(l1[0])            del l1[0]        else:            tmp.append(l2[0])            del l2[0]        return _recursion_merge_sort2(l1, l2, tmp)def recursion_merge_sort2(l1, l2):    return _recursion_merge_sort2(l1, l2, [])

class ListNode:    def __init__(self, x):        self.val = x        self.next = Nonedef node(l1, l2):    length1, lenth2 = 0, 0    # 求两个链表长度    while l1.next:        l1 = l1.next        length1 += 1    while l2.next:        l2 = l2.next        length2 += 1    # 长的链表先走    if length1 > lenth2:        for _ in range(length1 - length2):            l1 = l1.next    else:        for _ in range(length2 - length1):            l2 = l2.next    while l1 and l2:        if l1.next == l2.next:            return l1.next        else:            l1 = l1.next            l2 = l2.next

def binarySearch(l, t):    low, high = 0, len(l) - 1    while low < high:        print low, high        mid = (low + high) / 2        if l[mid] > t:            high = mid        elif l[mid] < t:            low = mid + 1        else:            return mid    return low if l[low] == t else Falseif __name__ == ‘__main__‘:    l = [1, 4, 12, 45, 66, 99, 120, 444]    print binarySearch(l, 12)    print binarySearch(l, 1)    print binarySearch(l, 13)    print binarySearch(l, 444)

def qsort(seq):    if seq==[]:        return []    else:        pivot=seq[0]        lesser=qsort([x for x in seq[1:] if x<pivot])        greater=qsort([x for x in seq[1:] if x>=pivot])        return lesser+[pivot]+greaterif __name__==‘__main__‘:    seq=[5,6,78,9,0,-1,2,3,-65,12]    print(qsort(seq))

def  coinChange(values, money, coinsUsed):    #values    T[1:n]数组    #valuesCounts   钱币对应的种类数    #money  找出来的总钱数    #coinsUsed   对应于目前钱币总数i所使用的硬币数目    for cents in range(1, money+1):        minCoins = cents     #从第一个开始到money的所有情况初始        for value in values:            if value <= cents:                temp = coinsUsed[cents - value] + 1                if temp < minCoins:                    minCoins = temp        coinsUsed[cents] = minCoins        print(‘面值为：{0} 的最小硬币数目为：{1} ‘.format(cents, coinsUsed[cents]) )if __name__ == ‘__main__‘:    values = [ 25, 21, 10, 5, 1]    money = 63    coinsUsed = {i:0 for i in range(money+1)}    coinChange(values, money, coinsUsed)

## 14 二叉树节点class Node(object):    def __init__(self, data, left=None, right=None):        self.data = data        self.left = left        self.right = righttree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))## 15 层次遍历def lookup(root):    stack = [root]    while stack:        current = stack.pop(0)        print current.data        if current.left:            stack.append(current.left)        if current.right:            stack.append(current.right)## 16 深度遍历def deep(root):    if not root:        return    print root.data    deep(root.left)    deep(root.right)if __name__ == ‘__main__‘:    lookup(tree)    deep(tree)

def maxDepth(root):        if not root:            return 0        return max(maxDepth(root.left), maxDepth(root.right)) + 1

def isSameTree(p, q):    if p == None and q == None:        return True    elif p and q :        return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)    else :        return False

def rebuild(pre, center):    if not pre:        return    cur = Node(pre[0])    index = center.index(pre[0])    cur.left = rebuild(pre[1:index + 1], center[:index])    cur.right = rebuild(pre[index + 1:], center[index + 1:])    return curdef deep(root):    if not root:        return    deep(root.left)    deep(root.right)    print root.data

class Node(object):    def __init__(self, data=None, next=None):        self.data = data        self.next = nextlink = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))def rev(link):    pre = link    cur = link.next    pre.next = None    while cur:        tmp = cur.next        cur.next = pre        pre = cur        cur = tmp    return preroot = rev(link)while root:    print root.data    root = root.next

class Anagram:    """    @:param s1: The first string    @:param s2: The second string    @:return true or false    """    def Solution1(s1,s2):        alist = list(s2)        pos1 = 0        stillOK = True        while pos1 < len(s1) and stillOK:            pos2 = 0            found = False            while pos2 < len(alist) and not found:                if s1[pos1] == alist[pos2]:                    found = True                else:                    pos2 = pos2 + 1            if found:                alist[pos2] = None            else:                stillOK = False            pos1 = pos1 + 1        return stillOK    print(Solution1(‘abcd‘,‘dcba‘))    def Solution2(s1,s2):        alist1 = list(s1)        alist2 = list(s2)        alist1.sort()        alist2.sort()        pos = 0        matches = True        while pos < len(s1) and matches:            if alist1[pos] == alist2[pos]:                pos = pos + 1            else:                matches = False        return matches    print(Solution2(‘abcde‘,‘edcbg‘))    def Solution3(s1,s2):        c1 = [0]*26        c2 = [0]*26        for i in range(len(s1)):            pos = ord(s1[i])-ord(‘a‘)            c1[pos] = c1[pos] + 1        for i in range(len(s2)):            pos = ord(s2[i])-ord(‘a‘)            c2[pos] = c2[pos] + 1        j = 0        stillOK = True        while j<26 and stillOK:            if c1[j] == c2[j]:                j = j + 1            else:                stillOK = False        return stillOK    print(Solution3(‘apple‘,‘pleap‘))