1. 台阶问题/斐波那契(伪)
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。{0，1，2，3，5，8......}
- 第一种方法
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
@memo
def 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
ps.真正的斐波那契数列是{0,1,1,2,3,5,8,....}
2. 变态台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
{0,1,2,4,8,16...}
fib = lambda n: n if n < 2 else 2 * fib(n - 1)
3.冒泡排序
def bubbleSort(relist):
len_ = len(relist)
for i in range(len_):
for j in range(0,len_-i-1):
if relist[j] > relist[j+1]:
relist[j+1], relist[j] = relist[j], relist[j+1]
return relist
print bubbleSort([1,5,2,6,9,3])
4.选择排序
基本思想(参考自–选择排序)：第1趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；第2趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；以此类推，第i趟在待排序记录r[i] ~ r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
# 方法一
def selectSort(relist):
len_ = len(relist)
for i in range(len_):
min_index = i
for j in range(i+1,len_): # 这个循环会找到值比第i个索引所代表值小的索引
if relist[j] < relist[min_index]:
min_index = j
relist[i] ,relist[min_index] = relist[min_index], relist[i] # 互换两个索引位置
return relist
print selectSort([1,5,2,6,9,3])
# 方法二，更加简便，但是注意和冒泡法进行区分
def selectSort(relist):
for i in range(len(relist)):
for j in range(len(relist)-i):
if relist[i] > relist[i+j]:
relist[i],relist[i+j] = relist[i+j],relist[i]
return relist
print selectSort([1,5,2,6,9,3])
5.快速排序
该方法的基本思想是(参考自–白话经典算法系列之六 快速排序 快速搞定)：
快排的思想：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
# 快排 分片的思想+递归的思想，这是取了第一个为基准值，栈高为O(log(n)),栈长O(n),所以运行时间为栈高x栈长，也就是算法平均运算时间为O(nlog(n))
def quickSort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i < pivot]
greater = [j for j in array[1:] if j > pivot]
return quickSort(less) + [pivot] + quickSort(greater)
print quickSort([1,5,2,6,9,3])
6.插入排序
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
- 1、默认序列中的第0个元素是有序的（因为只有一个元素a[0]嘛，自然是有序的）；
- 2、从下标为1（下标0没啥好插的）的元素开始，取当前下标i位置处的元素a[i]保存到一个临时变量waitInsert里；
- 3、waitInsert与对前半部分有序序列的循环遍历比较，直到遇到第一个比waitInsert大的元素（这里默认是从小到大排序），此时的下标为j，然后将其插入到j的位置即可；
- 4、因为前面的插入，导致后面元素向后推移一个位置，没关系，把原来下标i的元素弹出即可；
- 5、重复进行第2步到第4步，直到乱序序列中的元素被全部插入到有序序列中；
- 6、经过以上5个步骤之后，整体序列必然有序，排序完成。
# 直接插入排序
def insertSort(relist):
len_ = len(relist)
for i in range(1,len_):
for j in range(i):
if relist[i] < relist[j]:
relist.insert(j,relist[i]) # 首先碰到第一个比自己大的数字，赶紧刹车，停在那，所以选择insert
relist.pop(i+1) # 因为前面的insert操作，所以后面位数+1，这个位置的数已经insert到前面去了，所以pop弹出
break
return relist
print insertSort([1,5,2,6,9,3])
更多排序问题可见：数据结构与算法-排序篇-Python描述
