算法总结 | Yuan Tian's Blog

往期文章

二分法

使用情况：
① 能分成OOXX两部分
② 无法找到一个条件，形成OOXX模型。但是可以根据判断，保留下有解的那一半或者去掉无解的一半
③ 二分答案（假设答案的取值范围为[a,b]，用二分法缩小[a,b]）

二分法的本质：扔一半留一半

双指针

相向双指针

reverse类
- 三步翻转法
- 回文串
two sum类
partition类
- 快速选择算法
- 平均时间复杂度O(n)，最坏时间复杂度O(n^2)

同向双指针

数组去重问题
滑动窗口问题
- 维护滑动窗口的最大/小值：单调队列（维护最小值：非严格单调递增队列；维护最大值：非严格单调递减队列）
两数之差问题
链表中点问题
带环链表问题

快速排序

① 平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)
② 空间复杂度O(1)，是原地排序
③不稳定

用到了分治的思想
先整体有序，再局部有序

归并排序

① 时间复杂度最好最坏都是O(nlogn)
② 空间复杂度O(n)
③ 稳定

用到了分治的思想
先局部有序，再整体有序

计数排序

是有范围的数字的排序的最好方法
时间复杂度 O(n)

BFS

使用场景

图（包括树）的遍历
- 层级遍历
- 由点及面
- 拓扑排序
  - ①首先统计每个结点的入度，存在node2indegree里
  - ②BFS，把node2indegree[node]==0的点入队
简单图（边长都是1、或者边长相等的图）中的最短路径
- 最短路径
  - 简单图：BFS
  - 复杂图：Dijkstra
- 最长路径
  - 图可以分层：DP
  - 图不可以分层：DFS

二叉树的BFS vs. 图的BFS

树的BFS不需要保存已经访问过的节点（丢进过 queue 里的节点）。因为树中没有环，不可能出现一个节点的儿子的儿子是自己的情况。但是在图中，一个节点的邻居的邻居就可能是自己。

BFS的优化

bidirectional BFS：从起点和终点同时开始BFS（代码和多源BFS差不多）

BFS时间复杂度

图：O(m+n)（m：边个数，n：点个数），m最坏是n^2
矩阵：O(R*C)（R行C列），R*C个点，R*C*2 条边(每个点上下左右4条边，每条边被2个点共享)

多源BFS

求所有点到最近起点的最短距离（将所有起点都放入队列）

DFS

Binary Tree & Tree-based DFS

分治法：先“分”，再“治”，最后“合”

递归三要素：

递归的定义：递归函数的参数和返回值
递归的拆解：一个大问题如何拆解为若干小问题去解决
递归的出口：什么时候可以直接知道答案，不用再拆解，直接return

题型：

二叉树上求值，求路径
二叉树结构变化
- 例如：flatten binary tree to linked list
二叉搜索树
- 中序遍历
  - 递归方法
  - 非递归方法（用stack）
  - 递归方法相当于是OS帮你存在stack中

非递归遍历二叉树（用stack）：

后序遍历为“左右根”，可以按“根右左”遍历（左右相反的前序遍历），然后reverse

Combination-based DFS

思路：

最好想的方法：把它当成一个二叉树：每一层代表一个元素选不选中
更通用的方法：回溯

时间复杂度：O(答案总数*构造每个答案的时间)
举例：Subsets问题，求所有的子集。子集个数一共 2^n，每个集合的平均长度是 O(n) 的，所以时间复杂度为 O(n * 2^n)，同理 Permutations 问题的时间复杂度为：O(n * n!)

DFS vs BFS:

求所有方案可以用BFS
对于排列组合类问题，深度最多就是n，n不会很大。所以用DFS做排列组合类问题，不用管Stack Overflow问题
对排列组合类问题，图的宽度一般比深度大，所以dfs消耗空间比bfs小

有重复情况：记忆化搜索

函数必须有返回值才能记忆化搜索
用一个dict把已经搜索过的情况的结果记录下来
写记忆化搜索的步骤
- ① 写不带记忆化搜索的DFS
- ② 改为答案以返回值的形式存在，而不是参数形式
- ③ 添加记忆化数组

Permutation-based DFS

与Combination-base DFS不同的是，Permutation-based DFS只能用回溯法

例题:

求全排列
N皇后

Graph-based DFS

Trie Tree

可以解决和字符串前缀相关的题

实现Trie的插入和查找可以用非递归和递归两种方法，涉及到模糊匹配时用递归比较方便

class Node:
    def __init__(self, val='0'):
        self.val = val
        self.children = dict()
        self.isword = False


class Trie:
    def __init__(self):
        self.head = Node()


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        if not word:
            return

        word_len = len(word)

        # search the prefix
        cur_node = self.head
        i = 0
        while i < word_len:
            c = word[i]

            if c not in cur_node.children.keys():
                break
            cur_node = cur_node.children[c]

            i += 1

        # insert the rest part
        while i < word_len:
            c = word[i]
            cur_node.children[c] = Node(c)
            cur_node = cur_node.children[c]
            i += 1
        
        # mark the word
        cur_node.isword = True


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        if not word:
            return True

        cur_node = self.head
        for c in word:
            if c not in cur_node.children.keys():
                return False
            cur_node = cur_node.children[c]
        
        if cur_node.isword:
            return True
        return False


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        if not prefix:
            return True

        cur_node = self.head
        for c in prefix:
            if c not in cur_node.children.keys():
                return False
            cur_node = cur_node.children[c]
        
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

并查集

支持两个操作:

检查两个节点是否在同一个集合（find）：平均时间复杂度O(1)
合并两个集合（union）：平均时间复杂度O(1)