⌈贪心算法⌋田忌赛马策略
田忌赛马
齐使者如梁，孙膑以刑徒阴见，说齐使。齐使以为奇，窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远，马有上、中、下、辈。于是孙子谓田忌曰：“君弟重射，臣能令君胜。”田忌信然之，与王及诸公子逐射千金。及临质，“孙子曰：‘今以君之下驷与彼上驷，取君上驷与彼中驷，取君中驷与彼下驷。’既驰三辈毕，而田忌一不胜而再胜，卒得王千金。”
思考一个问题： 田忌和齐威王有相同数量的马，他们要在一场比赛中决出胜负，规则是：每匹马只能和对手比赛一次，胜者得一分，负者得零分，最后得分高的一方获胜。田忌和齐威王都是聪明的人，他们都会采用最优策略，田忌想要赢得齐威王的千金，那么田忌应该怎么安排马匹的顺序呢？
贪心算法
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
「字典序」问题—贪心+单调栈
问题：
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是 0。
一个思路是：
从左到右遍历
对于每一个遍历到的元素，我们决定是丢弃还是保留
问题的关键是：我们怎么知道，一个元素是应该保留还是丢弃呢？
这里有一个前置知识：对于两个数 123a456 和 123b456，如果 a > b， 那么数字 123a456 大于 数字 123b456，否则数字 123a456 小于等于数字 123b456。也就说，两个相同位数的数字大小关系取决于第一个不同的数的大小。
「LRUCache算法」—双向链表
「栈模拟迭代」—递归算法优化
模拟系统执行「递归」的过程
具体应用：
给定一个 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);
}
}
}
「图论」拓扑排序算法——Kahn算法和DFS算法
区间dp算法
688. 骑士在棋盘上的概率
象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
骑士继续移动，直到它走了 k 步或离开了棋盘。
蓄水池抽样算法
「蓄水池抽样算法」
优势：只需一次遍历，适用总量未知的情况
蓄水池抽样算法可以扩展很多应用范围，比如游戏的签到抽奖系统，在抽奖之前，你不知道参与的总人数。
对于一个池内，获取每个数字的概率都是一样的
- 如果我们池子中只有一个数字，那么拿到第一个数字的概率就是100%毋庸置疑。
- 两个数字50% 三个数字每个数字的几率都是33% 以此类推。。。。
当我们不知道池子里有多少个数字的时候，就需要用蓄水池的算法思想去计算。
- 当链表前行到第一个数字，此时取第一个数字的几率为100%，那result自然等于这个数字。
- 前进到第二个数字，那么此时取这个数字的几率自然就为50%（池子里只有两个数字），那么就是50%的几率取新数字，50%的几率保留原本的数字。
- 第三个数字的时候，33%的几率取当前最新的这个数字，66%的几率保留原本的数字。这66%中：原本的数字有50%的几率是1，有50%的几率是2。也就是此时三个数字的概率都为33%。 通过这个算法，就能达到取数的概率均摊，从而实现随机。
1 / 4