- Python数据结构与算法分析（第2版） —— 第4章 递归 and 第5章 搜索和排序
- 第4章 递归
- 4.2.2 递归三原则
- 4.2.3 将整数转换成任意进制的字符串
- 4.4 递归可视化
- 4.5 复杂的递归问题
- 4.6 探索迷宫
- 4.7 动态规划
- 题解
- 第5章 搜索和排序
- 5.2.1 无序列表的顺序搜索（时间复杂度O(n)）
- 5.2.2 二分搜索
- 5.2.3 散列
- 1. 散列函数
- 2. 处理冲突
- 3.实现映射抽象数据类型
- 4.分析散列搜索算法
- 5.3 排序
- 5.3.1 冒泡排序
- 5.3.2 选择排序
- 5.3.3 插入排序
- 5.3.4 希尔排序
- 5.3.5 归并排序
- 5.3.6 快速排序
- 递归算法必须有基本情况
- 递归算法必须改变其状态并向基本情况靠近
- 递归算法必须递归地调用自己
def toStr(n , base):
convertString = "0123456789ABCDEF"
if n < base:
return convertString[n]
else:
return toStr(n // base,base) + convertString[n % base]
x = 12
print(toStr(x,2))
4.4 递归可视化
- 使用turtle模块递归地绘制螺旋线
from turtle import *
myTurtle = Turtle()
myWin = myTurtle.getscreen()
def drawSpiral(myTurtle,lineLen):
if lineLen > 0:
myTurtle.forward(lineLen)
myTurtle.right(90)
drawSpiral(myTurtle,lineLen - 5)
drawSpiral(myTurtle,100)
myWin.exitemclick()
- 绘制分形树
from turtle import *
myTurtle = Turtle()
myWin = myTurtle.getscreen()
def tree(branchLen,t):
if branchLen > 5:
myTurtle.forward(branchLen)
myTurtle.right(20)
tree(branchLen - 15,myTurtle)
myTurtle.left(40)
tree(branchLen - 10,myTurtle)
myTurtle.right(20)
myTurtle.backward(branchLen)
myTurtle.left(90)
myTurtle.up()
myTurtle.backward(300)
myTurtle.down()
myTurtle.color("green")
tree(110,myTurtle)
myWin.exitonclick()
- 绘制谢尔平斯基三角形
from turtle import *
def drawTriangle(points,color,myTurtle):
myTurtle.fillcolor(color)
myTurtle.up()
myTurtle.goto(points[0])
myTurtle.down()
myTurtle.begin_fill()
myTurtle.goto(points[1])
myTurtle.goto(points[2])
myTurtle.goto(points[0])
myTurtle.end_fill()
def getMid(p1,p2):
return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
def sierpinski(points , degree , myTurtle):
colormap = ["blue","red","green","white","yellow","violet","orange"]
drawTriangle(points,colormap[degree],myTurtle)
if degree > 0:
sierpinski([points[0],
getMid(points[0],points[1]),
getMid(points[0],points[2],)],
degree - 1,
myTurtle
)
sierpinski([points[1],
getMid(points[0], points[1]),
getMid(points[1], points[2], )],
degree - 1,
myTurtle
)
sierpinski([points[2],
getMid(points[2], points[1]),
getMid(points[0], points[2], )],
degree - 1,
myTurtle
)
myTurtle = Turtle()
myWin = myTurtle.getscreen()
myPoints = [(-500,-250),(0,500),(500,-250)]
sierpinski(myPoints,5,myTurtle)
myWin.exitonclick()
4.5 复杂的递归问题
- 汉诺塔
用Python解决汉诺塔问题
def moveDisk(fromPole, toPole):
print("Moving disk from %d to %d" % (fromPole,toPole))
def moveTower(height , fromPole , toPole , withPole):
if height >= 1:
moveTower(height - 1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height - 1,withPole,toPole,fromPole)
if __name__ == '__main__':
plate = 5
moveTower(5,1,3,2)
4.6 探索迷宫
递归方法解决
4.7 动态规划经典问题：换硬币
假设某个自动售货机制造商希望在每笔交易中给出最少的硬币。
一个顾客使用一张一美元的纸币购买了价值37美分的物品，问最少需要找给顾客多少硬币？
答案：6枚【25美分的2枚，10美分的1枚，1美分的3枚】
贪婪算法：从面值最大的硬币(25美分)开始，使用尽可能多的硬币，然后尽可能多地使用面值第二大的硬币 → 试图最大程度地解决问题。
- 使用递归解决找零问题
def recMC(coinValueList,change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList,change - i)
if numCoins < minCoins:
minCoins = numCoins
return minCoins
# 硬币种类
coins = [1,5,10,25]
# 需要凑出
target = 63
print(recMC(coins,target))
67716925次递归调用才能找到最优解
- 使用动态规划解决找零问题
def dpMakeChange(coinValueList , change , minCoins):
for cents in range(change - 1):
coinCount = cents
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
minCoins[cents] = coinCount
return minCoins[change]
- 力扣322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
题解class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
# dp[i] 代表凑出i块钱，最少需要的硬币个数
dp[0] = 0 # 凑0块，一个硬币也不要
# 最后一步的思想
for coin in coins:# 遍历所有硬币种类
for i in range(coin , amount + 1): # 从当前硬币种类开始，i代表要凑的金额数
# dp[金额数 - 当前coin]代表除去coin后，凑齐[ ]金额还需要的硬币个数，再和dp[i]求最小值
dp[i] = min(dp[i] , dp[i - coin] + 1)
if dp[amount] != float("inf"):
return dp[amount]
else:
return - 1
第5章 搜索和排序
5.2.1 无序列表的顺序搜索（时间复杂度O(n)）
def sequentialSearch(alist,item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos + 1
return found
myList = [1,7,4,5,2]
target = 4
print(sequentialSearch(myList,target))
无序列表的顺序搜索，略
5.2.2 二分搜索- 递归版本（时间复杂度为对数阶）
def binnarySearch(alist,item):
if len(alist) == 0:
return False
else:
midpoint = len(alist) // 2
if alist[midpoint] == item:
return True
else:
if item < alist[midpoint]:
return binnarySearch(alist[:midpoint],item)
else:
return binnarySearch(alist[midpoint:],item)
myList = [1,2,3,4,5]
target = 4
print(binnarySearch(myList,target))
5.2.3 散列
通过散列可以构建一个查找目标元素时间复杂度为O(1)的数据结构
散列表：一个元素集合，其中的元素以一种便于查找的方式存储，散列表中的每个位置通常被称为槽，其中可以存储一个元素。从0开始整数标记每一个槽。
散列函数将散列表中的元素与其所属位置对应起来。
对散列表中的任一元素，散列函数返回一个介于0 ~ m-1【m为元素个数】之间的整数
-
取余函数：使用余数作为散列值：即用元素 % 表的大小
槽的占用率称作载荷因子 λ = 元素个数 / 散列表大小
搜索目标函数时，仅需使用散列函数计算出槽编号，并查看对应的槽中是否有值。
有时候，散列函数会将两个元素放入同一个槽 → 冲突(碰撞)
给定一个元素集合，能将每个元素映射到不同的槽，这种散列函数称作完美散列函数。
构建完美散列函数的一个方法是增大散列表,使之能容纳每一个元素,这样就能保证每个元素都有属于自己的槽【可能空间浪费】
目标：创建这样一个散列函数:冲突数最少,计算方便，元素均匀分布于散列表中。
→ 扩展取余函数
- 折叠法
- 平方取中法
！散列函数一定要高效，以免它成为存储和搜索过程的负担。如果散列函数过于复杂，计算槽编号的工作量可能比在进行顺序搜索或二分搜索时的更大，这不是散列的初衷。
2. 处理冲突当两个元素被分到同一个槽时，必须通过一种系统化方法在散列表中安置第二个元素
-
开放定址法：尝试在散列表中寻找下一个空槽或地址→又叫线性探测
缺点：聚集现象。如果一个槽发生太多冲突，线性探测会填满其附近的槽。
-
扩展线性探测
再散列：泛指发生冲突后，寻找另一个槽的过程。
-
平方探测
不采用固定的跨步，通过再散列函数递增散列值
-
链接法：允许散列表同一个位置上存在多个元素。发生冲突，仍进行插入【链条状】
Python使用两个列表实现HashTable类
class HashTable:
def __init__(self):
#指定散列表初始大小
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self,key,data):
hashvalue = self.hashfunction(key,len(self.slots))
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data
else:
nextslot = self.rehash(hashvalue,len(self.slots))
while self.slots[nextslot] != None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if self.slots[nextslot] == None:
self.slots[nextslot]= key
self.data[nextslot] = data
else:
self.data[nextslot] = data
def get(self,key):
startslot = self.hashfunction(key,len(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key,data)
def hashfunction(self,key,size):
return key % size
def rehash(self,oldhash,size):
return (oldhash + 1) % size
4.分析散列搜索算法
5.3 排序
5.3.1 冒泡排序
冒泡排序多次遍历列表。它比较相邻的元素,将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。本质上,每个元素通过“冒泡”找到自己所属的位置。
- Python实现冒泡排序
def bubbleSort(alist):
for passnum in range(len(alist) - 1, 0 ,-1):
for i in range(passnum):
if alist[i] > alist[i + 1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
5.3.2 选择排序
选择排序在冒泡排序的基础上做了改进，每次遍历列表时只做一次交换。要实现这一点，选择排序在每次遍历时寻找最大值，并在遍历完之后将它放到正确位置上。
- Python实现选择排序
def selectionSort(alist):
for fillslot in range(len(alist - 1),0,-1):
positionOfMax = 0
for location in range(1,fillslot + 1):
if alist[location] > alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
5.3.3 插入排序
在列表较低的一端维护一个有序的子列表，并逐个将每个新元素“插入”这个子列表。图5-16展示了插入排序的过程。
- Python实现插入排序
def insertionSort(alist):
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position > 0 and alist[position -1 ] > currentvalue:
alist[position] = alist[position - 1]
position = position - 1
alist[position] = currentvalue
5.3.4 希尔排序
希尔排序也称“递减增量排序”,它对插入排序做了改进,将列表分成数个子列表，并对每一个子列表应用插入排序。如何切分列表是希尔排序的关键——并不是连续切分，而是使用增量i（有时称作步长）选取所有间隔为i的元素组成子列表。
- 使用Python实现希尔排序
def gapInsertionSort(alist, start, gap):
for i in range(start + gap,len(alist),gap):
currentvalue = alist[i]
position = i
while position >= gap and alist[position - gap] > currentvalue:
alist[position] = alist[position - gap]
position = position - gap
alist[position] = currentvalue
def shellSort(alist):
sublistcount = len(alist) // 2
while sublistcount > 0:
for startposition in range(sublistcount):
gapInsertionSort(alist,startposition,sublistcount)
print("After increments of size",sublistcount,"The list is ",alist)
sublistcount = sublistcount // 2
5.3.5 归并排序
递归算法，每次将一个列表一分为二。如果列表为空或只有一个元素，那么从定义上来说它就是有序的(基本情况)。如果列表不止一个元素，就将列表一分为二，并对两部分都递归调用归并排序。当两部分都有序后，就进行归并这一基本操作。归并是指将两个较小的有序列表归并为一个有序列表的过程。
- 用Python实现归并排序
def mergeSort(alist):
print("Splitting " , alist)
if len(alist) > 1:
mid = len(alist) // 2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i = 0
j = 0
k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k] = lefthalf[i]
i += 1
else:
alist[k] = righthalf[j]
j += 1
k += 1
while i < len(lefthalf):
alist[k] = lefthalf[i]
i += 1
k += 1
while j < len(righthalf):
alist[k] = righthalf[j]
j += 1
k += 1
print("Merging ",alist)
5.3.6 快速排序
快速排序算法首先选出一个基准值基准值的作用是帮助切分列表。在最终的有序列表中，基准值的位置通常被称作分割点，算法在分割点切分列表，以进行对快速排序的子调用。
- 用Python实现快排
def partition(alist, first, last):
pivotvalue = alist[first]
leftmark = first + 1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark - 1
if rightmark < leftmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
def quickSortHelper(alist, first, last):
if first < last:
splitpoint = partition(alist,first,last)
quickSortHelper(alist,first,splitpoint - 1)
quickSortHelper(alist,splitpoint + 1,last)
def quickSort(alist):
quickSortHelper(alist,0,len(alist) - 1)
暑期编程PK赛
得CSDN机械键盘等精美礼品！
