图解算法读书笔记

从一个朋友那里学来的读书笔记的习惯 还不是很会写 努力吧
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

光学字符识别