《算法图解》阅读笔记

def binary_search(list, item):
    low = 0
    high = len(list)
    while low <= high:
        mid = int((low + high) / 2)
        mid_v = list[mid]
        if mid_v == item:
            return mid
        elif mid_v < item:
            low = mid + 1
        else:
            high = mid - 1
    return None

print(binary_search([1,4,5,7,8,33,333,445], 33))

def findSmallest(arr):
    smallest = arr[0]
    smallest_idx = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest_idx = i
            smallest = arr[i]
    return smallest_idx

def selectionSort(arr):
    result = []
    for i in range(len(arr)):
        smallest_idx = findSmallest(arr)
        result.append(arr.pop(smallest_idx))
    return result

print(selectionSort([1,5,3,1,3,5,7,4,3,2,4]))
print(selectionSort([1,5,3,345,23,12,3,4]))

def quicksort(arr):
    if len(arr) < 2:
        return arr
    base = arr.pop()
    low_arr = []
    high_arr = []
    for i in arr:
        if i > base:
            high_arr.append(i)
        else:
            low_arr.append(i)
    return quicksort(low_arr) + [base] + quicksort(high_arr)

quicksort([1,2,33,43,3,9,2,3,1])

from collections import deque

graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['alice'] = ['job', 'claire']
graph['claire'] = ['marry']
graph['marry'] = ['mark']

def is_seller(person):
    return person == 'mark'

search_queue = deque()
search_queue += graph['you']
print(graph)

def search(search_queue):
    searched = set()
    while search_queue:
        person = search_queue.popleft()
        if person in searched:
            continue
        searched.add(person)
        if is_seller(person):
            print('find seller')
            return True
        elif graph.get(person):
            search_queue += graph[person]
    return False

search(search_queue)

def find_lowest_cost_node(costs, processed):
    lowest_cost = float('inf')
    lowest_node = None
    for n in costs.keys():
        if n not in processed and costs[n] < lowest_cost:
            lowest_cost = costs[n]
            lowest_node = n
    return lowest_node


def find_lowest_path(graph):
    processed = set()
    costs = {}
    parents = {}
    for n in graph['start'].keys():
        costs[n] = graph['start'][n]
        parents[n] = 'start'
    node = find_lowest_cost_node(costs, processed)
    while node is not None:
        cost = costs[node]
        if node in graph:
            neighbors = graph[node]
            for n in neighbors.keys():
                new_cost = cost + neighbors[n]
                if n not in costs or costs[n] > new_cost:
                    costs[n] = new_cost
                    parents[n] = node
        processed.add(node)
        node = find_lowest_cost_node(costs, processed)
    print(costs['fin'])
    str = 'fin'
    parent = parents['fin']
    while parent in parents:
        str = parent + '->' + str
        parent = parents[parent]
    print('start->' + str)

graph = {}
graph['start'] = {}
graph['start']['a'] = 3
graph['start']['b'] = 5
graph['a'] = {}
graph['a']['c'] = 6
graph['b'] = {}
graph['b']['fin'] = 14
graph['c'] = {}
graph['c']['fin'] = 1
print(graph)
find_lowest_path(graph)

graph1 = {}
graph1['start'] = {}
graph1['start']['a'] = 5
graph1['start']['b'] = 2
graph1['b'] = {}
graph1['b']['a'] = 8
graph1['b']['d'] = 7
graph1['a'] = {}
graph1['a']['c'] = 4
graph1['a']['d'] = 2
graph1['c'] = {}
graph1['c']['d'] = 6
graph1['c']['fin'] = 3
graph1['d'] = {}
graph1['d']['fin'] = 1
print(graph1)
find_lowest_path(graph1)

stations = {}
stations["k1"] = {"id", "nv", "ut"}
stations["k2"] = {"wa", "id", "mt"}
stations["k3"] = {"or", "nv", "ca"}
stations["k4"] = {"nv", "ut"}
stations["k5"] = {"ca", "az"}

# 找出覆盖所有 states 的最小的集合，

def find_min(stations):
    result_stations = set()
    states_covered = set()

    while True:
        best_states = set()
        best_station = None
        for station, states in stations.items():
            if station not in result_stations:
                covered = states - states_covered
                if len(covered) > len(best_states):
                    best_states = covered
                    best_station = station
        if best_station == None:
            break
        result_stations.add(best_station)
        states_covered = states_covered | best_states
    return result_stations

print(find_min(stations))