二分查找
1 | def binary_search(list, item): |
最短路径问题:使用广度优先搜索,使用图来建立问题模型
假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。
查找最短路径,广度优先搜索可回答两类问题
- 第一类问题:从节点A出发,有前往节点B的路径吗?(在你的人际关系网中,有芒果销 售商吗?)
- 第二类问题:从节点A出发,前往节点B的哪条路径最短?(哪个芒果销售商与你的关系 最近?)
1 | graph = {} |
1 | from collection import deque |
将一个人加入对列的时间是固定的O(1),总时间就为O(人数)。所以广度优先搜索的运行时间为O(人数+边数)
狄克斯特拉算法
- 问题:其中每个数字表示的都是时间,单位分钟。为找出从起点到终点耗时最短的路径,你将使用 狄克斯特拉算法。
1 | graph TD |
1 | graph = {} |
- 第一步:找出最便宜的节点
- 第二步:计算经起点的下一节点前往其各个节点所需的时间
- 第三步:重复
- 重复第一步:找出可在最短时间内前往的节点。你对节点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 | # 实现这个公式的伪代码 |
最长公共子序列之解决方案
最长公共子序列:两个单词都有的序列包含的字母数
问题:求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 | if word_a[i] == word_b[j]: # 两个字母相同 |