当前位置：首页 > news >正文

左神算法基础巩固--5

news 2025/6/27 0:34:14

文章目录

前缀树
- 生成前缀树
- 查询前缀树
- - 查询字符串加入过几次
  - 查询所有加入的字符串中，有几个是以pre这个字符串作为前缀
- 删除前缀树中的某个字符串
贪心算法
- 解题

前缀树

在这里插入图片描述

生成前缀树

要想生成一棵前缀树，需要先创建一个根节点，这个根节点有26条分支对应26个字母、pass代表有多少个字符串经过，end代码有多少个字符串以这个节点为终止节点。
在想往这棵前缀树中添加字符串的话，先是将字符串分割为一个又一个字符，之后从根节点出发先判断树中存不存在已经创建的节点，如果存在便直接pass++，如果不存在便需要创建出来，再往下走。当字符串的所有节点都正确的存在与树中时，便在最后指向的节点出end++
在这里插入图片描述

在这里插入图片描述
在构建完这棵树后，树上的每个节点都代表着一些前缀信息，如：上图中的根节点下a分支下的节点，该节点的pass代表着以a为前缀的字符串的个数，其end代表着字符a的个数；上图中根节点下a分支下b分支的节点，该节点的pass代表着以ab为前缀的字符串的个数，其end代表着字符串ab的个数。

查询前缀树

查询字符串加入过几次

由前缀树每个节点的信息得知，查询字符串加入过几次可以由树中字符串最后一个字符对应节点的end得知
我们先将字符串分割为一个又一个字符，之后从根节点出发根据那些字符找到该字符的最后一个节点，并直接返回最后一个节点的end信息。
在这里插入图片描述

查询所有加入的字符串中，有几个是以pre这个字符串作为前缀

由前缀树每个节点的信息得知，查询字符串加入过几次可以由树中字符串最后一个字符对应节点的pass得知
我们先将字符串分割为一个又一个字符，之后从根节点出发根据那些字符找到该字符的最后一个节点，并直接返回最后一个节点的pass信息。
在这里插入图片描述

删除前缀树中的某个字符串

在删除前缀树中的某个字符串中时，首先需要判断树中是否存在，在确定存在后将字符串分割为字符，后根据字符找到字符所对应的各个节点，将每个节点的pass值均减一并判断当存在某个节点的pass值为0时将其下一个节点设为null，如果没有便在最后的节点的位置将end–
在这里插入图片描述

贪心算法

在这里插入图片描述

解题

在这里插入图片描述

在这里插入图片描述
在此题中，我们需要知道以宣讲的结束时间按从小到大排序并进行选择所能选择的宣讲的场次是最多的。这个的证明需要耗费很多的篇幅，因此便不在这里证明，感兴趣的可以自行去搜索了解

在这里插入图片描述
这道题的解法需要我们知道要想求得拼接后字典序最小，我们可以将两两拼接后得到的结果进行比较，当a在前b在后得到的字典序大于b在前a在后，那么我们便得到我们需要将b在前a在后这个局部最优解，之后我们再根据局部最优解便能得到全局最优解
在这里插入图片描述

在这里插入图片描述
这道题是典型的哈夫曼编码问题，可以使用哈夫曼编码解决这个问题，问题的证明请大家自行去看证明。
哈夫曼编码问题可以用小根堆解决，我们先用给定数组创建一个小根堆，每次从小根堆中取出两个数，之后将两数相加的结果记录下来加入到最后的代价中并将其相加后的结果重新投入到小根堆中，不断循环直到小根堆为空。
在这里插入图片描述

在这里插入图片描述
求解这道问题是我们可以使用一个小根堆和一个大根堆，小根堆负责存储按项目的花费存储，大根堆可以将当前资金能够满足的项目按收益存储起来。在求解这道问题时，我们先将所有项目存储到小根堆中，再进行k轮判断，将小根堆中所有能够满足条件的项目加入到大根堆中，之后再弹出大根堆中的项目，并用所弹出的项目的利润更新当前所有的资金数。