《啊哈！算法》学习 - Python笔记

最常用的排序 -- 快速排序

def quickSort(array):
    smaller = []
    greater = []
    if len(array) <= 1:
        return array
    base = array.pop()
    for x in array:
        if x < base:
            smaller.append(x)
        else:
            greater.append(x)
    return quickSort(smaller) + [base] + quickSort(greater)

arrayList = [9, 12, 25, 5, 21, 3, 7, 11, 85]
quickSort(arrayList)

[3, 5, 7, 9, 11, 12, 21, 25, 85]

解密QQ号 -- 队列

def extractQQNumber(qq, result=[]):
    """
    Python技巧：利用Python默认参数再次调用不重新计算的特性获得返回值
    （参考《编写高质量代码 改善Python程序的91个建议》建议32：警惕默认参数潜在的问题）
    """
    num = qq.pop(0)
    result.append(num)
    if len(qq) > 0:
        num = qq.pop(0)
        qq.append(num)
        extractQQNumber(qq)
    return result

qq = '631758924'
extractQQNumber([i for i in qq])

['6', '1', '5', '9', '4', '7', '2', '8', '3']

坑爹的奥数：口口口+口口口=口口口

代码参考网上的，原谅我自己不太理解。《啊哈！算法》中深度优先搜索基本模型已经体现了。

perm_lst = []
def permutation(lst):
    if lst == []:                               # 判断边界
        if perm_lst[0]*100 + perm_lst[1]*10 + perm_lst[2] + perm_lst[3]*100 + perm_lst[4]*10 + perm_lst[5] == perm_lst[6]*100 + perm_lst[7]*10 + perm_lst[8]:
            print(perm_lst)
    else:
        for elem in lst:                 # 尝试每一种可能
            perm_lst.append(elem)
            rest_lst = lst[:]
            rest_lst.remove(elem)
            permutation(rest_lst)        # 继续下一步
            perm_lst.pop()               # 回收

## 测试         
permutation([i for i in range(1, 10)])

## 输出结果：
[1, 2, 4, 6, 5, 9, 7, 8, 3]
[1, 2, 5, 7, 3, 9, 8, 6, 4]
[1, 2, 7, 3, 5, 9, 4, 8, 6]
···

[7, 8, 3, 1, 6, 2, 9, 4, 5]
[7, 8, 4, 1, 5, 2, 9, 3, 6]