图解算法

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = int((low + high) / 2) # 中间的
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None


my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

  • 最短路径问题:使用广度优先搜索,使用图来建立问题模型

  • 假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。

  • 查找最短路径,广度优先搜索可回答两类问题

    • 第一类问题:从节点A出发,有前往节点B的路径吗?(在你的人际关系网中,有芒果销 售商吗?)
    • 第二类问题:从节点A出发,前往节点B的哪条路径最短?(哪个芒果销售商与你的关系 最近?)
1
2
3
4
5
6
7
8
9
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collection import deque
search_queue = deque() # 创建一个队列
search_queue += graph['you'] # 将你的邻居都加入到这个搜索队列中

while search_queue: # 只要队列不为空
person = search_queue.popleft() # 就取出其中的第一个人
if person_is_seller(person): # 检查这个人是否是芒果商
print('{} is a mango seller!'.format('person') # 是芒果商
return True
else:
search_queue += graph[person] # 不是芒果销售商。将这个人的朋友都加入搜索队列
return False # 如果到达了这里,就说明队列中没人是芒果商

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

将一个人加入对列的时间是固定的O(1),总时间就为O(人数)。所以广度优先搜索的运行时间为O(人数+边数)


狄克斯特拉算法

  • 问题:其中每个数字表示的都是时间,单位分钟。为找出从起点到终点耗时最短的路径,你将使用 狄克斯特拉算法。
1
2
3
4
5
6
graph TD
A[起点] -->|6| B(A)
A[起点] -->|2| C(B)
C -->|3| B
B -->|1| D(终点)
C -->|5| D(终点)
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
49
50
51
52
53
54
55
56
57
graph = {}

graph["you"] = ["alice", "bob", "claire"]

# 使用散列表
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"] = {} # 终点没有任何邻居


infinity = float("inf")

# 创建开销表
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# 创建这个散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

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

# 代码
node = find_lowest_cost_node(costs) # 在未处理的节点中找出开销量最小的节点
while node is not None: # 这个while循环在所有节点都被处理过后结束
cost = costs[node]
neighbors = graph[node]
for n in neighbors.key(): # 遍历当前节点
new_cost = cost + neighbors[n]
if costs[n] > new_costs: # 如果经过当前节点前往该邻居更近
costs[n] = new_costs # 就更新该邻居的开销
parents[n] = node # 同时将该邻居的父节点设置为当前节点
processed.append(node) # 将当前节点标记为处理过
node = find_lowest_cost_node(costs) # 找出接下来要处理的节点

def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs: # 遍历所有的节点
cost = costs[node]
if cost < lowest_cost and node not in processed: # 如果当前节点的开销更低且未处理过
lowest_cost = cost # 就将其视为开销最低的节点
lowest_cost_node = node
return lowest_cost_node
  • 第一步:找出最便宜的节点
  • 第二步:计算经起点的下一节点前往其各个节点所需的时间
  • 第三步:重复
  • 重复第一步:找出可在最短时间内前往的节点。你对节点B执行了第二步,除节点B外,可在最短时间内前往的节点是节点A。
  • 重复第二步:更新节点A的所有邻居的开销。

  • 算法异同:

    • 使用广度优先搜索来查找两点之间的最短路径,这里的“最短路径”的意思是段数最少
    • 在狄克斯特拉算法中,你给每段都分配了一个数字或权重,因此狄克斯特拉算法找出的是总权重最小的路径。
  • 使用:

    • 要计算非加权图中的最短路径,可使用广度优先搜索。要计算加权图中的最短路径,可使用狄克斯特拉算法。
    • 狄克斯特拉算法只适用于有向无环图

贪婪算法

  • 贪婪算法并不能得到最优解,因为每步都是局部最优解

动态规划

  • 使用动态规划时,要么考虑拿走整件商品,要么考虑不拿,而没法判断该不该拿走商品的一部分。

问题:

  • 假设你要去伦敦度假,假期两天,但你想去游览的地方很多。你没法前往每个地方游览,因此你列个单子。
名胜 时间 评分
威斯敏斯特教堂 0.5天 7
环球剧场 0.5天 6
英国国家美术馆 1天 9
大英博物馆 2天 9
圣保罗大教堂 0.5天 8
  • 思路:
    • 使用网格,先建立空网格
0.5 1 1.5 2
威斯敏斯特教堂
环球剧场
英国国家美术馆
大英博物馆
圣保罗大教堂
    • 网格填充结果
0.5 1 1.5 2
威斯敏斯特教堂(w) 7(w) 7(w) 7(w) 7(w)
环球剧场(g) 7(w) 13(wg) 13(wg) 13(wg)
英国国家美术馆(n) 7(w) 13(wg) 16(wn) 22(wgn)
大英博物馆(b) 7(w) 13(wg) 16(wn) 22(wgn)
圣保罗大教堂(s) 8(s) 15(ws) 21(wgs) 24(wns)

填充表格从左到右,然后下一行,重复。

最长公共子串

  • 问题:HISH和FISH的最长公共子串是?

  • 思路:

    • 画表格
H I S H
F
I
S
H
    • 填充表格
H I S H
F 0 0 0 0
I 0 1 0 0
S 0 0 2 0
H 0 0 0 3

若果横纵字母相同则对应空格为1加上空格左上角邻居的值

1
2
3
4
5
# 实现这个公式的伪代码
if word_a[i] == word_b[j]: # 两个字母相同
cell[i][j] = cell[i-1][j-1] + 1
else: # 两个字母不同
cell[i][j] = 0

最长公共子序列之解决方案

  • 最长公共子序列:两个单词都有的序列包含的字母数

  • 问题:求fish和fosh的最长公共子序列

  • 思路:

    • 画网格
H O S H
F
I
S
H
    • 填充表格
H O S H
F 1 1 1 1
I 1 1 1 1
S 1 1 2 2
H 1 1 2 3

如果两个字母不同,就选择上方和左邻居中较大的那个
如果两个字母相同,就将当前单元格的值设为左上方单元格的值加1

1
2
3
4
if word_a[i] == word_b[j]:  # 两个字母相同
cell[i][j] = cell[i-1][j-1] + 1
else: # 两个字母不同
cell[i][j] = max(cell[i-1][j], cell[i][j-1])
Donate comment here