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

请随意观看表演

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

二分查找

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)

快速排序

分而治之

def Sum(arr):
    if len(arr):
        return arr[0] + Sum(arr[1:])
    else:
        return 0
Sum([i for i in range(1,101)])

找到最大值

‘‘‘
错误的写法，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 = http://www.mamicode.com/get_data_from_server(url)#默认配置>


冲突+性能
填装因子 = 存在的/全部空间
 
 
广度优先搜索(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‘}
《算法图解》代码实现和改进



make 基线 _for tables 缓存 


 声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。









 看完仍有疑问？有类似问题直接问程序猿









  
    
      
        投诉/举报
        
      
      
        




       
          
            
            
            
            
          
        
       
           您的姓名
          
            
            
            
          
          
        
        
           反馈内容






 相关代码解决方案


 《算法图解》 KMP算法的理解和代码实现 改进的二值图像像素标记算法及程序实现（含代码） 《算法图解》3 《算法图解》2 作业-----菱形改进算法 KMP及其改进算法 冒泡排序改进算法 KMP算法代码实现 算法：Astar寻路算法改进 常见排序算法思路和简单代码实现 ISAP算法对 Dinic算法的改进 反思和改进 KMP算法的代码实现 图解zookeeper FastLeader选举算法 Kd-Tree算法原理和开源实现代码 改进的起泡排序算法--java Submission Details [leetcode] 算法的改进 kmp算法c++代码实现 算法-java代码实现堆排序 算法-java代码实现希尔排序 算法-java代码实现计数排序 一行代码改进NMS 我对TCP CDG拥塞控制算法的改进和优化 我对TCP CDG拥塞控制算法的改进和优化 多种排序算法的思路和简单代码的实现（一） 图解zookeeper FastLeader选举算法【转】 OpenCv关于灰度积分图的SSE代码学习和改进。 排序系列 之 简单选择排序及其改进算法 —— Java实现


当日更新
 web html 在线调试工具
 常见浏览器兼容问题及解决技
 UML类图及PHP的几个函数
 SQL结构化查询语言分类介绍
 Git详解之三 Git分支
 python杨辉三角实现练习
 Eclipse卡顿，内存猛增解决方
 python enumerate用法总结
 oracle dataguard 角色切换
 Allow Zero Length 允许空字