阅读《算法图解》一书的一些笔记记录。
选择排序：
def findSmallest(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 selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
递归
1.调用自己的函数
2.条件： 基线（退出）条件＋递归条件
栈：
1.两种操作： 压入和弹出
2.所有函数调用都是调用栈
3.后进先出LIFO。
快排
1.使用分而治之策略
def quicksort(array):
if len(array) < 2:
return array //基线条件
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
二分查找：
def binary_search(list, item):
low = 0
high = len(list)—1
while low <= high:
mid = (low + high)/2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
各算法大O运行时间对比如图：
分而治之（D&C）问题解决问题的两个步骤：
1.找出基线条件，此条件尽可能简单
2.不断分解问题，知道满足基线条件
备注：
1.D&C不是解决问题的办法，而是解决问题的思路。
2.D&C处理列表时，基线条件很可能是空列表或者只包含一个元素。
散列表：
1.处理冲突的方式的简单办法，如果两个键映射到同一个位置，可在该位置存储一个链表。
2.目的是要将键均匀的映射到散列表的不同位置处。
3.避免冲突：
3.1.较低的填装因子
填装因子＝散列表保护元素数／位置总数，度量散列表中多少位置是空的。填装因子月底，冲突可能性越小，散列表性能越高。经验：一旦填装因子大于0.7，就调整散列表长度。
3.2.良好的散列函数
4.可用来表示图关系。
广度优先搜索BFS：
1.找到两件东西的最短距离
2.解决最短路径的算法被称为广度优先搜索
3.运行时间：O（人数＋边数），通常为O（V+E），V为顶点数，E为边数。
4.广度优先搜索指出是否有A到B的最短路径。
5.你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径。因此搜索列表必须是队列。
6.对于检查过的人，不需要再检查，否则会造成无限循环。
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = [] //标记检查过的人
while search_queue:
person = search_queue.popleft()
if person not in searched://仅当这个人没检查过才检查
if person_is_seller(person):
print person + " is a mango seller!"
return True
else:
search_queue += graph[person]
searched.append(person）//将这个人标记检查过
return False
队列
1.先进先出，FIFO，按添加顺序进行检查
2.
图：
1.有向图：关系是单向的
2.无向图，直接相连的节点，无箭头。
拓扑排序：
1.列表中任务A必须在任务B后面，这成为拓扑排序。
2.使用它可根据图创建一个有序列表。
3.比如起床－》刷牙－》吃早饭－》上班
迪杰斯塔拉算法
1.起点到终点的耗时最短路径
2.加权图：带权重的图
3.计算非加权图的最短路径是广度优先搜索，计算加权图的最短路径是迪杰特斯拉算法
4：只适合有向无环图（DAG）
5.不适用于负权边的图。
6.负权边的图，找出最短路径使用：贝尔曼－福德算法。
7.四步骤：
7.1.找到最便宜的节点
7.2.对于该节点的邻居，检查是否有通往他们的更短路径，如果有，更新其开销
7.3.重复这个过程，直到所有节点都这样做了
7.4.计算最终路径
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):
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
贪婪算法
1.每步都采取最优的做法，即每步都选择局部最优解，最终得到全局最优解。
2.旅行商和集合覆盖问题共同点：都需要计算所有解，并从中选出最小／最短的那个，这两个问题都属于NP完全问题
3.如何判断是不是NP完全问题：
1.设计所有组合问题都是NP完全问题。
2.不能将问题分成小问题，需要考虑各种可能情况，这可能是NP完全问题。
3.问题涉及序列，（旅行商问题中城市序列）且难以解决，可能是NP完全问题。
4.问题涉及集合（广播台集合），且难以解决，可能是NP完全问题。
5.问题可转为旅行商问题或者集覆盖问题，肯定是NP完全问题。
4.面临NP完全问题，最佳做法是使用近似算法。
5.贪婪算法易于实现，速度快，是不错的近似算法。
动态规划：
1.每个单元格都包含当前可装入背包的所有商品。
2.最长公共字串：
if word_a[i] == word_b[j]://两个字母相同
cell[i][j] = cell[i－1][j－1] ＋1
else: //两个字母不同
cell[i][j] = 0
3.最长公共子序列：
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])
4.动态规划应用： 最长公共子序列确认DNA链的相似性，从而判断疾病相似性；git diff命令，指出两个文件差异，使用动态规划来实现的。编辑距离指出两个字符串的相似程度。
5.使用场景：
5.1给定约束条件下优化某种指标：动态规划很有用。
5.2问题可分解为离散子问题，可使用动态规划来解决。
二叉查找树：
1.查找，插入，删除时间O（logn）
傅立叶变换：
1.给定歌曲，将其中各种频率分离出来。
布隆过滤器：
1.一种概率型数据结构，提供的答案可能不对，可能正确
2.判断网页是否收集，可不使用散列表，使用布隆过滤器。
3.两个特点： 可能出现错报情况，说收集了，可能没收集；不可能出现漏报情况，说没收集，肯定没收集。
4.优点：占用存储空间少，
5.使用散列表需要存储所有搜集的url。使用布隆过滤器不需要都存储。
6.适合于不要求答案绝对正确的情况。
7.比如，对于某个网站，这样说完全可行：我们认为这个网站可能是恶意的，请小心。
8.面临海量数据，且要求答案八九不离十使用，可使用概率性算法。
SHA散列函数：
1.安全散列算法函数。给定一个字符串，返回一个字符串。
2.在比较超大型文件时候，可用来比较两个文件是否相同。
3.重要特性： 局部不敏感。即你修改其中一个字符，散列值截然不同。攻击者无法比较散列值来破解密码。
4.希望散列函数是局部敏感的，可是有simhash函数。对字符串的细微更改，simhash的散列值也会有细微的差别。可通过此比较散列值来比较两个字符串的相似程度。
5.google提供simhash判断网页是否已搜集
6.老师根据simhash来判断学生作业是否从网上抄袭的。
7.需要检查两项内容相似程度，simhash很有用。
