defquick_sort(arr):iflen(arr)<=1:returnarr    else:pivot =arr[len(arr)//2]left =[x forx inarr ifx <pivot]middle =[x forx inarr ifx ==pivot]right =[x forx inarr ifx >pivot]returnquick_sort(left)+middle +quick_sort(right)# 示例print(quick_sort([3,6,8,10,1,2,1]))

defedit_distance(str1,str2):m =len(str1)n =len(str2)dp =[[0forx inrange(n+1)]forx inrange(m+1)]fori inrange(m+1):forj inrange(n+1):ifi ==0:dp[i][j]=j            elifj ==0:dp[i][j]=i            elifstr1[i-1]==str2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])returndp[m][n]# 示例str1 ="sunday"str2 ="saturday"print(edit_distance(str1,str2))

classGraph:def__init__(self,vertices):self.V =vertices        self.graph =[]defadd_edge(self,u,v,w):self.graph.append([u,v,w])deffind(self,parent,i):ifparent[i]==i:returni        returnself.find(parent,parent[i])defunion(self,parent,rank,x,y):xroot =self.find(parent,x)yroot =self.find(parent,y)ifrank[xroot]<rank[yroot]:parent[xroot]=yroot        elifrank[xroot]>rank[yroot]:parent[yroot]=xroot        else:parent[yroot]=xroot            rank[xroot]+=1defkruskal_mst(self):result =[]i =0e =0self.graph =sorted(self.graph,key=lambdaitem:item[2])parent =[]rank =[]fornode inrange(self.V):parent.append(node)rank.append(0)whilee <self.V -1:u,v,w =self.graph[i]i =i +1x =self.find(parent,u)y =self.find(parent,v)ifx !=y:e =e +1result.append([u,v,w])self.union(parent,rank,x,y)returnresult# 示例g =Graph(4)g.add_edge(0,1,10)g.add_edge(0,2,6)g.add_edge(0,3,5)g.add_edge(1,3,15)g.add_edge(2,3,4)print(g.kruskal_mst())

fromcollections importdequedefbfs(graph,start):visited =set()queue =deque([start])visited.add(start)whilequeue:vertex =queue.popleft()print(vertex,end=" ")forneighbour ingraph[vertex]:ifneighbour notinvisited:visited.add(neighbour)queue.append(neighbour)# 示例graph ={'A':['B','C','D'],'B':['E','F'],'C':['G'],'D':[],'E':[],'F':[],'G':[]}bfs(graph,'A')

deflinear_search(arr,x):fori inrange(len(arr)):ifarr[i]==x:returni    return-1# 示例arr =[2,3,4,10,40]x =10print(linear_search(arr,x))

deflis(arr):n =len(arr)lis =[1]*n    fori inrange(1,n):forj inrange(0,i):ifarr[i]>arr[j]andlis[i]<lis[j]+1:lis[i]=lis[j]+1maximum =0fori inrange(n):maximum =max(maximum,lis[i])returnmaximum# 示例arr =[10,22,9,33,21,50,41,60,80]print(lis(arr))

defbubble_sort(arr):n =len(arr)fori inrange(n):forj inrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr# 示例print(bubble_sort([64,34,25,12,22,11,90]))

defcounting_sort_exp(arr,exp1):n =len(arr)output =[0]*n    count =[0]*10fori inrange(0,n):index =arr[i]//exp1        count[index %10]+=1fori inrange(1,10):count[i]+=count[i -1]i =n -1whilei >=0:index =arr[i]//exp1        output[count[index %10]-1]=arr[i]count[index %10]-=1i -=1fori inrange(0,len(arr)):arr[i]=output[i]defradix_sort(arr):max1 =max(arr)exp =1whilemax1 //exp >0:counting_sort_exp(arr,exp)exp *=10returnarr# 示例print(radix_sort([170,45,75,90,802,24,2,66]))

defheapify(arr,n,i):largest =i    l =2*i +1r =2*i +2ifl <n andarr[i]<arr[l]:largest =l    ifr <n andarr[largest]<arr[r]:largest =r    iflargest !=i:arr[i],arr[largest]=arr[largest],arr[i]heapify(arr,n,largest)defheap_sort(arr):n =len(arr)fori inrange(n //2-1,-1,-1):heapify(arr,n,i)fori inrange(n-1,0,-1):arr[i],arr[0]=arr[0],arr[i]heapify(arr,i,0)returnarr# 示例print(heap_sort([12,11,13,5,6,7]))

defis_subset_sum(arr,n,sum):subset =[[Falsefori inrange(sum+1)]fori inrange(n +1)]fori inrange(n +1):subset[i][0]=Truefori inrange(1,sum+1):subset[0][i]=Falsefori inrange(1,n +1):forj inrange(1,sum+1):ifj <arr[i -1]:subset[i][j]=subset[i -1][j]ifj >=arr[i -1]:subset[i][j]=(subset[i -1][j]orsubset[i -1][j -arr[i -1]])returnsubset[n][sum]deffind_partition(arr,n):sum=0fori inrange(n):sum+=arr[i]ifsum%2!=0:returnFalsereturnis_subset_sum(arr,n,sum//2)# 示例arr =[3,1,5,9,12]n =len(arr)iffind_partition(arr,n)==True:print("Can be divided into two subsets of equal sum")else:print("Cannot be divided into two subsets of equal sum")

defbinary_search(arr,x):l =0r =len(arr)-1whilel <=r:mid =l +(r -l)//2ifarr[mid]==x:returnmid        elifarr[mid]<x:l =mid +1else:r =mid -1return-1# 示例arr =[2,3,4,10,40]x =10print(binary_search(arr,x))

defKMPSearch(pat,txt):M =len(pat)N =len(txt)lps =[0]*M    j =0computeLPSArray(pat,M,lps)i =0whilei <N:ifpat[j]==txt[i]:i +=1j +=1ifj ==M:print("Found pattern at index "+str(i-j))j =lps[j-1]elifi <N andpat[j]!=txt[i]:ifj !=0:j =lps[j-1]else:i +=1defcomputeLPSArray(pat,M,lps):length =0lps[0]=0i =1whilei <M:ifpat[i]==pat[length]:length +=1lps[i]=length            i +=1else:iflength !=0:length =lps[length-1]else:lps[i]=0i +=1# 示例txt ="ABABDABACDABABCABAB"pat ="ABABCABAB"KMPSearch(pat,txt)

deflcs(X,Y):m =len(X)n =len(Y)L =[[None]*(n+1)fori inrange(m+1)]fori inrange(m+1):forj inrange(n+1):ifi ==0orj ==0:L[i][j]=0elifX[i-1]==Y[j-1]:L[i][j]=L[i-1][j-1]+1else:L[i][j]=max(L[i-1][j],L[i][j-1])returnL[m][n]# 示例X ="AGGTAB"Y ="GXTXAYB"print(lcs(X,Y))

编辑距离（Edit Distance）

编辑距离用于计算两个字符串之间转换的最少操作数。

defmerge_sort(arr):iflen(arr)>1:mid =len(arr)//2L =arr[:mid]R =arr[mid:]merge_sort(L)merge_sort(R)i =j =k =0whilei <len(L)andj <len(R):ifL[i]<R[j]:arr[k]=L[i]i +=1else:arr[k]=R[j]j +=1k +=1whilei <len(L):arr[k]=L[i]i +=1k +=1whilej <len(R):arr[k]=R[j]j +=1k +=1returnarr# 示例print(merge_sort([12,11,13,5,6,7]))

堆排序（Heap Sort）

堆排序是一种基于堆数据结构的比较排序算法。

fromqueue importPriorityQueuedefheuristic(a,b):returnabs(b[0]-a[0])+abs(b[1]-a[1])defa_star(graph,start,goal):pq =PriorityQueue()pq.put((0,start))came_from ={}cost_so_far ={}came_from[start]=Nonecost_so_far[start]=0whilenotpq.empty():current =pq.get()[1]ifcurrent ==goal:breakfornextingraph[current]:new_cost =cost_so_far[current]+graph[current][next]ifnextnotincost_so_far ornew_cost <cost_so_far[next]:cost_so_far[next]=new_cost                priority =new_cost +heuristic(goal,next)pq.put((priority,next))came_from[next]=current    returncame_from,cost_so_far# 示例graph ={'A':{'B':1,'C':3},'B':{'A':1,'C':1,'D':6},'C':{'A':3,'B':1,'D':2,'E':4},'D':{'B':6,'C':2,'E':1},'E':{'C':4,'D':1}}start ='A'goal ='E'came_from,cost_so_far =a_star(graph,start,goal)print(came_from)print(cost_so_far)

拓扑排序（Topological Sort）

拓扑排序用于有向无环图（DAG）中的顶点排序。

defbellman_ford(graph,V,E,src):dist =[float("Inf")]*V    dist[src]=0for_ inrange(V -1):foru,v,w ingraph:ifdist[u]!=float("Inf")anddist[u]+w <dist[v]:dist[v]=dist[u]+w    foru,v,w ingraph:ifdist[u]!=float("Inf")anddist[u]+w <dist[v]:print("Graph contains negative weight cycle")returnreturndist# 示例V =5E =8graph =[[0,1,-1],[0,2,4],[1,2,3],[1,3,2],[1,4,2],[3,2,5],[3,1,1],[4,3,-3]]print(bellman_ford(graph,V,E,0))

最大子数组和（Kadane’s Algorithm）

Kadane’s算法用于查找具有最大和的连续子数组。

defjosephus(n,k):ifn ==1:return0else:return(josephus(n -1,k)+k)%n# 示例n =7k =3print("The chosen place is ",josephus(n,k))

集合划分问题（Partition Problem）

集合划分问题涉及将给定的集合划分为两个子集，使得它们的和相等。

defknapSack(W,wt,val,n):K =[[0forx inrange(W+1)]forx inrange(n+1)]fori inrange(n+1):forw inrange(W+1):ifi ==0orw ==0:K[i][w]=0elifwt[i-1]<=w:K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w])else:K[i][w]=K[i-1][w]returnK[n][W]# 示例val =[60,100,120]wt =[10,20,30]W =50n =len(val)print(knapSack(W,wt,val,n))

最长上升子序列（Longest Increasing Subsequence）

LIS用于查找最长的严格上升子序列。

defcounting_sort(arr):max_val =max(arr)m =max_val +1count =[0]*m                 fora inarr:count[a]+=1i =0fora inrange(m):forc inrange(count[a]):arr[i]=a            i +=1returnarr# 示例print(counting_sort([4,2,2,8,3,3,1]))

基数排序（Radix Sort）

基数排序是一种非比较整数排序算法，通过按位分配和排序来处理数字。

defbucket_sort(arr):bucket =[]fori inrange(len(arr)):bucket.append([])forj inarr:index_b =int(10*j)bucket[index_b].append(j)fori inrange(len(arr)):bucket[i]=sorted(bucket[i])k =0fori inrange(len(arr)):forj inrange(len(bucket[i])):arr[k]=bucket[i][j]k +=1returnarr# 示例print(bucket_sort([0.897,0.565,0.656,0.123,0.665,0.343]))

希尔排序（Shell Sort）

希尔排序是插入排序的一种更高效的改进版本，通过初始使用大间隔的插入排序来减少数据量。

deftower_of_hanoi(n,from_rod,to_rod,aux_rod):ifn ==1:print("Move disk 1 from rod",from_rod,"to rod",to_rod)returntower_of_hanoi(n-1,from_rod,aux_rod,to_rod)print("Move disk",n,"from rod",from_rod,"to rod",to_rod)tower_of_hanoi(n-1,aux_rod,to_rod,from_rod)# 示例n =4tower_of_hanoi(n,'A','C','B')

N皇后问题（N-Queens Problem）

N皇后问题涉及在N x N的棋盘上放置N个皇后，使得它们彼此之间不会攻击。

defdfs(graph,start,visited=None):ifvisited isNone:visited =set()visited.add(start)print(start,end=" ")fornextingraph[start]-visited:dfs(graph,next,visited)returnvisited# 示例graph ={'A':set(['B','C']),'B':set(['A','D','E']),'C':set(['A','F']),'D':set(['B']),'E':set(['B','F']),'F':set(['C','E'])}dfs(graph,'A')

Dijkstra算法

Dijkstra算法用于查找加权图中从单个顶点到其他顶点的最短路径。

defis_safe(maze,x,y,n):ifx >=0andx <n andy >=0andy <n andmaze[x][y]==1:returnTruereturnFalsedefsolve_maze_util(maze,x,y,sol,n):ifx ==n -1andy ==n -1andmaze[x][y]==1:sol[x][y]=1returnTrueifis_safe(maze,x,y,n):ifsol[x][y]==1:returnFalsesol[x][y]=1ifsolve_maze_util(maze,x +1,y,sol,n):returnTrueifsolve_maze_util(maze,x,y +1,sol,n):returnTrueifsolve_maze_util(maze,x -1,y,sol,n):returnTrueifsolve_maze_util(maze,x,y -1,sol,n):returnTruesol[x][y]=0returnFalsedefsolve_maze(maze):n =len(maze)sol =[[0forj inrange(n)]fori inrange(n)]ifnotsolve_maze_util(maze,0,0,sol,n):print("Solution does not exist")returnFalseprint_solution(sol)returnTrue# 示例maze =[[1,0,0,0],[1,1,0,1],[0,1,0,0],[1,1,1,1]]solve_maze(maze)

图的颜色问题（Graph Coloring Problem）

图的颜色问题涉及为图的顶点着色，使得相邻顶点不具有相同颜色。

INF =float('inf')deffloyd_warshall(graph):dist =list(map(lambdai:list(map(lambdaj:j,i)),graph))V =len(graph)fork inrange(V):fori inrange(V):forj inrange(V):dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])returndist# 示例graph =[[0,5,INF,10],[INF,0,3,INF],[INF,INF,0,1],[INF,INF,INF,0]]print(floyd_warshall(graph))

贝尔曼-福特算法

贝尔曼-福特算法用于查找带负权重的加权图中从单个顶点到其他顶点的最短路径。

importsysdefdijkstra(graph,start):shortest_paths ={start:(None,0)}current_node =start    visited =set()whilecurrent_node isnotNone:visited.add(current_node)destinations =graph[current_node]weight_to_current_node =shortest_paths[current_node][1]fornext_node,weight indestinations.items():weight =weight_to_current_node +weight            ifnext_node notinshortest_paths:shortest_paths[next_node]=(current_node,weight)else:current_shortest_weight =shortest_paths[next_node][1]ifcurrent_shortest_weight >weight:shortest_paths[next_node]=(current_node,weight)next_destinations ={node:shortest_paths[node]fornode inshortest_paths ifnode notinvisited}ifnotnext_destinations:returnshortest_paths        current_node =min(next_destinations,key=lambdak:next_destinations[k][1])# 示例graph ={'A':{'B':1,'C':4},'B':{'A':1,'C':2,'D':5},'C':{'A':4,'B':2,'D':1},'D':{'B':5,'C':1}}start ='A'print(dijkstra(graph,start))

A*算法

A*算法用于在加权图中查找从起点到目标的最短路径。

importsysdefmin_key(key,mst_set,V):min=sys.maxsize    forv inrange(V):ifkey[v]<minandmst_set[v]==False:min=key[v]min_index =v    returnmin_indexdefprim_mst(graph,V):key =[sys.maxsize]*V    parent =[None]*V    key[0]=0mst_set =[False]*V    parent[0]=-1forcout inrange(V):u =min_key(key,mst_set,V)mst_set[u]=Trueforv inrange(V):ifgraph[u][v]andmst_set[v]==Falseandkey[v]>graph[u][v]:key[v]=graph[u][v]parent[v]=u    returnparent# 示例graph =[[0,2,0,6,0],[2,0,3,8,5],[0,3,0,0,7],[6,8,0,0,9],[0,5,7,9,0]]V =5parent =prim_mst(graph,V)fori inrange(1,V):print(parent[i],"-",i,"\t",graph[i][parent[i]])

Floyd-Warshall算法

Floyd-Warshall算法用于查找所有顶点对之间的最短路径。

fromcollections importdefaultdictdeftopological_sort_util(v,visited,stack,graph):visited[v]=Truefori ingraph[v]:ifnotvisited[i]:topological_sort_util(i,visited,stack,graph)stack.insert(0,v)deftopological_sort(graph):visited ={i:Falsefori ingraph}stack =[]fori ingraph:ifnotvisited[i]:topological_sort_util(i,visited,stack,graph)returnstack# 示例graph ={'A':['C'],'B':['C','D'],'C':['E'],'D':['F'],'E':['H','F'],'F':['G'],'G':[],'H':[]}print(topological_sort(graph))

Kruskal算法

Kruskal算法用于查找加权无向图的最小生成树。

defselection_sort(arr):fori inrange(len(arr)):min_idx =i        forj inrange(i+1,len(arr)):ifarr[j]<arr[min_idx]:min_idx =j        arr[i],arr[min_idx]=arr[min_idx],arr[i]returnarr# 示例print(selection_sort([64,25,12,22,11]))

插入排序（Insertion Sort）

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

definsertion_sort(arr):fori inrange(1,len(arr)):key =arr[i]j =i-1whilej >=0andkey <arr[j]:arr[j +1]=arr[j]j -=1arr[j +1]=key    returnarr# 示例print(insertion_sort([12,11,13,5,6]))

快速排序（Quick Sort）

快速排序是一种分治算法，它选择一个基准元素，分区操作使得比基准元素小的元素放在左边，比基准元素大的元素放在右边，然后递归地对两边进行排序。

defkadane(arr):max_so_far =arr[0]max_ending_here =arr[0]fori inrange(1,len(arr)):max_ending_here =max(arr[i],max_ending_here +arr[i])max_so_far =max(max_so_far,max_ending_here)returnmax_so_far# 示例print(kadane([1,-3,2,1,-1]))

最长公共子序列（Longest Common Subsequence）

LCS用于查找两个字符串的最长公共子序列。

文章目录

• 冒泡排序（Bubble Sort）
• 选择排序（Selection Sort）
• 插入排序（Insertion Sort）
• 快速排序（Quick Sort）
• 归并排序（Merge Sort）
• 堆排序（Heap Sort）
• 计数排序（Counting Sort）
• 基数排序（Radix Sort）
• 桶排序（Bucket Sort）
• 希尔排序（Shell Sort）
• 二分查找（Binary Search）
• 线性查找（Linear Search）
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• Dijkstra算法
• A*算法
• 拓扑排序（Topological Sort）
• Kruskal算法
• Prim算法
• Floyd-Warshall算法
• 贝尔曼-福特算法
• 最大子数组和（Kadane's Algorithm）
• 最长公共子序列（Longest Common Subsequence）
• 编辑距离（Edit Distance）
• 背包问题（Knapsack Problem）
• 最长上升子序列（Longest Increasing Subsequence）
• 汉诺塔问题（Tower of Hanoi）
• N皇后问题（N-Queens Problem）
• Rat in a Maze
• 图的颜色问题（Graph Coloring Problem）
• 约瑟夫斯问题（Josephus Problem）
• 集合划分问题（Partition Problem）
• 字符串匹配（KMP算法）

冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法之一。

defis_safe(v,graph,color,c):fori inrange(len(graph)):ifgraph[v][i]==1andcolor[i]==c:returnFalsereturnTruedefgraph_coloring_util(graph,m,color,v):ifv ==len(graph):returnTrueforc inrange(1,m +1):ifis_safe(v,graph,color,c):color[v]=c            ifgraph_coloring_util(graph,m,color,v +1):returnTruecolor[v]=0defgraph_coloring(graph,m):color =[0]*len(graph)ifnotgraph_coloring_util(graph,m,color,0):print("Solution does not exist")returnFalseprint("Solution exists: ",color)returnTrue# 示例graph =[[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]]m =3graph_coloring(graph,m)

约瑟夫斯问题（Josephus Problem）

约瑟夫斯问题涉及找到最后一个幸存者的位置。

defshell_sort(arr):n =len(arr)gap =n //2whilegap >0:fori inrange(gap,n):temp =arr[i]j =i            whilej >=gap andarr[j -gap]>temp:arr[j]=arr[j -gap]j -=gap            arr[j]=temp        gap //=2returnarr# 示例print(shell_sort([12,34,54,2,3]))

二分查找（Binary Search）

二分查找用于在有序数组中查找元素，通过反复将搜索范围缩小一半来找到目标元素。

defprint_solution(board):fori inboard:print(" ".join(str(x)forx ini))defis_safe(board,row,col,n):fori inrange(col):ifboard[row][i]==1:returnFalsefori,j inzip(range(row,-1,-1),range(col,-1,-1)):ifboard[i][j]==1:returnFalsefori,j inzip(range(row,n,1),range(col,-1,-1)):ifboard[i][j]==1:returnFalsereturnTruedefsolve_nq_util(board,col,n):ifcol >=n:returnTruefori inrange(n):ifis_safe(board,i,col,n):board[i][col]=1ifsolve_nq_util(board,col +1,n):returnTrueboard[i][col]=0returnFalsedefsolve_nq(n):board =[[0forj inrange(n)]fori inrange(n)]ifnotsolve_nq_util(board,0,n):print("Solution does not exist")returnFalseprint_solution(board)returnTrue# 示例n =4solve_nq(n)

Rat in a Maze

Rat in a Maze问题是经典的回溯问题，涉及找到迷宫的所有可能路径。

上一篇：卡牌游戏：探索未知的战略之旅

下一篇：阿里云、腾讯云、华为云平台数据库比较