图解算法读书笔记

从一个朋友那里学来的读书笔记的习惯 还不是很会写 努力吧
ps: 很多问题其实学生时期 是想过的呀 … 看这本书 经常会有一种 好像赚钱的方法都写在了刑法上了的感觉

排序

选择排序

code:

1
2
3
4
5
6
7
8
9
10
def findSmallest(arr):
    # 存储最小的值
    smallest = arr[0]
    # 存储最小的元素的 index
    smallest_index = 0
    for i in range(1,len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

快速排序

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quicksort(array):
    # 所有小于基准值的元素组成的子数组
    less = []
    # 所有大于基准值的元素组成的子数组
    greater = []
    if len(array) < 2:
        # 基线条件
        return array
    else:
        # 递归条件
        pivot = array[0]
        for i in array[1:]:
            if i <= pivot:
                less.append(i)
            if i > pivot:
                greater.append(i)
    return quicksort(less) + [pivot] + quicksort(greater)

图

广度优先搜索

广度优先搜索可以解决两类问题

  • 从节点 a 出发, 有前往节点 b 的路径么
  • 从节点 a 出发, 前往节点 b 的哪条路径最短

    使用广度优先搜索解决芒果销售商问题, 假设你经营一个芒果农场, 需要寻找芒果销售商(假设无重复好友)…

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    from collections import deque


    def person_is_seller(name):
        return name[-1] == 'm'


    def search_seller():
        graph = {'you': ['tom', 'jerry']}
        # 创建一个队列
        search_queue = deque()
        # 添加邻居
        search_queue += graph['you']
        # 只要队列不为空
        while search_queue:
            person = search_queue.popleft()
            if person_is_seller(person):
                print('{} is seller ...'.format(person))
                return True
            else:
                search_queue += graph[person]
                return False

    迪克斯特拉算法

    加权的广度优先搜索

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def find_lowest_cost_node(costs):
        lowest_cost = fload('inf')
        lowest_cost_node = None
        # 遍历所有节点
        for node in costs:
            cost = costs[nodes]
            # 如果当前节点的开销更低 且未处理过
            if cost < lowest_cost and node not in processes:
                # 将其视为开销最低的节点
                lowest_cost = cost
                lowest_cost_node = node
        return lowest_cost_node

    贪婪算法

    教室调度问题

    每步选择局部最优解 最终得到的就是全局最优解

    广播台问题

    使用贪婪算法计算近似最优解…

选择覆盖 50 个的州的最小电台合集 

1
2
3
4
5
6
7
8
9
10
while states_needed:
    best_station = None
    states_covered = set()
    for station, states in stations.items():
        covered = states_needed & states
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
        states_needed -= states_covered
        final_stations.add(best_station)

背包问题

动态规划

K 最近邻算法

KNN

橘子还是橙子

OCR

光学字符识别