您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

图解算法 递归/快速排序/散列表/广度优先搜索

图解算法 递归/快速排序/散列表/广度优先搜索

1.递归

每个递归函数都有两个条件:基线条件和递归条件

简单例子:实现sum函数

# 1.实现sum函数
def sumNumber(arr):
    if arr==[]:
        return 0 
    else:
        print(arr.pop())
        return arr.pop()+sumNumber(arr)

print(sumNumber([2,5,7,10]))

2.快速排序 O(nlogn)

分而治之(divide and conquer, D&C)是著名的递归式问题解决方法
快速排序-重要的D&C算法

# 2.快速排序 O(nlogn)
def quicksort(array):
    if len(array)<2: # 递归的基线条件:数组为空或者只包含一个元素,这时的数组是有序的
        return array
    else:
        pivot=array[0] # 选择一个数作为基准值(pivot)
        less=[i for i in array[1:] if i <= pivot] # 找出比基准值小的数组 
        # array[1:] 除去基准值以外的数组
        greater=[i for i in array[1:] if i > pivot] #找出比基准值大的数组
        return quicksort(less)+[pivot]+quicksort(greater)

print (quicksort([5,6,10,2,3]))

3.散列表

# 散列表hash table
# 作用:
# 1.查找
phone_book=dict()
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
# 2.防止重复
voted = {}
def check_voter(name):
    if voted.get(name):
        print("kick them out!")
    else:
        voted[name] = True
        print("let them vote!")
# 3.用作缓存(浏览器缓存原理)
cache = {}
def get_page(url):
    if cache.get(url):
        return cache[url] # 返回缓存的数据
    else:
        data = get_data_from_server(url)
        cache[url] = data # 先将数据保存到缓存中
        return data

4.广度优先搜索

图: 一种新的数据结构
广度优先搜索(breadth-first search BFS):一种图算法

知识点①:BFS可以回答的问题:
1.A TO B 有路径吗?
2.A TO B 最短路径?
知识点②:
队列:先进先出
栈:后进先出
知识点③:BFS运行时间
O(人数+边数)-O(V+E)

# !例:寻找芒果销售商
from collections import deque
#建立每个人之间的关系
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"] = [] 

def person_is_seller(name):#判断一个人是不是芒果销售商
    return 'mango' in name

def search(name):
    search_queue=deque() #创建一个队列
    search_queue +=graph['you'] #将你的邻居加入到搜索队列中
    searched=[] #用于保存检查过的人 不然会一直循环


    while search_queue: #如果队列不为空
        person=search_queue.popleft() #取出其中的第一个人
        #检查他是不是芒果销售商
        if person_is_seller(person):
            print('Mango seller is:'+person)
            return True
        else:
            #把朋友的朋友加入队列
            search_queue+=graph[person] 
            searched.append(person)
    print('No one find!')
    return False

search('you')

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进