毕业总结

• 哈希表也称为散列表，通过散列函数将关键码映射到表中的一个位置，从而加快查询速度。
• LinkedList是特殊化的Tree，Tree是特殊化的Map。
• 二叉树的遍历方式包括：前序遍历、中序遍历、后序遍历。
• 二叉搜索树是针对每一个节点，其左子树上的全部节点小于根节点，右子树上的全部节点大于根节点。
• 递归是通过函数体进行的循环，注意三点：不要人肉递归、找重复子问题、数学归纳法。
• 分治是指split、merge子问题。回溯是指通过试错的思想分步解决问题。

深度优先搜索、广度优先搜索的实现和特性

搜索：本质上就是简单朴素搜索，它做的事情就是把所有的节点遍历一遍，找到你要的结果即可。同时保证每个节点访问一次且仅访问一次。
根据节点的访问顺序不同可以对搜索方式进行分类：

• 深度优先搜索（depth first search）
• 广度优先搜索（breadth first search）
  当然也有其他的优先级搜索等方式，具体的优先级搜索方式可以根据业务来确定。

深度优先搜索示例代码

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    dfs(node.left)
    dfs(node.right)

深度优先搜索本质上就是递归，分为三个部分：

• 终止条件：如果这个节点已经访问过了，就终止
• 当前层逻辑：将节点加入访问集合中
• 下转：进入当前节点的子节点

多叉树示例代码

visited = Set()
def dfs(node, visited):
    visited.add(node)
    for next_node in node.children():
        if not next_node in visited:
            dfs(next_node, visited)

与一般的深度优先代码相比，只是多了一个获取全部子节点的步骤。

DFS非递归写法

def DFS (self, tree):
    if tree.root is None:
        return[]
    visited, stack = [], [tree.root]
    while stack:
        node = stack.pop()
        visited.add(node)
        process(node)
        nodes = generate_related_nodes(node)
        stack.push(nodes)

DFS非递归的写法本质上是利用栈来模拟递归，当Stack不为空时，Pop出节点，再push相关的节点到栈里面。

BFS代码写法

def BFS(graph, start ,end):
    queue = []
    queue.append([start])
    visited.add(start)
    while queue:
        node = queue.pop()
        visited.add(node)
        process(node)
        nodes = generates_releated_nodes(node)
        queue.push(nodes)

贪心算法

贪心算法时一种在每一步选择中都采取当下状态下最好或者最优的选择，从而希望导致结果时全局最好或者最优的算法。
贪心算法与动态规划不同的点在于，它对每一个子问题的解决方案都做出选择，不能回退，动态规划则会保存以前的运算结果，并且根据以前的结果对当前进行选择，有回退的功能。
贪心法可以解决一些最优化问题，比如：求图中的最小生成树，求哈夫曼编码等，然而对于工程和生活中的问题，贪心算法一般不能得到理想的结果。但如果一个问题被证明可以使用贪心法求解，那么一般而言，贪心法就是这个问题效率最高的一种解法。由于贪心法的高效性，我们有时也会将其用作辅助算法或者求解一些对精度要求不高的问题。

二叉查找法

二叉查找法有三个前提：

• 目标函数的单调性（单调递增或者单调递减）
• 存在上下界（bounded）
• 能够通过索引访问（index accessible）

代码模版

left, right = 0 , Len(array)-1
while(left <= right)
    mid = (left + right)/2
    if array[mid] == target
        break or return result
    elif array[mid]<target
        left = mid + 1
    else:
        right = mid - 1

DP三个关键点：

1、DP和递归或者分治没有本质上的区别。
2、它们的共性都是找到重复子问题。
3、差异性：DP问题具有最优子结构，在计算的中途必须淘汰次优解。
从没有意义上来说，分治也可以当作是动态规划，每一次的最优解就是当前解，没有淘汰机制

递归 + 记忆化搜索

记忆化搜索的本质就是另外使用数组结构来保存递归过程中产生的结果，从而避免重复计算以及淘汰次优解，这是一种自顶向下的思路。但是在实际的算法训练过程中，通过递归分治的思路来初步解析题目，然后必须找到递推公式（也就是DP方程），然后采用自底向上循环递推的方式来实现DP。

动态规划解题三步骤

1、找重复性，分解子问题，找最优子结构
2、定义状态数组，明确数组元素的定义
3、找到DP递推公式

字典树、并查集

• 字典树
  1、字典树的结点本身并不保存完整的单词
  从根节点到某一个结点，路径上经过的字符连接起来，成为该结点对应的字符串。每个结点所有的子结点路径代表的字符都不相同。
  结点也可以存储额外的信息，比如频次等。当然你也可以存储别等信息，视情况而定。
  2、结点内部的实现
  很多时候我们可以将其视为26分叉的多叉树，当然也可能区分大小写、甚至ASII码，这样就是255分叉。但是通常情况下是26分叉。所以字典树的空间消耗比较大。
  字典树的核心是空间换时间，利用字符串的公共前缀来降低查询时间的开销。所以字典树非常适合解决以前缀来推测候选词的问题。故而在搜索引擎相关领域，字典树被大量的应用。

• 并查集
  并查集输入跳跃式的数据结构，并没有太多自我发挥的空间，碰到类似组团、配对等问题时，都可以考虑套用并查集的模版。其基本操作包括以下：
  1、makeSet(s)：新建一个并查集，期中包含s个元素集合。
  2、unionSet(s)：把元素x和元素y所在的集合进行合并，要求x和y所在的集合不能相交，如果相交则不合并。
  3、find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否属于同一个集合，只要将它们各自的代表比较一下就可以。

高级搜索

包括剪枝、双向BFS、启发式搜索。

高级树

包括AVL的概念以及红黑树。

位运算

按位或、按位与、按位取反、按位异或

布隆过滤器

如果元素没有查到，则一定不存在。如果元素查到了，则可能存在。在Redis缓存、分布式服务中经常使用布隆过滤器。

排序算法

1、比较类排序：由于其时间复杂度不能突破O(nlogn)，因此也成为非线性时间比较类排序。
2、非比较类排序：可以突破比较类排序的时间下界，以线性时间运行。