图解算法笔记

前言

最近,想了一下,好像有一年没刷题了,回顾去年刷的笔记,感觉忘的都差不多。于是找了本图解算法重新回顾一下,然后再去刷些题。这里记录一下笔记。

O

O(log n) 表示操作数,算法的运行时间不是以秒为单位,是以增速的角度度量的。

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def search(self, nums, target):
low = 0
high = len(nums) - 1

while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
if nums[mid] > target:
high = mid -1
else:
low = mid + 1
return -1

选择

数组:在内存中,元素是连在一起的,一般预留位置,如果再加元素超过位置,就要重新申请内存。
链表:元素可以存在任何地方,因为链表的每个元素都存储了下一个元素的地址。
读取,插入,删除: O(1) O(n), O(n) O(1), O(n) O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# O(n * 1/2 * n) => O(n * n)
def find_smallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index

def select_sort(arr):
new_arr = []
for i in range(len(arr)):
smallest = find_smallest(arr)
new_arr.append(arr.pop(smallest))
return new_arr

递归

递归(函数自身调用自己)一定要有基线条件,避免无限循环
调用栈(先进后出)

快排

1
2
3
4
5
6
7
8
9
# O(nlog n) ~ O(n * n) 每层O(n) 共(O(log n) ~ O(n))层
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
mid = arr[0]
left = [i for i in arr[1:] if i <= mid]
right = [i for i in arr[1:] if i > mid]
return quick_sort(left) + [mid] + quick_sort(right)

广度优先

解决1: A=>B 有路径吗 2:A=>B 哪条路径最短
图由节点和边组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# O(V+E) V顶点 E边数
from collections import deque
graph = {} # 图可以用字典表示,key表示节点,value表示邻居
graph['you'] = ['w', 'c', 'g']
graph['bob'] = ['tom', 'anuj']
graph['tom'] = []

def search(name):
search_queue = deque()
search_queue += graph['you'] # 先把我所有邻居加入队列
searched = [] # 记录检查过的人,避免无限循环
while search_queue: # 只要队列不为空
person = search_queue.popleft() # 从第一个开始, 取出第一个
if not person in searched:
if person_is_seller(person): # 是, 返回成功
print('{} is a seller'.format(person))
return True
else: # 否则, 将person的朋友加入队列尾部
search_queue += graph[person]
searched.append(person)
return False

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

狄克思特拉

找出加权图中前往x的最短路径,找出到达的最快路径,只适用有向无环图,不适用包含负权边的图,包含负权边的可以用贝尔曼-福德算法
关键理念:找出图中最便宜的节点,并确保没有到该节点的更便宜的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 需要3个字典,分别保存Graph, costs, parents
graph = {} # 保存节点的邻居和权重
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['fin'] = 1

graph['b'] = {}
graph['b']['a'] = 3
graph['b']['fin'] = 5

graph['fin'] = {}

costs = {} # 保存节点的开销,从起点到该节点需要多长时间
costs['a'] = 6
costs['b'] = 2
costs['fin'] = float('inf') # 终点不确定,用无穷大表示

parents = {} # 保存节点的父节点
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None

processed = [] # 保存处理过的节点

node = find_lowest_cost_node(costs) # 找出花费最小的节点
while node is not None:
cost = costs[node] # 花费
neighbors = graph[node] # 邻居
for n in neighbors.keys(): # 遍历邻居
new_cost = cost + neighbors[n] # 更新邻居节点从我经过的花费
if costs[n] > new_cost: # 和原来比较,如果大,就更新
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)

def find_lowest_cost_node(costs):
loweset_cost = float('inf')
loweset_cost_node = None
for node in costs:
cost = costs[node]
if cost < loweset_cost and node not in processed:
loweset_cost = cost
loweset_cost_node = node
return loweset_cost_node

贪婪

每一步都采取最优的做法,最终得到的是全局最优解,但并非任何情况下都行之有效。
NP完全问题:计算所有的解,并从中选出最小/最短的那个,如旅行商问题和集合覆盖问题,采用近似算法

动态规划

动态规划先解决子问题,再逐步解决大问题,动态问题都是从一个表格开始的, 如背包问题、最长公共子串
https://blog.itswcg.com/2018-04/python-dynamic.html

K最近邻(KNN)

分类和回归
垃圾邮件过滤器 -朴素贝叶斯分类器

其他

二叉查找树(左边的值小,右边大,查找类似二分(O(log n)))
B树是一种特殊的二叉树
分布式算法 MapReduce
布隆过滤器,是一种概率型数据结构,提供的答案不一定对,优点占用存储空间少
所有的图算法都可以用线性规划来实现,Simplex算法

参考

https://github.com/itswcg/Books/blob/master/%E7%AE%97%E6%B3%95%E5%9B%BE%E8%A7%A3.pdf

----------本文完,感谢您的阅读----------