<图解算法>读后笔记

1. 二分查找

def binary_search(li, num):
    """
    :param li: 有序列表 
    :param num: 指定数字
    :return: 
    """
    low = 0
    high = len(li) - 1
    while low <= high:
        mid = int((low+high) / 2)
        guess = li[mid]
        if guess == num:
            return mid
        elif guess > num:
            high = mid - 1
        else:
            low = mid + 1
    return None

2. 选择排序

li = [1, 5, 7, 3, 2, 9]

def selection_sort(li):
    result = []
    for i in range(len(li)):
        minest = min(li)
        result.append(li.pop(li.index(minest)))
    return result

3. 快速排序

li = [1, 5, 7, 3, 2, 9]

def quicksort(li):
    if len(li) <= 1:
        return li
    guard = li[0]
    less = [l for l in li[1:] if l < guard]
    more = [l for l in li[1:] if l >= guard]
    return quicksort(more) + [guard] + quicksort(less)

4. fibonacci

def fibonacci(num):
    if num <= 0:
        return None
    elif num <= 2:
        return 1
    return fibonacci(num-1) + fibonacci(num-2)

def fib2(num):
    a, b = 0, 1
    for i in range(num):
        a, b = b, a + b
    return a

5. 广度优先算法

查找最短路径, 无向图

广度优先算法.png

graph = {
    'alice': ['peggy'],
    'anuj': [],
    'bob': ['anuj', 'peggy'],
    'claire': ['thom', 'jonny'],
    'jonny': [],
    'peggy': [],
    'thom': [],
    'you': ['alice', 'bob', 'claire']
}
from collections import deque

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []

    while search_queue:
        person = search_queue.popleft()
        if person in searched:
            continue
        if check_person(person):
            print(f"{person} is the man")
            return True
        else:
            searched.append(person)
            search_queue += graph[person]
    return False

6. 狄克斯特拉算法

加权图, 查找最短路径
无负权边

狄克斯特拉算法.png

infinity = float("inf")
graph = {
    'a': {'b': 4, 'd': 2},
    'b': {'d': 6, 'fin': 3},
    'c': {'a': 8, 'd': 7},
    'd': {'fin': 1},
    'fin': {},
    'start': {'a': 5, 'c': 2}
}
costs = {
    "a": 5,
    "c": 2,
    "b": infinity,
    "d": infinity,
    "fin": infinity
}
parents = {
    "a": "start",
    "c": "start"
}
selected = []

def find_lowest_cost_node(costs):
    lowest_node = None
    lowest_cost = infinity
    for node, cost in costs.items():
        if node in selected:
            continue
        if cost < lowest_cost:
            lowest_cost = cost
            lowest_node = node
    return lowest_node

def shortest_path():
    node = find_lowest_cost_node(costs)
    while node:
        cost = costs[node]
        neighbours = graph[node]
        for n in neighbours:
            new_cost = cost + neighbours[n]
            if new_cost < costs[n]:
                costs[n] = new_cost
                parents[n] = node
        selected.append(node)
        node = find_lowest_cost_node(costs)
    return costs

7. 贪婪算法

选出覆盖所有州的电台

贪婪算法.png

stations = {
    'kfive': {'az', 'ca'},
    'kfour': {'nv', 'ut'},
    'kone': {'id', 'nv', 'ut'},
    'kthree': {'ca', 'nv', 'or'},
    'ktwo': {'id', 'mt', 'wa'}
}

def select_stations():
    states_need = {'az', 'ca', 'id', 'mt', 'nv', 'or', 'ut', 'wa'}
    stations_selected = []
    while states_need:
        best_station = None
        states_covered = set()
        for k, v in stations.items():
            covered = states_need.intersection(v)
            if len(covered) > len(states_covered):
                states_covered = covered
                best_station = k
        stations_selected.append(best_station)
        states_need -= states_covered
    return stations_selected

8. 最长公共子串

最长公共子串.png

9. 最长公共子序列

最长公共子序列.png

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

番外: 嫌疑人问题

a: 凶手不是我
b: 凶手是c
c: 凶手是d
d: c在说谎
四个人里有一个人在说谎, 问凶手是谁

for l in ["a", "b", "c", "d"]:
    if ((l != 'a') + (l == 'c') + (l == 'd') + (l != 'd')) == 3:
        print(l)