1 台阶问题/斐波那契

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

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

第二种记忆方法

  1. def memo(func):
  2.     cache = {}
  3.     def wrap(*args):
  4.         if args not in cache:
  5.             cache[args] = func(*args)
  6.         return cache[args]
  7.     return wrap
  10. @memo
  11. def fib(i):
  12.     if i < 2:
  13.         return 1
  14.     return fib(i-1) + fib(i-2)

第三种方法

  1. def fib(n):
  2.     a, b = 0, 1
  3.     for _ in xrange(n):
  4.         a, b = b, a + b
  5.     return b

2 变态台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

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

3 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。

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

4 杨氏矩阵查找

在一个m行n列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

使用Step-wise线性搜索。

  1. def get_value(l, r, c):
  2.     return l[r][c]
  4. def find(l, x):
  5.     m = len(l) - 1
  6.     n = len(l[0]) - 1
  7.     r = 0
  8.     c = n
  9.     while c >= 0 and r <= m:
  10.         value = get_value(l, r, c)
  11.         if value == x:
  12.             return True
  13.         elif value > x:
  14.             c = c - 1
  15.         elif value < x:
  16.             r = r + 1
  17.     return False

5 去除列表中的重复元素

用集合

  1. list(set(l))

用字典

  1. l1 = ['b','c','d','b','c','a','a']
  2. l2 = {}.fromkeys(l1).keys()
  3. print l2

用字典并保持顺序

  1. l1 = ['b','c','d','b','c','a','a']
  2. l2 = list(set(l1))
  3. l2.sort(key=l1.index)
  4. print l2

列表推导式

  1. l1 = ['b','c','d','b','c','a','a']
  2. l2 = []
  3. [l2.append(i) for i in l1 if not i in l2]

sorted排序并且用列表推导式.

l = [‘b’,’c’,’d’,’b’,’c’,’a’,’a’]
[single.append(i) for i in sorted(l) if i not in single]
print single

6 链表成对调换

1->2->3->4转换成2->1->4->3.

  1. class ListNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.next = None
  6. class Solution:
  7.     # @param a ListNode
  8.     # @return a ListNode
  9.     def swapPairs(self, head):
  10.         if head != None and head.next != None:
  11.             next = head.next
  12.             head.next = self.swapPairs(next.next)
  13.             next.next = head
  14.             return next
  15.         return head

7 创建字典的方法

1 直接创建

  1. dict = {'name':'earth', 'port':'80'}

2 工厂方法

  1. items=[('name','earth'),('port','80')]
  2. dict2=dict(items)
  3. dict1=dict((['name','earth'],['port','80']))

3 fromkeys()方法

  1. dict1={}.fromkeys(('x','y'),-1)
  2. dict={'x':-1,'y':-1}
  3. dict2={}.fromkeys(('x','y'))
  4. dict2={'x':None, 'y':None}

8 合并两个有序列表

知乎远程面试要求编程

尾递归

  1. def _recursion_merge_sort2(l1, l2, tmp):
  2.     if len(l1) == 0 or len(l2) == 0:
  3.         tmp.extend(l1)
  4.         tmp.extend(l2)
  5.         return tmp
  6.     else:
  7.         if l1[0] < l2[0]:
  8.             tmp.append(l1[0])
  9.             del l1[0]
  10.         else:
  11.             tmp.append(l2[0])
  12.             del l2[0]
  13.         return _recursion_merge_sort2(l1, l2, tmp)
  15. def recursion_merge_sort2(l1, l2):
  16.     return _recursion_merge_sort2(l1, l2, [])

循环算法

思路：

定义一个新的空列表

比较两个列表的首个元素

小的就插入到新列表里

把已经插入新列表的元素从旧列表删除

直到两个旧列表有一个为空

再把旧列表加到新列表后面

  1. def loop_merge_sort(l1, l2):
  2.     tmp = []
  3.     while len(l1) > 0 and len(l2) > 0:
  4.         if l1[0] < l2[0]:
  5.             tmp.append(l1[0])
  6.             del l1[0]
  7.         else:
  8.             tmp.append(l2[0])
  9.             del l2[0]
  10.     tmp.extend(l1)
  11.     tmp.extend(l2)
  12.     return tmp

pop弹出

  1. a = [1,2,3,7]
  2. b = [3,4,5]
  4. def merge_sortedlist(a,b):
  5.     c = []
  6.     while a and b:
  7.         if a[0] >= b[0]:
  8.             c.append(b.pop(0))
  9.         else:
  10.             c.append(a.pop(0))
  11.     while a:
  12.         c.append(a.pop(0))
  13.     while b:
  14.         c.append(b.pop(0))
  15.     return c
  16. print merge_sortedlist(a,b)

9 交叉链表求交点

其实思想可以按照从尾开始比较两个链表，如果相交，则从尾开始必然一致，只要从尾开始比较，直至不一致的地方即为交叉点，如图所示

编程题 - 图1

  1. # 使用a,b两个list来模拟链表，可以看出交叉点是 7这个节点
  2. a = [1,2,3,7,9,1,5]
  3. b = [4,5,7,9,1,5]
  5. for i in range(1,min(len(a),len(b))):
  6.     if i==1 and (a[-1] != b[-1]):
  7.         print "No"
  8.         break
  9.     else:
  10.         if a[-i] != b[-i]:
  11.             print "交叉节点：",a[-i+1]
  12.             break
  13.         else:
  14.             pass

另外一种比较正规的方法，构造链表类

  1. class ListNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.next = None
  5. def node(l1, l2):
  6.     length1, lenth2 = 0, 0
  7.     # 求两个链表长度
  8.     while l1.next:
  9.         l1 = l1.next
  10.         length1 += 1
  11.     while l2.next:
  12.         l2 = l2.next
  13.         length2 += 1
  14.     # 长的链表先走
  15.     if length1 > lenth2:
  16.         for _ in range(length1 - length2):
  17.             l1 = l1.next
  18.     else:
  19.         for _ in range(length2 - length1):
  20.             l2 = l2.next
  21.     while l1 and l2:
  22.         if l1.next == l2.next:
  23.             return l1.next
  24.         else:
  25.             l1 = l1.next
  26.             l2 = l2.next

修改了一下:

  1. #coding:utf-8
  2. class ListNode:
  3.     def __init__(self, x):
  4.         self.val = x
  5.         self.next = None
  7. def node(l1, l2):
  8.     length1, length2 = 0, 0
  9.     # 求两个链表长度
  10.     while l1.next:
  11.         l1 = l1.next#尾节点
  12.         length1 += 1
  13.     while l2.next:
  14.         l2 = l2.next#尾节点
  15.         length2 += 1
  17.     #如果相交
  18.     if l1.next == l2.next:
  19.         # 长的链表先走
  20.         if length1 > length2:
  21.             for _ in range(length1 - length2):
  22.                 l1 = l1.next
  23.             return l1#返回交点
  24.         else:
  25.             for _ in range(length2 - length1):
  26.                 l2 = l2.next
  27.             return l2#返回交点
  28.     # 如果不相交
  29.     else:
  30.         return

思路: http://humaoli.blog.163.com/blog/static/13346651820141125102125995/

10 二分查找

  2. #coding:utf-8
  3. def binary_search(list,item):
  4.     low = 0
  5.     high = len(list)-1
  6.     while low<=high:
  7.         mid = (low+high)/2
  8.         guess = list[mid]
  9.         if guess>item:
  10.             high = mid-1
  11.         elif guess<item:
  12.             low = mid+1
  13.         else:
  14.             return mid
  15.     return None
  16. mylist = [1,3,5,7,9]
  17. print binary_search(mylist,3)

参考: http://blog.csdn.net/u013205877/article/details/76411718

11 快排

  1. #coding:utf-8
  2. def quicksort(list):
  3.     if len(list)<2:
  4.         return list
  5.     else:
  6.         midpivot = list[0]
  7.         lessbeforemidpivot = [i for i in list[1:] if i<=midpivot]
  8.         biggerafterpivot = [i for i in list[1:] if i > midpivot]
  9.         finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot)
  10.         return finallylist
  12. print quicksort([2,4,6,7,1,2,5])

更多排序问题可见：数据结构与算法-排序篇-Python描述

12 找零问题

  2. #coding:utf-8
  3. #values是硬币的面值values = [ 25, 21, 10, 5, 1]
  4. #valuesCounts   钱币对应的种类数
  5. #money  找出来的总钱数
  6. #coinsUsed   对应于目前钱币总数i所使用的硬币数目
  8. def coinChange(values,valuesCounts,money,coinsUsed):
  9.     #遍历出从1到money所有的钱数可能
  10.     for cents in range(1,money+1):
  11.         minCoins = cents
  12.         #把所有的硬币面值遍历出来和钱数做对比
  13.         for kind in range(0,valuesCounts):
  14.             if (values[kind] <= cents):
  15.                 temp = coinsUsed[cents - values[kind]] +1
  16.                 if (temp < minCoins):
  17.                     minCoins = temp
  18.         coinsUsed[cents] = minCoins
  19.         print ('面值:{0}的最少硬币使用数为:{1}'.format(cents, coinsUsed[cents]))

思路: http://blog.csdn.net/wdxin1322/article/details/9501163

方法: http://www.cnblogs.com/ChenxofHit/archive/2011/03/18/1988431.html

13 广度遍历和深度遍历二叉树

给定一个数组，构建二叉树，并且按层次打印这个二叉树

14 二叉树节点

  2. class Node(object):
  3.     def __init__(self, data, left=None, right=None):
  4.         self.data = data
  5.         self.left = left
  6.         self.right = right
  8. tree = Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))

15 层次遍历

  2. def lookup(root):
  3.     stack = [root]
  4.     while stack:
  5.         current = stack.pop(0)
  6.         print current.data
  7.         if current.left:
  8.             stack.append(current.left)
  9.         if current.right:
  10.             stack.append(current.right)

16 深度遍历

  2. def deep(root):
  3.     if not root:
  4.         return
  5.     print root.data
  6.     deep(root.left)
  7.     deep(root.right)
  9. if __name__ == '__main__':
  10.     lookup(tree)
  11.     deep(tree)

17 前中后序遍历

深度遍历改变顺序就OK了

  2. #coding:utf-8
  3. #二叉树的遍历
  4. #简单的二叉树节点类
  5. class Node(object):
  6.     def __init__(self,value,left,right):
  7.         self.value = value
  8.         self.left = left
  9.         self.right = right
  11. #中序遍历:遍历左子树,访问当前节点,遍历右子树
  13. def mid_travelsal(root):
  14.     if root.left is None:
  15.         mid_travelsal(root.left)
  16.     #访问当前节点
  17.     print(root.value)
  18.     if root.right is not None:
  19.         mid_travelsal(root.right)
  21. #前序遍历:访问当前节点,遍历左子树,遍历右子树
  23. def pre_travelsal(root):
  24.     print (root.value)
  25.     if root.left is not None:
  26.         pre_travelsal(root.left)
  27.     if root.right is not None:
  28.         pre_travelsal(root.right)
  30. #后续遍历:遍历左子树,遍历右子树,访问当前节点
  32. def post_trvelsal(root):
  33.     if root.left is not None:
  34.         post_trvelsal(root.left)
  35.     if root.right is not None:
  36.         post_trvelsal(root.right)
  37.     print (root.value)

18 求最大树深

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

19 求两棵树是否相同

  1. def isSameTree(p, q):
  2.     if p == None and q == None:
  3.         return True
  4.     elif p and q :
  5.         return p.val == q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)
  6.     else :
  7.         return False

20 前序中序求后序

推荐: http://blog.csdn.net/hinyunsin/article/details/6315502

  1. def rebuild(pre, center):
  2.     if not pre:
  3.         return
  4.     cur = Node(pre[0])
  5.     index = center.index(pre[0])
  6.     cur.left = rebuild(pre[1:index + 1], center[:index])
  7.     cur.right = rebuild(pre[index + 1:], center[index + 1:])
  8.     return cur
  10. def deep(root):
  11.     if not root:
  12.         return
  13.     deep(root.left)
  14.     deep(root.right)
  15.     print root.data

21 单链表逆置

  1. class Node(object):
  2.     def __init__(self, data=None, next=None):
  3.         self.data = data
  4.         self.next = next
  6. link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
  8. def rev(link):
  9.     pre = link
  10.     cur = link.next
  11.     pre.next = None
  12.     while cur:
  13.         tmp = cur.next
  14.         cur.next = pre
  15.         pre = cur
  16.         cur = tmp
  17.     return pre
  19. root = rev(link)
  20. while root:
  21.     print root.data
  22.     root = root.next

思路: http://blog.csdn.net/feliciafay/article/details/6841115

方法: http://www.xuebuyuan.com/2066385.html?mobile=1

22 两个字符串是否是变位词

  1. class Anagram:
  2.     """
  3.     @:param s1: The first string
  4.     @:param s2: The second string
  5.     @:return true or false
  6.     """
  7.     def Solution1(s1,s2):
  8.         alist = list(s2)
  10.         pos1 = 0
  11.         stillOK = True
  13.         while pos1 < len(s1) and stillOK:
  14.             pos2 = 0
  15.             found = False
  16.             while pos2 < len(alist) and not found:
  17.                 if s1[pos1] == alist[pos2]:
  18.                     found = True
  19.                 else:
  20.                     pos2 = pos2 + 1
  22.             if found:
  23.                 alist[pos2] = None
  24.             else:
  25.                 stillOK = False
  27.             pos1 = pos1 + 1
  29.         return stillOK
  31.     print(Solution1('abcd','dcba'))
  33.     def Solution2(s1,s2):
  34.         alist1 = list(s1)
  35.         alist2 = list(s2)
  37.         alist1.sort()
  38.         alist2.sort()
  41.         pos = 0
  42.         matches = True
  44.         while pos < len(s1) and matches:
  45.             if alist1[pos] == alist2[pos]:
  46.                 pos = pos + 1
  47.             else:
  48.                 matches = False
  50.         return matches
  52.     print(Solution2('abcde','edcbg'))
  54.     def Solution3(s1,s2):
  55.         c1 = [0]*26
  56.         c2 = [0]*26
  58.         for i in range(len(s1)):
  59.             pos = ord(s1[i])-ord('a')
  60.             c1[pos] = c1[pos] + 1
  62.         for i in range(len(s2)):
  63.             pos = ord(s2[i])-ord('a')
  64.             c2[pos] = c2[pos] + 1
  66.         j = 0
  67.         stillOK = True
  68.         while j<26 and stillOK:
  69.             if c1[j] == c2[j]:
  70.                 j = j + 1
  71.             else:
  72.                 stillOK = False
  74.         return stillOK
  76.     print(Solution3('apple','pleap'))

23 动态规划问题

可参考：动态规划(DP)的整理-Python描述