演算法基礎， 常用演算法總結

接觸的一些演算法，搞不清楚搞得清楚的 列一個，大部分是最近看演算法圖解裡邊的演算法，平常也經常用到，包括

二分查找，選擇排序，快速排序，BFS DFS 動態規劃

def binary_search(arr,item):
    #二分查找
    l,h=0,len(arr)-1
    while l<h:
        mid=(l+h)//2
        if arr[mid]<item:
            l = mid + 1
        elif arr[mid]>item:
            h=mid-1
        else:
            return  mid
    return None

def selectsort(arr):
    #選擇排序
    n=len(arr)
    if n<2:return 
    start=0
    while start<n:
        res=[]
        index=start
        #每次找剩下的最小值
        for i in range(start+1,len(arr)):
            if arr[i] < arr[index]:
                index=i
            
        t=arr[index]
        arr[index]=arr[start]
        arr[start]=t
        start+=1


def quicksort(arr):
    #快速排序
    if len(arr)<2:return arr
    else:
        pivot=arr[0]
        #每次把序列分成小於基準和大於基準的
        less=[i for i in arr[1:] if i<=pivot]
        greator=[i for i in arr[1:] if i >pivot]
        return quicksort(less) + [pivot]+ quicksort(greator)

        
def bfs(node,target):
    #查找路徑是否存在
    from collections import deque
    search_queue=deque()
    searched=[]
    search_queue.append(name)
    while search_queue:
        p=search_queue.popleft()
        if p not in searched:
            if p == target:
                return True
            else:
                search_queue.append(p.next)
                searched.append(p)
    return False

    
class Node:
   
    def __init__(self,x,y,step):
        self.x=x
        self.y=y
        self.step=step
        pass


def bfs(Arr,target):
    #走迷宮問題
    from collections import deque
    r=len(Arr)
    c=len(Arr[0])
    visit=Arr[None]*c
    for i in range(r):
        visti[i]=[0]*r
    
    step=[[-1,0],[1,0],[0,-1],[0,1]]
    q=deque()
    q.append(Node(0,0,0))
    while q:
        cur=q.popleft()
        if cur.x==target[0] and cur.y==target[1]:
            return cur.step
        for i in step:
            nr=cur[0]+i[0]
            nc=cur[1]+i[1]
            if nr>=0 and nc>=0 and nr<r and nc<c and visit[nr][nc]==0:
                visit[nr][nc]=steps
                if Arr[nr][nc]==1:#能走加入隊列累加步數
                    q.append(Node(nr,nc,cur.step+1))

    return 0


def dp(dicstuf,bag):
    #動態規劃 背包問題
    #dicstruf 一組二位數組，[[1,2]]  第一位表示重量，第二位表示價值
    cell=[None]*len(dicstuf)
    for i in range(len(dicstuf)):
        cell[i]=[0]*bag
    
    for i in len(dicstuf):
        for j in bag:
            if i==0 and dicstuf[i][0]<j:
                cell[i][j]=dicstuf[i][1]
            else:
                if dicstuf[i][0]<j:# 比較上一個單元格和當前單元格放了當前商品+剩餘價值
                    cell[i][j]=max(cell[i-1][j],cell[i-1][j-dicstuf[i][0]])
                else:
                    cell[i][j]=cell[i-1][j]

    return cell[-1][-1]

def dfs(nums,k):
    #部分求和問題， nums為數字序列，k為和，求一個序列和為k
    #類似與二叉樹求路徑和為k的路徑，nums又n個數，構建n層的完全二叉樹，根節點    
    #為0，每個左節點為0，右子節點為nums[c]，c為層數，然後遍歷所有路徑求路徑和為k的路徑就是的··· 前邊有一次做的lintcode題目就是這個·
    res=[]
    def dfssum(i,sum):
        if i >=len(nums):
            return sum==k
        if sum>k:
            return False
        if dfssum(i+1,sum):
            return True
        if dfssum(i+1,sum+nums[i]):
            res.append(nums[i])
            return True
        return False

    if dfssum(0,0):return res
    return []