分类标签归档：读书笔记
https://en.wikipedia.org/wiki/Dynamic_programming
https://zh.wikipedia.org/wiki/动态规划
function DP():
dp = [][] # 二维情况
for i = 0 left, right = 0, len(array) -1
while left <= right:
mid = (left+right)/2
if array[mid] == target:
# find the target
break or return result
elif array[mid] < target:
left = mid + 1 # 左右下界为整型需要加一减一，左右下界如一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。
优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。https://www.cnblogs.com/cpselvis/p/6265825.html https://blog.csdn.net/tianyaleix
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致
结果是全剧最好或最优的算法
贪心算法与动态规划的不同在于他对每个字问题的解决方案都做出选择，不能回退。动态规划则会
保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能
贪心算法可以解决工程中一些最优化问题， 如: 求图中的最小生成树、求哈夫曼编码等。然而对于 工程和生活中的问题，贪心法一般不能得到我们所要求的答案
一旦一个问题可以通过贪心法来解决。那么贪心法一般是解决这个问题的最好办法。 由于贪心法的搞笑性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者
def divide_conquer(problem, param1, param2, ...):
# recursion terminator
if problem is None:
print_result
return
# prepare data
data = prepare_data(problem)
subproblems = split_problem(problem, data)
# conquer subproblems
subresult1 = self.divide_conquer(subproblems[0], 启发式函数: h(n)，它用来评价哪些结点最有希望的是一个我们要找的结 点，h(n) 会返回一个非负实数,也可以认为是从结点n的目标结点路径的估 计成本。 启发式函数是一种告知搜索方向的方法。它提供了一种明智的方法来猜测 哪个邻居结点会导向一个目标。
https://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/
def AstartSearch(graph, start, end):
pq = visited = set()
def dfs(node, visited):
# 1. terminator
if node in visited:
return
visited.add(node)
# process_current_logic
...
for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
def dfs(self, root):
if not ro并查集(union & find) 是一种树形结构，用于处理一些不交集(Disjoint Sets) 的合并及查询问题
Find: 确定元素属于哪一个子集。他可以被用来确定两个元素是否属于同一个子集。
Union: 将两个子集合合并成同一个集合
字典树，即 Trie 树，又称单词 查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。 它的优点是:最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie 树的核心思想是空间换时间。 利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
static