《算法图解》代码实现和改进
请随意观看表演
二分查找
def bin_search(list,item):
low = 0
high = len(list) - 1
while low<=high:
mid = (low+high)//2 #得到中间值
guess = list[mid]
if guess==item:
return mid
elif guess>item:
high = mid-1
else:
low = mid+1
return None
func = lambda x:x%2!=0
my_list = list(filter(func,range(0,10)))
print(my_list)
print(bin_search(my_list,2))
print(bin_search(my_list,5))
[1, 3, 5, 7, 9]
None
2
数组和链表
选择排序
def findSmall(arr):#找到最小
small = arr[0]
small_index = 0
for i in range(1,len(arr)):
if arr[i]<small:
small = arr[i]
small_index = i
return (small_index,small)
def selectionSelect(arr):#选择排序,升序
newArr = []
for i in range(len(arr)):
small_index = findSmall(arr)[0]
newArr.append(arr.pop(small_index))
return newArr
print(selectionSelect([i for i in range(10,0,-1)]))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
递归
盒子查找
迭代写法
def lookForKey(mainBox):
pile = mainBox.makePileToLook()
while len(pile):
box = pile.grabBox()
for item in box:
if item.isBox():
pile.append(item)
elif item.isKey():
print("found the key!")
递归写法
def lookForKey(box):
for item in box:
if item.isBox():
lookForKey(item)
elif item.isKey():
print('Found the key at ',item)
基线条件和递归条件
def countdown(i):
print(i)
if i-1:
countdown(i-1)
else : return
countdown(5)
5
4
3
2
1
快速排序
分而治之
def Sum(arr):
if len(arr):
return arr[0] + Sum(arr[1:])
else:
return 0
Sum([i for i in range(1,101)])
5050
找到最大值
'''
错误的写法，out of range
def getMax(arr,index=0):
if len(arr)>1:
new_index = index + 1
print(new_index,len(arr))
return arr[index] if arr[index]>getMax(arr[new_index:],new_index) else getMax(arr[new_index:],new_index)
else:
return arr[index]
'''
def getMax(arr):
if arr and len(arr)>1:
return arr[0] if arr[0] > getMax(arr[1:]) else getMax(arr[1:])
else:
return arr[0]
import random
List = [i for i in range(6)]
random.shuffle(List)
print(List)
getMax(List)
[1, 4, 5, 2, 3, 0]
5
快速排序
def quickSort(arr):
if len(arr)<2:
return arr #基线条件，为空或者只含有一个元素的数组
else:
pivot = arr[0] # 递归条件，这里可以随机选取的
small= [i for i in arr[1:] if i<=pivot] #小于基准值组成的子数组
big = [i for i in arr[1:] if i>pivot]
return quickSort(small) +[pivot] + quickSort(big)
print(quickSort([10,5,3]))
[3, 5, 10]
快速排序改进（个人代码，可能有bug）
from random import randrange
def quickSort(arr):
if len(arr)<2:
return arr
else:
flag = 0
for i in range(0,len(arr)-1):
if arr[i]>arr[i+1]:
flag = 1
break
if flag:
index = randrange(0,len(arr))
pivot = arr[index]
small = [arr[i] for i in range(0,len(arr)) if i!=index and arr[i]<=pivot]
big = [arr[i] for i in range(0,len(arr)) if i!=index and arr[i]>pivot]
return quickSort(small)+[pivot]+quickSort(big)
else:
return arr
print(quickSort([10,5,3,-5]))
[-5, 3, 5, 10]
散列表
python里面实现方式是字典
DNS实现
dns = {}
dns['google.com'] = '74.125.239.133'
dns['scribd.com'] = '23.235.47.175'
site = input('>>> ')
print(site,dns.get(site))
>>> google.com
google.com 74.125.239.133
投票
voted = {}
def check_voter(name):
if voted.get(name):
print('已经投过票')
else:
voted[name] = True
print('可以投票')
check_voter('Tom')
check_voter('Vic')
check_voter('Tom')
可以投票
可以投票
已经投过票
用户缓存
cache = {}
def get_page(url):
if cache.get(url):
return chache[url]#返回缓存数据
else:
data = get_data_from_server(url)#默认配置
cache[url] = data
return data
冲突+性能
填装因子 = 存在的/全部空间
广度优先搜索(BFS)
实现图
graph = {}
graph['you'] = ['alice','bob','claire']
graph['bob'] = ['anuj','peggy']
graph['alice'] = ['peggy']
graph['claire']=['thom','jonny']
graph['anuj']=[]
graph['peggy']=[]
graph['thom'] = []
graph['jonny'] = []
队列
from collections import deque
collections.deque
def person_is_seller(name):
return name[-1] == 'm'
def search(name):
search_queue = deque()#创建对列
global graph
search_queue += graph[name]#从谁开始搜索
searched = []#已经搜索，防止无限循环
while search_queue:#只要队列里有人
person = search_queue.popleft()#取出一人
if person not in searched:
if person_is_seller(person):
print(person+' is a mango seller')
return True
else:
search_queue+=graph[person]
searched.append(person)
return False
search('you')
thom is a mango seller
True
狄克斯特拉算法
有向无环图、加权图(权值为正)
graph = {}
graph['start'] = {}
graph['start']['a']=6
graph['start']['b'] = 2
graph['a']={}
graph['a']['fin'] = 1
graph['b']={}
graph['b']['a']=3
graph['b']['fin']=5
graph['fin'] = {}#终点没有邻居
infinity = float("inf")#+oo正无穷
costs = {}
costs['a'] =6
costs['b'] =2
costs['fin'] = infinity
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:#遍历所有节点
cost = costs[node]
global processed
if cost<lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
def get_load(parents,destination):#获得路径
t = parents.get(destination)
print(destination,'<--',end=" ")
while t:
print(t,'<--',end=" ")
t = parents.get(t)
print('None')
node = find_lowest_cost_node(costs)
while node:#当还有节点可以处理的时候
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if new_cost < costs[n]:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)
print("cost is ",costs['fin'])
get_load(parents,'fin')
cost is 6
fin <-- a <-- b <-- start <-- None
贪婪算法(不一定是最优解,非常接近)
集合操作
fruits = set(['avocado','tomato','banana'])
vegetables = set(['beets','carrots','tomato'])
print('|:并集
',fruits | vegetables)
print('&:交集
',fruits & vegetables)
print('-:差集
',fruits - vegetables)
|:并集
{'tomato', 'avocado', 'beets', 'carrots', 'banana'}
&:交集
{'tomato'}
-:差集
{'avocado', 'banana'}
模糊算法--集合覆盖问题
states_needed = set(['mt','wa','or','id','nv','ut','ca','az'])
stations = {}
stations['kone'] = set(['id','nv','ut'])
stations['ktwo'] = set(['wa','id','mt'])
stations['kthree'] = set(['or','nv','ca'])
stations['kfour'] = set(['nv','ut'])
stations['kfive'] = set(['ca','az'])
final_stations = set()#最终电台
while states_needed:
best_station = None#存放覆盖区域最多的电台
states_covered = set()
for station,states_for_station in stations.items():
covered = states_needed & states_for_station
if len(covered)>len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
del stations[best_station]#用过的删除
print(final_stations)
{'kfive', 'ktwo', 'kone', 'kthree'}