【算法】007_前缀树和贪心算法

news/发布时间2024/7/15 3:23:51

1. 前缀树

一个字符串类型的数组arr1,另一个字符串类型的数组arr2.arr2中有哪些字符,是arr1中出现的?arr2中有哪些字符是作为arr1中某个字符串前缀出现的?arr2中有哪些字符是作为arr1中某个字符串前缀出现的?

image-20240216122039031

  • pass:表示当前这个结点被经过的次数

  • end:这个结点作为结尾的次数

  • 例如将abc转换为前缀树:

    • 初始p=e=0,当要插入a的时候p=1,表示到达a要经过根结点

      image-20240216122252953

    • 插入a,a的p++

      image-20240216122518163

    • 插入b,b的p++

      image-20240216122614125

    • 插入c

      image-20240216122629657

    • c是最后一个点,修改c的e=1

      image-20240216122812252

  • 插入ab

    • 来到头结点,p变成2

    • 有走向a的路,所以a的p=2

    • 有走向b的路,所以b的p=2

    • b就结尾了,所以b结点的e=1

      image-20240216123014422

  • 当查找ab字符串时

    • 有走向a的路
    • 有走向b的路
    • b的end=1,说明b已经结束了,找到了ab
    • 如果b的end=0,说明没有以b作为结尾的字符串,找不到ab
public class Code01_TrieTree {public class TrieNode{public int pass;//经过了这个结点pass+1public int end;//以这个结点结尾end+1public TrieNode[] nexts;public TrieNode() {pass = 0;end = 0;//nexts[0] == null   没有走向a的路//nexts[0] != null   有走向a的路nexts = new TrieNode[26];}}public class Trie{private TrieNode root;//根结点public Trie(){root = new TrieNode();}public void insert(String word){if (word == null){return;}char[] chs = word.toCharArray();TrieNode node = root;//node从根结点开始node.pass++;//经过了根结点int index = 0;for (int i = 0; i < chs.length; i++) {//从左往右遍历字符index = chs[i] - 'a';//由字符对应走向哪条路if (node.nexts[index] == null){//当前的树上没有这个结点node.nexts[index] = new TrieNode();//新建}node = node.nexts[index];//有这个结点的话就直接到这个结点node.pass++;//经过这个结点}node.end++;//结尾}public void delete(String word){//确定树中确实加入过word,才删除if (search(word) == 0){return;}char[] chs = word.toCharArray();TrieNode node = root;node.pass--;int index = 0;for (int i = 0; i < chs.length; i++) {// index = chs[i] - 'a';// node = node.nexts[index];// node.pass--;// //删除了字符之后node的pass为0,说明没有经过node的路径,就该把node从前缀树中删除。之前插入的时候,有经过结点的路径,才会创建结点// if (node.pass == 0){//     node = null;//     return;// }index = chs[i] - 'a';if (--node.nexts[index].pass == 0){node.nexts[index] = null;//这里为null了之后,node之后的结点也会被释放,即使后面还有p!=0的结点,只是还没循环到,循环到了之后p依然会变成0,可以自己画图理解return;//后面的结点都会被释放,所以返回即可}node = node.nexts[index];}node.end--;}//word这个单词之前加入过几次public int search(String word){if (word == null){return 0;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';//word的字符还没有比较完,但是前缀树已经没有路了,说明word没有被加入过前缀树if (node.nexts[index] == null){return 0;}node = node.nexts[index];}return node.end;//node被作为结尾的次数,就说明这个字符串有几个}//所有加入的字符串中,有几个是以pre这个字符串作为前缀的public int prefixNumber(String pre){if (pre == null){return 0;}char[] chs = pre.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';//pre中的字符,没有出现在路径中if (node.nexts[index] == null){return 0;}node = node.nexts[index];}return node.pass;//node被路过的次数}}
}

2. 贪心算法

题目一

一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。给你每一个项目的开始时间和结束时间,你来安排宣讲的日程,要求会议室进行的宣讲的场次最多,返回这个最多的宣讲场次。

  • 按照结束时间从早到晚进行排序

  • 按排序好的顺序进行遍历

  • 如果遍历到的会议开始时间没有早于当前时间点,就可以安排这个会议

    • 第一个被安排的会议是①,①最早结束

    • 第二个被安排的会议是⑤,因为①结束之后,⑤是最早开始的

    • 第三个被安排的会议是Ⅵ,因为⑤结束之后,⑥是最早开始的

image-20240216151453713

题目二

给定一个字符串类型的数组strs,找到一种拼接方式,使得把所有字符串拼起来之后形成的字符串具有最小的字典序。

  • 通常想到的思路是,将字符串找到字典序排序,但是如果遇到ba和b:

    按字典序排序:b,ba,拼接之后就会得到bba。但正确答案应该是bab。所以这种方式不对

  • 正确的是,两两字符串拼接之后比较字典序

    证明听不懂,算了,不为难自己

public class Code03_LowestLexicography {public class MyComparator implements Comparator<String>{@Overridepublic int compare(String o1, String o2) {return (o1 + o2).compareTo(o2 + o1);}}public String lowestString(String[] strs){if (strs == null || strs.length == 0){return "";}Arrays.sort(strs, new MyComparator());String res = "";for (int i = 0; i < strs.length; i++) {res += strs[i];}return res;}
}

题目三

一块金条切成两半,是需要花费和长度数值一样的铜板的。比如长度为20的金条,不管切成长度多大的两半,都需要花费20个铜板。

一群人想整分整块金条,怎么分最省铜板。

image-20240218110145177

  • 60先分成30和30,花费60
  • 再把30分成10和20,花费30
  • 哈夫曼编码,从底部向上
public class Code04_LessMoneySplitGold {public static void main(String[] args) {int[] arr = {2,3,4,7,9,2};Code04_LessMoneySplitGold mon = new Code04_LessMoneySplitGold();System.out.println(mon.lessMoney(arr));}public int lessMoney(int[] arr){PriorityQueue<Integer> queue = new PriorityQueue<>(new MinHeapComparator());for (int i = 0; i < arr.length; i++) {queue.add(arr[i]);}int sum = 0;int cur = 0;while (queue.size() > 1){cur = queue.poll() + queue.poll();sum += cur;//加的是中间结点,没有加叶子结点queue.add(cur);}return sum;}public class MinHeapComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o1- o2;}}
}

题目四

输入:

正数数组costs,正数数组profits,正数k,正数m

含义:

costs[i]表示i号项目的花费

profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)

k表示你只能串行的最多做k个项目

m表示你初始的资金

说明:你每做完一个项目,马上获得的收益,可以支持你去做下一个项目

输出:你最后获得的最大钱数

假设m=1,k=4

image-20240218111345345

由于初始资金为1,所以只能先做第二个项目。做完之后资金变为3。

做第一个项目,资金变为4

做第三个项目,资金变为7

之后的项目都做不了,资金不够。

  • 小根堆,按照花费从小到大进行排序

  • 将花费小于等于资金的项目弹出,进入大根堆

  • 从大根堆中弹出一个项目,这就是要做的项目

  • 更新资金,继续将小根堆中花费小于等于资金的项目弹出,进入大根堆

  • 这样操作的结果就是,每次做的项目都是花费小于等于资金的所有项目中选择一个利润最高的项目

public class Code05_IPO {public class Node{public int profit;public int cost;public Node(int profit, int cost){this.profit = profit;this.cost = cost;}}public class MinCostComparator implements Comparator<Node>{@Overridepublic int compare(Node o1, Node o2) {return o1.cost - o2.cost;}}public class MaxProfitComparator implements Comparator<Node>{@Overridepublic int compare(Node o1, Node o2) {return o2.profit - o1.profit;}}public int findMaximizedCapital(int k, int m, int[] Profits, int[] Costs){PriorityQueue<Node> minQueue = new PriorityQueue<>(new MinCostComparator());PriorityQueue<Node> maxQueue = new PriorityQueue<>(new MaxProfitComparator());//按照花费从小到大进入小根堆for (int i = 0; i < Profits.length; i++) {minQueue.add(new Node(Profits[i], Costs[i])); }//最多做k个项目for (int i = 0; i < k; i++) {//将花费小于等于资金的项目弹出到大根堆中while (!minQueue.isEmpty() && minQueue.peek().profit <= m){maxQueue.add(minQueue.poll());}//大根堆为空,说明当前资金已经不够做项目了if (maxQueue.isEmpty()){return m;}m += maxQueue.poll().profit;}return m;}
}

题目五

一个数据流中,随时可以取得中位数

  • 一个大根堆和一个小根堆
  • 第一个数字进入大根堆
  • 后来的数字,判断是否小于等于大根堆的堆顶
    • 是,则进入大根堆
    • 否,则进入小根堆
    • 小根堆中的元素总是大于大根堆中的元素,于是两个堆顶的元素就是大小相邻的元素
  • 比较大根堆和小根堆的大小,如果差值大于1,就将多的堆弹出一个元素到少的堆
  • 最后,最小的一半数在大根堆中,最大的一半数在小根堆中。
public class Code06_MedianQuick {public static class MedianHolder{private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());public Integer getMedian(){int maxHeapSize = this.maxHeap.size();int minHeapSize = this.minHeap.size();Integer maxHeapHead = this.maxHeap.peek();Integer minHeapHead = this.minHeap.peek();//数字一共是偶数个,中位数是中间两个数的平均数if (maxHeapSize == minHeapSize){return (maxHeapHead + minHeapHead) / 2;}//奇数个数字,中位数是多出的那一个return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;}public void addNumber(int num){//第一个数字进入大根堆if (maxHeap.isEmpty()){maxHeap.add(num);}if (num <= maxHeap.peek()){maxHeap.add(num);}else {minHeap.add(num);}modifyTwoHeapsSize();}private void modifyTwoHeapsSize(){if (this.minHeap.size() - this.maxHeap.size() == 2){maxHeap.add(minHeap.poll());}if (this.maxHeap.size() - this.minHeap.size() == 2){minHeap.add(maxHeap.poll());}}}public static class MaxHeapComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {if (o2 > o1) {return 1;} else {return -1;}}}public static class MinHeapComparator implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {if (o2 < o1) {return 1;} else {return -1;}}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.jwkm.cn/p/23320664.html

如若内容造成侵权/违法违规/事实不符,请联系宁远站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

Linux清理buff/cache

使用以下命令清理 # sudo sync && echo 3 | sudo tee /proc/sys/vm/drop_caches清理前后对比

物理隔离环境下 如何实现数据安全导入导出?

数据安全导入导出是指在确保数据安全的前提下,将文件从一个系统或网络环境传输到另一个系统或网络环境的过程。一般情况下,都是物理隔离的环境,而且是单向的数据导入导出。我们以数据导出为例,要实现这种物理隔离环境下的数据安全导出,比较传统的方式就是用户将文件上传到…

读十堂极简人工智能课笔记05_无监督学习

无监督学习1. 自我改善 1.1. 只有学会了如何学习和改变的人,才称得上是受过教育的人 1.1.1. 卡尔罗杰斯 1.2. 人工智能如果只是学习纯理论的游戏(从国际象棋和围棋到电脑游戏),其结果已然可以令人惊叹 1.3. 让大多数机器人玩叠叠乐游戏(用积木搭成塔,慢慢从塔中抽出积木,…

汽车传感器类型图例

汽车传感器类型图例 在某种程度上,车辆传感器是车辆的感觉器官。作为电子管理系统的基本组成部分,它们必须记录物理或化学变量,并将其转换为电信号… 近年来,不同类型的传感器数量激增。在安全和方便的物理科学领域,人们特别看到了许多新型的传感元件。 从本质上讲,传感器…

ucontext库

目录ucontext接触ucontext到底是什么 ucontext接触 利用ucontext提供的四个函数 getcontext(),setcontext(),makecontext(),swapcontext() 可以在一个进程中实现用户级的线程切换。 #include <unistd.h> #include <ucontext.h> #include <stdio.h>int main()…

免费的虚拟主机还不错

免费的虚拟主机和免费云服务器还不错的阿贝云 https://www.abeiyun.com,