《算法图解》代码实现和改进

xiaoxiao2021-02-28  12

《算法图解》代码实现和改进

请随意观看表演

二分查找数组和链表递归递归条件和基线条件快速排序散列表广度优先搜索狄克斯特拉算法贪婪算法

二分查找

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 type(search_queue) 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 processed = []#已经处理过的点 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('|:并集\n\t',fruits | vegetables) print('&:交集\n\t',fruits & vegetables) print('-:差集\n\t',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'}
转载请注明原文地址: https://www.6miu.com/read-250100.html

最新回复(0)