Python 30个常用算法

def linear_search(arr, target):
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1

print(linear_search([4, 2, 7, 1, 9], 7))      # → 2

def binary_search(arr, target):
    left, right = 0, len(arr) -1
    while left<= right:
        mid = (left+right) //2
        if arr[mid] == target:
            return mid
        elif arr[mid] <target:
            left = mid+1
        else:
            right = mid-1
    return -1

print(binary_search([1, 3, 5, 7, 9], 5))      # → 2

def selection_sort(arr):
    for i in range(len(arr)):
        min_i = i
        for j in range(i+1, len(arr)):
            if arr[j] <arr[min_i]:
                min_i = j
        arr[i], arr[min_i] = arr[min_i], arr[i]
    return arr

print(selection_sort([64, 25, 12, 22, 11]))  # → [11, 12, 22, 25, 64]

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j>= 0 and arr[j] >key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

print(insertion_sort([12, 11, 13, 5, 6]))    # → [5, 6, 11, 12, 13]

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) //2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    res, i, j = [], 0, 0
    while i<len(left) and j<len(right):
        if left[i] <right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))  # → [3, 9, 10, 27, 38, 43, 82]

class Node:
    def__init__(self, val):
        self.val, self.left, self.right = val, None, None

# 构造示例树
root = Node(1); root.left = Node(2); root.right = Node(3)
root.left.left = Node(4); root.left.right = Node(5)

def preorder(r):
    return [r.val] +preorder(r.left) +preorder(r.right)

def inorder(r):
    return inorder(r.left) + [r.val] +inorder(r.right)

def postorder(r):
    return postorder(r.left) +postorder(r.right) + [r.val]

print(preorder(root))   # → [1, 2, 4, 5, 3]
print(inorder(root))    # → [4, 2, 5, 1, 3]
print(postorder(root))  # → [4, 5, 2, 3, 1]

from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])
    visited.add(start)
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for n in graph[v]:
            if n not in visited:
                visited.add(n); queue.append(n)

graph = {'A':['B','C'],'B':['A','D','E'],'C':['A','F'],'D':['B'],'E':['B','F'],'F':['C','E']}
bfs(graph, 'A')  # → A B C D E F

def dfs(graph, start, visited=None):
    if visited is None: visited = set()
    visited.add(start)
    print(start, end=' ')
    for n in graph[start]:
        if n not in visited: dfs(graph, n, visited)

dfs(graph, 'A')  # → A B D E F C

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d>dist[u]: continue
        for v, w in graph[u].items():
            nd = d+w
            if nd<dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

g = {'A':{'B':1,'C':4},'B':{'A':1,'C':2,'D':5},'C':{'A':4,'B':2,'D':1},'D':{'B':5,'C':1}}
print(dijkstra(g, 'A'))  # → {'A': 0, 'B': 1, 'C': 3, 'D': 4}

def floyd_warshall(g):
    n = len(g)
    dist = [[float('inf')]*n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for u in g:
        for v, w in g[u].items(): dist[u][v] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] +dist[k][j])
    return dist

g = {0:{1:3,2:6},1:{0:3,2:2},2:{0:6,1:2}}
print(floyd_warshall(g))  # → [[0, 3, 5], [3, 0, 2], [5, 2, 0]]

class UnionFind:
    def __init__(self, n): self.p = list(range(n))
    def find(self, x):
        if self.p[x] != x: self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, x, y): self.p[self.find(y)] = self.find(x)

def kruskal(g):
    edges = [(w, u, v) for u in g for v, w in g[u].items()]
    edges.sort()
    uf, mst = UnionFind(len(g)), []
    for w, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v); mst.append((u, v, w))
    return mst

g = {0:{1:10,2:6},1:{0:10,2:5},2:{0:6,1:5}}
print(kruskal(g))  # → [(1, 2, 5), (0, 2, 6)]

import heapq

def prim(g, start=0):
    visited, mst = {start}, []
    edges = [(w, start, v) for v, w in g[start].items()]
    heapq.heapify(edges)
    while edges:
        w, u, v = heapq.heappop(edges)
        if v not in visited:
            visited.add(v); mst.append((u, v, w))
            for v2, w2 in g[v].items():
                if v2 not in visited: heapq.heappush(edges, (w2, v, v2))
    return mst

print(prim(g))  # → [(0, 2, 6), (2, 1, 5)]

from collections import deque, defaultdict

def topological_sort(graph):
    indeg = defaultdict(int)
    for u in graph:
        for v in graph[u]: indeg[v] += 1
    q = deque([u for u in graphifindeg[u] == 0])
    res = []
    while q:
        u = q.popleft(); res.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return res if len(res) == len(graph) else None  # None 表示有环

g = {0:[1,2],1:[3],2:[3],3:[]}
print(topological_sort(g))  # → [0, 1, 2, 3]

def fib(n):
    if n<= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b

print(fib(10))  # → 55

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] +1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs("abcde", "ace"))  # → 3

def knapsack(w, v, cap):
    n = len(w)
    dp = [0] * (cap+1)
    for i in range(n):
        for c in range(cap, w[i] -1, -1):
            dp[c] = max(dp[c], dp[c-w[i]] +v[i])
    return dp[cap]

w = [1, 2, 3]; v = [6, 10, 12]; cap = 5
print(knapsack(w, v, cap))  # → 22

def lis(arr):
    if not arr: return0
    dp = [1] *len(arr)
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] >arr[j]:
                dp[i] = max(dp[i], dp[j] +1)
    return max(dp)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # → 4

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

print(edit_distance("horse", "ros"))  # → 3

def activity_selection(start, finish):
    acts = sorted(zip(start, finish), key=lambdax: x[1])
    res = [acts[0]]
    last = acts[0][1]
    for s, f in acts[1:]:
        if s>= last:
            res.append((s, f))
            last = f
    return res

s = [1, 3, 0, 5, 8, 5]; f = [2, 4, 6, 7, 9, 9]
print(activity_selection(s, f))  # → [(1, 2), (3, 4), (5, 7), (8, 9)]

import heapq
from collections import defaultdict

def huffman(freq):
    heap = [[w, [sym, ""]] for sym, w in freq.items()]
    heapq.heapify(heap)
    while len(heap) >1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]: pair[1] = '0'+pair[1]
        for pair in hi[1:]: pair[1] = '1'+pair[1]
        heapq.heappush(heap, [lo[0] +hi[0]] +lo[1:] +hi[1:])
    return {sym: code for sym, code in heap[0][1:]}

freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
print(huffman(freq))  # → {'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111'}

def fractional_knapsack(values, weights, capacity):
    items = sorted(zip(values, weights), key=lambdax: x[0]/x[1], reverse=True)
    total = 0.0
    for v, w in items:
        if capacity>= w:
            total += v; capacity -= w
        else:
            total += v*capacity/w; break
    return total

values = [60, 100, 120]; weights = [10, 20, 30]; capacity = 50
print(fractional_knapsack(values, weights, capacity))  # → 240.0

def coin_change(coins, amount):
    coins.sort(reverse=True)
    res = []
    for c in coins:
        while amount>= c:
            res.append(c); amount -= c
    return res if amount == 0elseNone

print(coin_change([1, 5, 10, 25], 63))  # → [25, 25, 10, 1, 1, 1]

def interval_scheduling(intervals):
    intervals.sort(key=lambdax: x[1])
    res, last_end = [], float('-inf')
    for s, e in intervals:
        if s>= last_end:
            res.append((s, e)); last_end = e
    return res

print(interval_scheduling([(1, 3), (2, 4), (3, 5), (6, 8)]))  # → [(1, 3), (3, 5), (6, 8)]

def permute(nums):
    res = []
    def dfs(first=0):
        if first == len(nums):
            res.append(nums.copy()); return
        for i in range(first, len(nums)):
            nums[first], nums[i] = nums[i], nums[first]
            dfs(first+1)
            nums[first], nums[i] = nums[i], nums[first]
    dfs()
    return res

print(permute([1, 2, 3]))

def combination_sum(candidates, target):
    res = []
    def dfs(remain, path, start):
        if remain == 0: res.append(path); return
        if remain<0: return
        for i in range(start, len(candidates)):
            dfs(remain-candidates[i], path+ [candidates[i]], i)
    dfs(target, [], 0)
    return res

print(combination_sum([2, 3, 6, 7], 7))  # → [[2, 2, 3], [7]]

def solve_n_queens(n):
    res, cols, diag1, diag2 = [], set(), set(), set()

    def dfs(row, path):
        if row == n:
            res.append(['.'*c+'Q'+'.'* (n-1-c) for c in path])
            return
        for c in range(n):
            d1, d2 = row-c, row+c
            if c in cols or d1 in diag1or d2 in diag2: continue
            cols.add(c); diag1.add(d1); diag2.add(d2)
            dfs(row+1, path+ [c])
            cols.remove(c); diag1.remove(d1); diag2.remove(d2)

    dfs(0, [])
    return res

print(len(solve_n_queens(4)))  # → 2 个合法解

def subsets(nums):
    res = []
    def dfs(path, i):
        if i == len(nums):
            res.append(path); return
        dfs(path+ [nums[i]], i+1)  # 选
        dfs(path, i+1)              # 不选
    dfs([], 0)
    return res

print(subsets([1, 2, 3]))

def solve_sudoku(board):
    def is_valid(r, c, num):
        for i in range(9):
            if board[r][i] == num or board[i][c] == num: return False
        br, bc = (r//3) *3, (c//3) *3
        for i in range(3):
            for j in range(3):
                if board[br+i][bc+j] == num: return False
        return True

    def dfs():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for num in map(str, range(1, 10)):
                        if is_valid(r, c, num):
                            board[r][c] = num
                            if dfs(): return True
                            board[r][c] = '.'
                    return False
        return True

    dfs()
    return board

b = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
solve_sudoku(b)
for row in b: print(row)  # 已填充完整棋盘