模拟系统执行「递归」的过程

具体应用：

给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。

递归做法:

class DFS{
    public List<Integer> preorder(Node root){
        List<Integer> res = new ArrayList<>();
        dfs(root,res);
        return res;
    }

    public void dfs(Node root,List<Integer> res){
        if(null == root) return;
        //前序遍历位置
        res.add(root.val);
        List<Node> children = root.children;
        for(Node child: children){
            dfs(child,res);
        }
    }
}

直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。

图片" style="zoom:50%;

对于任何有向图而言，其拓扑排序为其所有结点的一个线性排序（对于同一个有向图而言可能存在多个这样的结点排序）。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。

拓扑排序可以用来判断图中是否有环， 还可以用来判断图是否是一条链。

算法思路

688. 骑士在棋盘上的概率

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

「蓄水池抽样算法」

优势：只需一次遍历，适用总量未知的情况

蓄水池抽样算法可以扩展很多应用范围，比如游戏的签到抽奖系统，在抽奖之前，你不知道参与的总人数。

对于一个池内，获取每个数字的概率都是一样的

• 如果我们池子中只有一个数字，那么拿到第一个数字的概率就是100%毋庸置疑。
• 两个数字50% 三个数字每个数字的几率都是33% 以此类推。。。。

当我们不知道池子里有多少个数字的时候，就需要用蓄水池的算法思想去计算。

• 当链表前行到第一个数字，此时取第一个数字的几率为100%，那result自然等于这个数字。
• 前进到第二个数字，那么此时取这个数字的几率自然就为50%（池子里只有两个数字），那么就是50%的几率取新数字，50%的几率保留原本的数字。
• 第三个数字的时候，33%的几率取当前最新的这个数字，66%的几率保留原本的数字。这66%中：原本的数字有50%的几率是1，有50%的几率是2。也就是此时三个数字的概率都为33%。 通过这个算法，就能达到取数的概率均摊，从而实现随机。

「优先队列」

应用场景：从序列中找一个最值（最大值或最小值），如果顺序寻找最值需要O(n)的时间，而使用优先队列则只需要O(logn)的时间。

普通的队列是一种先进先出的数据结构，元素在队尾入，在队头出。

在优先队列中。元素被赋予了优先级，具有最高优先级的元素先出。

优先队列是利用堆来实现的，堆可以看作是一棵完全二叉树的循序存储结构，具有n个节点的完全二叉树的深度为（logn）+1

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。

prefix[i]就代表着nums[0..i-1]所有元素的累加和，如果我们想求区间nums[i..j]的累加和，只要计算prefix[j+1] - prefix[i]即可，而不需要遍历整个区间求和。

「差分数组」

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减

对nums数组构造一个diff差分数组，diff[i]就是nums[i]和nums[i-1]之差：