⌈贪心算法⌋田忌赛马策略

田忌赛马

齐使者如梁,孙膑以刑徒阴见,说齐使。齐使以为奇,窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远,马有上、中、下、辈。于是孙子谓田忌曰:“君弟重射,臣能令君胜。”田忌信然之,与王及诸公子逐射千金。及临质,“孙子曰:‘今以君之下驷与彼上驷,取君上驷与彼中驷,取君中驷与彼下驷。’既驰三辈毕,而田忌一不胜而再胜,卒得王千金。”

思考一个问题: 田忌和齐威王有相同数量的马,他们要在一场比赛中决出胜负,规则是:每匹马只能和对手比赛一次,胜者得一分,负者得零分,最后得分高的一方获胜。田忌和齐威王都是聪明的人,他们都会采用最优策略,田忌想要赢得齐威王的千金,那么田忌应该怎么安排马匹的顺序呢?

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

超高精度计算

高精算法解决了什么问题?

在利用计算机作数值计算的时候,有时候会遇到这样的问题:

希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度。

所以,往往在处理对超大精度计算时,都会通过巧妙的算法设计实现。

本算法使用字符串实现,防止数据溢出。

最小生成树

最小生成树

定义

最小生成树(Minimum Spanning Tree,MST)是一个连通图的极小连通子图,它包含图中所有顶点,且所有边的权值之和最小。

即用最小的边连接所有的顶点,使得图连通。
符合一下两个条件:

  1. 覆盖所有的顶点
  2. 边的权值之和最小

Kruskal 算法

「字典序」问题—贪心+单调栈

问题:


给定一个以字符串表示的非负整数  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算法」—双向链表

当不得不淘汰某些数据时(通常是容量已满),选择最久未被使用的数据进行淘汰。 class LRUCache { class Node { int k, v; Node l, r; Node(int _k, int _v) { k = _k; v = _v; ...

「栈模拟迭代」—递归算法优化

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

具体应用:

给定一个 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算法

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

图片
图片" style="zoom:50%;

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

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

算法思路

区间dp算法

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