《图解算法》学习笔记

程序员文章站 2022-05-05 17:37:32

...

第1章
二分查找法
需要数组有序，且需要判断零点方向

def Bin_Sear(arr,low,high,val):
    mid=int((low+high)/2)
    if arr[mid]==val:
        return mid
    elif (arr[mid]-val)*(arr[low]-val)<0:        
        return Bin_Sear(arr,low,mid,val)
    else:
        return Bin_Sear(arr,mid+1,high,val)

第2章插入排序
从第二个开始取值，将值与前面一个已经排好的进行对比，若比前面的大，则在后面插入

def exchange(arr,i,j):
    if i!=j: #当相等时意味着不用交换
        val=arr[i]
        for k in range(i,j):
            arr[k]=arr[k+1]
        arr[j]=val
    return arr

def insert_sort(arr):
    for i in range(1,len(arr)):
        val=arr[i]
        for j in range(i):
            if val>=arr[i-1-j] and j!=0:  #当待排序值比前面某个数大时，在其背后插入，但只有两个数进行排序时，若后者比前者小，则不满足该条件，所以需要专门为其写一个出口
                arr=exchange(arr,i-j,i)
                break
            elif val<arr[0] and i==1:
                arr=exchange(arr,0,1)
    return arr

第4章快速排序
分而治之，将数据二分成小问题，交给递归解决
随机取数组中某数作为基准，其余值根据大小分在其左右，平均时间O(n*logn)，最差时间O(n2)
注意，要将int类型加[]括号，才能与其余数组合并
不稳定排序：指对原有数组中相同大小的值排序，前后顺序可能会发生变化

def qsort(arr):
    if len(arr)<2:
        return arr
    else:
        val=arr[0]
        smaller=[i for i in arr[1:] if i<=val]
        bigger=[i for i in arr[1:] if i>val]
        return qsort(smaller)+[val]+qsort(bigger)

第5章散列表==哈希表
用字符串来代替数组的数字索引，在py中是字典类型

graph={}
graph=dict()
graph['A']=[val1,val2,...]
graph['B']=[]

第6章广度优先搜索
设计有向无环图，然后将起点的邻居添加到队列，并将按队列一个个查找，在邻居中没找到的话，就将邻居的邻居添加到队列尾，以此保证每次查找都是从离起点最近的地方开始找起

from queue import Queue
G={}
G[1]=[2,3]
G[2]=[1,3,4]
G[3]=[1,2,4]
G[4]=[2,3]

processed=[]
que=Queue()

node=1
que.put(node)
processed.append(node)#要点1，处理表
while not que.empty():
    node=que.get()
    print('当前遍历顶点为：'+str(node))
    for i in G[node]:
        if not i in processed:
            processed.append(i)#要点2：处理表要在确认对象未处理后，马上将对象扔到已处理，因为放到队列里意味着一定会被处理
            que.put(i)
#广度用队列保存，深度用递归

第7章解决正权重的有/无向图——基于贪婪算法的狄克斯特拉算法
需要初始化三个图和一个列表：
图1：主图，用于确定邻居；
图2：到所有节点的花费时间，初开始节点设为0，其余都初始为无穷大；
图3：用于记录某节点的父节点；
列表1：用于记录已经处理过的节点。
思想是，从图2中选择未处理过的、数值最小的节点，如B，因为去其他邻居的路径比去B更远，就不可能有比直接去B的更短路径。路程都是正的，没有负权重，所以可以用狄克斯特拉实现。

#G:初始图
#dis：起点距离图
#fat：父节点图
def graph(line):  
    G={}
    start=1
    end=line[0]
    for i in range(line[1]):
        line = input()
        line = line.split(' ')
        line = list(map(int, line))
        for i in range(2):   #关键点1，对每条路线，要互相保存邻居
            if line[i] in G.keys():
                G[line[i]].append([line[1-i],line[2]])
            else:
                G[line[i]]=[]  #不存在时，要初始化
                G[line[i]].append([line[1-i], line[2]])
    return G,start,end

def dis(G):
    dis={}
    for i in G:
        dis[i]=float('inf') #距离初始化为无穷大
    return dis

def fat(dis):
    fat={}
    for i in dis:
        fat[i]=[]
    return fat

def min_node(dis,processed):#可能会有多个最小值,min_ind是个列表
    min_ind=float('inf')
    min_val=float('inf')
    for i in dis:
        if not i in processed:
            if dis[i]<min_val:
                min_val=dis[i]
                min_ind=[i]
            elif dis[i]==min_val and dis[i]!=float('inf'):
                min_ind.append(i)
    return min_ind

def min_dis(G,dis,fat,end):
    processed=[]
    while True:
        node_list=min_node(dis,processed)
        if node_list==float('inf') or len(processed)==len(G):
            return dis[end]
        for node in node_list:
            processed.append(node)
            for neighbor in G[node]:
                if not neighbor[0] in processed:
                    tmp_dis=neighbor[1] + dis[node]
                    if tmp_dis<dis[neighbor[0]]:    #只有比dis中的路径短时，才能保存。避免多个最小值都对dis修改
                        dis[neighbor[0]]=tmp_dis
                        fat[neighbor[0]]=node   #保存父节点
                    if node==end:
                        return dis[end]         #当终点加入被处理数组，说明寻找已经结束

def print_fat(fat,end): #显示父节点
    f=fat[end]
    print(str(end)+'的父节点依次是：')
    while(f!=1):
        print(f)
        f=fat[f]
    print(str(1))

while True:     #主程序
    line = input()
    line = line.split(' ')
    line = list(map(int, line))
    if line[0]!=00:         #当输入00时停止
        G,start,end=graph(line)
        dis_=dis(G)         #初始化G、dis、fat
        fat_=fat(dis_)
        dis_[start]=0
        fat_[start]=start
        min_dis_=min_dis(G,dis_,fat_,end)
        print('最短路程为：'+str(min_dis_))
        print_fat(fat_,end)
    else:
        break

测试数据：
4 4
1 2 3
1 3 3
2 4 2
3 4 1
测试结果：
从1到4的最短路程为：4

终点4的父节点依次是：
3
1

最长路径算法改动只有两点：1将输入路程改为负数；2将输出结果改为正数

#G:初始图
#dis：起点距离图
#fat：父节点图
def graph(line):
    G={}
    start=1
    end=line[0]
    for i in range(line[1]):
        line = input()
        line = line.split(' ')
        line = list(map(int, line))
        line[2]=-line[2]
        for i in range(2):   #关键点1，对每条路线，要互相保存邻居
            if line[i] in G.keys():
                G[line[i]].append([line[1-i],line[2]])
            else:
                G[line[i]]=[]  #不存在时，要初始化
                G[line[i]].append([line[1-i], line[2]])
    return G,start,end

def dis(G):
    dis={}
    for i in G:
        dis[i]=float('inf') #距离初始化为无穷大
    return dis

def fat(dis):
    fat={}
    for i in dis:
        fat[i]=[]
    return fat

def min_node(dis,processed):#可能会有多个最小值,min_ind是个列表
    min_ind=float('inf')
    min_val=float('inf')
    for i in dis:
        if not i in processed:
            if dis[i]<min_val:
                min_val=dis[i]
                min_ind=[i]
            elif dis[i]==min_val and dis[i]!=float('inf'):
                min_ind.append(i)
    return min_ind

def min_dis(G,dis,fat,end):
    processed=[]
    while True:
        node_list=min_node(dis,processed)
        if node_list==float('inf') or len(processed)==len(G):       #当连接图全部搜索完，或者整张图搜索完时返回
            return dis[end]
        for node in node_list:
            processed.append(node)
            for neighbor in G[node]:
                if not neighbor[0] in processed:
                    tmp_dis=neighbor[1] + dis[node]
                    if tmp_dis<dis[neighbor[0]]:    #多最小值情况：只有比dis中的路径短时，才能保存。避免多个最小值都对dis修改
                        dis[neighbor[0]]=tmp_dis
                        fat[neighbor[0]]=node   #保存父节点
                    if node==end:
                        return dis[end]         #当终点加入被处理数组，说明寻找已经结束

def print_fat(fat,end): #显示父节点
    f=fat[end]
    print(str(end)+'的父节点依次是：')
    while(f!=1):
        print(f)
        f=fat[f]
    print(str(1))

while True:     #主程序
    line = input()
    line = line.split(' ')
    line = list(map(int, line))
    if line[0]!=00:         #当输入00时停止
        G,start,end=graph(line)
        dis_=dis(G)         #初始化G、dis、fat
        fat_=fat(dis_)
        dis_[start]=0
        fat_[start]=start
        min_dis_=min_dis(G,dis_,fat_,end)
        print('最长路程为：'+str(-min_dis_))
        print_fat(fat_,end)
    else:
        break

第8章贪婪算法
假设偷东西，有许多物品可供选择，且价值不同，但背包空间有限，求偷到最大价值的最近似解。需要每次都取当前最大价值的东西，如果太重了，就取第二大的。
该算法不能解决可以可以拆分的物品，如一袋米中取半袋，而动态规划可以

def max_val(arr_val,arr_vol,vol):
    ind=arr_val.index(max(arr_val))#找最大价值的东西在哪
    current_val = arr_val[ind]
    arr_val[ind] = 0  #无论拿不拿都算检查过了，不再考虑该价值
    if current_val: #是否全部检查完毕
        if arr_vol[ind] <= vol:  #是否可拿
            return max_val(arr_val, arr_vol, vol - arr_vol[ind]) + current_val
        else:#不拿的话，继续判断次高价值的东西
            return max_val(arr_val, arr_vol, vol)
    else:
        return 0

第9章动态规划
1.二维数组法（华为2018.8.8机试第二题）
01背包，到底拿还是不拿呢？

jiazhi=[6,3,5,4,6]
zhongliang=[2,2,6,5,4]
rongliang=10

import sys
test=sys.stdin.readline().split(',')
jiazhi=list(test)
print(int(test[2]))
zhongliang=list(sys.stdin.readline())

rongliang=int(sys.stdin.readline())

cell=[[-1 for j in range(rongliang)] for i in range(len(zhongliang))]
for i in range(len(zhongliang)):
    for j in range(rongliang):
        if i==0:
            if j+1>=zhongliang[i]:
                cell[i][j]=jiazhi[i]
            else:
                cell[i][j]=0
        else:
            p=j - zhongliang[i]
            if p<0:
                cell[i][j]=cell[i-1][j]
            else:
                if cell[i-1][j]>cell[i-1][p]+jiazhi[i]:
                    cell[i][j]=cell[i-1][j]
                else:
                    cell[i][j] =cell[i-1][p]+jiazhi[i]

print(cell[len(zhongliang)-1][rongliang-1])

2.逆向递归——正循环
例：设opt(i)为i以内的最优解，则该最优解可以分解为：

    opt(i)=better{opt(i-1)，opt(i-1)+arr[i]}

比较第i个项目做还是不做时的最优解，从而递归

但该过程可以使用循环的方式来做，复杂度从O(n2)到O(n)：
设置好opt一维数组前几个数的初始状态,同样也是上面递归的出口，如opt(1)、opt(2)等

for j in range(3,i):
    opt(j)=better{opt(j-1)，opt(j-1)+arr[j]}

这种算法，意味着在有限的空间内完成最佳配比，与贪婪不同的是，贪婪取当前步最优，动态规划解全局最优。
毕竟动态规划是从上而下分析的，有一个从上头派下来的政委better指导工作，贯彻上头的意思。
分析到底部就会发现，底部的如果达到了最佳，那么上一层的也会最佳。于是前面都求最佳了，最终的结果也同样是最佳。这倒是和分而治之的道理有点像，小问题能用一个函数解决，大问题也同样可以用这个函数解决。

3圣诞苹果问题：

cell[i][j]=bigger(cell[i-1][j],cell[i][j-1])+G[i][j]

4最长公共子串

if word_a[i]==word_b[j]:
    cell[i][j]=cell[i-1][j-1]+1
else:
cell[i][j]=max(cell[i-1][j],cell[i][j-1])

第10章 K最近邻
数据先归一化
然后取多维空间的欧氏距离最近的K个，多着为胜

《图解算法》学习笔记

将笔记本硬盘自制成移动硬盘的方法图解

jQuery学习笔记之jQuery+CSS3的浏览器兼容性

ASP.NET学习笔记（五）-全球化部署，网站发布方法，AJAX使用，水晶报表使用，DropDownList，CheckBox全选

Python基础学习笔记

【莫烦强化学习】视频笔记（二）3.Q_Learning算法实现走迷宫

Linux学习笔记（一）：入门知识

Linux学习笔记（三）：磁盘和文件系统管理

Linux学习笔记（二）：文件目录管理和VIM编辑器的使用

Linux学习笔记（三）：权限管理（文件目录权限、用户权限）

NumPy 学习笔记（四）