模拟系统执行「递归」的过程
具体应用:
给定一个 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);
}
}
}
象棋骑士有8种可能的走法,如下图所示。每次移动在基本方向上是两个单元格,然后在正交方向上是一个单元格。
每次骑士要移动时,它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘),然后移动到那里。
骑士继续移动,直到它走了 k
步或离开了棋盘。
优势:只需一次遍历,适用总量未知的情况
蓄水池抽样算法可以扩展很多应用范围,比如游戏的签到抽奖系统,在抽奖之前,你不知道参与的总人数。
对于一个池内,获取每个数字的概率都是一样的
- 如果我们池子中只有一个数字,那么拿到第一个数字的概率就是100%毋庸置疑。
- 两个数字50% 三个数字每个数字的几率都是33% 以此类推。。。。
当我们不知道池子里有多少个数字的时候,就需要用蓄水池的算法思想去计算。
- 当链表前行到第一个数字,此时取第一个数字的几率为100%,那result自然等于这个数字。
- 前进到第二个数字,那么此时取这个数字的几率自然就为50%(池子里只有两个数字),那么就是50%的几率取新数字,50%的几率保留原本的数字。
- 第三个数字的时候,33%的几率取当前最新的这个数字,66%的几率保留原本的数字。这66%中:原本的数字有50%的几率是1,有50%的几率是2。也就是此时三个数字的概率都为33%。 通过这个算法,就能达到取数的概率均摊,从而实现随机。