左神一周刷爆LeetCode 7 详解前缀树和贪心算法

系统管理员 2024-03-27 13:49 56阅读 0赞

#### 左神一周刷爆LeetCode ####

[【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解】][LeetCode_100_BTAJ]

![在这里插入图片描述][7a4b72b8a00d446c895c1fb97ec97dc6.png_pic_center]

#### 7 详解前缀树和贪心算法 ####

##### 7.1 介绍前缀树 #####

何为前缀树? 如何生成前缀树?

经典前缀树，点是放在路上的。没有路就新建，有就复用【点上是没有数据的】

![在这里插入图片描述][09783977004e44989c47fd52b17ad778.png_pic_center]

但是为了方便一些功能，使用前缀树时通常会将点上的信息变得丰富一点

点的数据结构Java代码描述：

public static class TrieNode {
        
       public int pass; // 在加前缀树时，该节点到达(通过)过多少次
       public int end; // 该节点是否是一个字符串的结尾节点，如果是，它是多少个字符串的结尾节点
       public TrieNode[] nexts; // 往下去的路
    
       public TrieNode() {
        
          pass = 0;
          end = 0;
          nexts = new TrieNode[26]; //假定一直都添加的是小写字母 【如果不是，我们可以把路换成哈希表或者有序表】
          // nexts[0] == null → 没有走向 'a' 的路
          // nexts[0] != null → 有走向 'a' 的路
          // ...
          // nexts[25] != null → 有走向 'z' 的路
       }
    }

*  查询某个字符串是否被加过【甚至加过多少次】 end值
 *  查询之前加入过的字符串，有多少个是以 “ab” 作为前缀的。 pass 值

前缀树的Java 结构实现代码：

public static 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 ++;  // 一上来pass 先++【根节点的p值其实是整个树中我们加入了多少个字符串】
          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++; // 当前 word 插入完毕，end ++
       }
    
       public void delete(String word) {
         // 删除某个word 【其实就跟着走，经过的节点的p值都--，走完了，最后一个节点的 e值--】
          if (search(word) != 0) {
         // 之前加入过，才能进行删除
             char[] chs = word.toCharArray();
             TrieNode node = root;
             int index = 0;
             for (int i = 0; i < chs.length; i++) {
        
                index = chs[i] - 'a';
                if (--node.nexts[index].pass == 0) {
        
                   node.nexts[index] = null; // 删着删着发现 p值为0了，这样后面的东西都不用要了，直接置空【这是Java的写法，JVM自动回收掉】
                   return;
                }
                node = node.nexts[index];
             }
             node.end--;
          }
       }
    
       public int search(String word) {
         // 查询word 这个字符串之前加入过几次
          if (word == null) {
        
             return 0;
          }
          char[] chs = word.toCharArray();
          TrieNode node = root; // node 从根节点开始
          int index = 0;
          for (int i = 0; i < chs.length; i++) {
        
             index = chs[i] - 'a'; 
             if (node.nexts[index] == null) {
         // 走着走着发现已经无路了，说明压根儿没有加过 word
                return 0;
             }
             node = node.nexts[index];
          }
          return node.end; // 字符串走完时，来到节点的end 值就是这个word 字符串加入过的次数
       }
    
       public int prefixNumber(String pre) {
         // 求：在所有加入的字符串中，有多少个是以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';
             if (node.nexts[index] == null) {
        
                return 0;
             }
             node = node.nexts[index];
          }
          return node.pass; //pass 值【妙啊】
       }
    }

栗子：

一个字符串类型的数组arr1，另一个字符串类型的数组arr2。arr2中有哪些字符，是arr1中 出现的？请打印。arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印。arr2 中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 arr2中出现次数最大的前缀。

##### 7.2 贪心算法 #####

在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。

也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

局部最优 -?-> 整体最优

###### 7.2.1 贪心算法的在笔试时的解题套路 ######

1.  实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
2.  脑补出贪心策略A、贪心策略B、贪心策略C…
3.  用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
4.  不要去纠结贪心策略的证明【很难】

###### 7.2.2 从头到尾展示最正统的贪心策略求解过程 ######

例子：

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

> 【字典序的比较】
> 
>  *  如果两个字符串长度相等【想象成26进制的数】
>     
>     abc < bck
>  *  长度不等，短的补0
>     
>     b 和 apple
>     
>     b0000 > apple

贪心策略：

a 和 b 挑，如果ab ≤ ba，那么a放前面，否则b 放前面

Java实现代码：

public static class MyComparator implements Comparator<String> {
         // 自定义比较器
       @Override
       public int compare(String a, String b) {
        
          return (a + b).compareTo(b + a);
       }
    }
    
    public static 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;
    }

证明：

*  有效性。比较策略一定要有传递性，不然没意义
    
    a.b ≤ b.a、b.c ≤ c.b → a.c ≤ c.a【这里的. 是拼接运算】
    
    这个结论是很好证明的。其实可以把字符串看成k 进制的数
    
    “abc” . “de” = “abcde” 如何把这个东西表达成数学运算
    
    → “abc” \*  k 2 k^2 k2 \+ “de” 【牛逼】
    
    普适一点就可以写成 → a.b → a \*  k b 长度 k^\{b长度\} kb长度 \+ b 【之后就可以接着证明了】
    
    ![在这里插入图片描述][7f9ff86e3d1f410796e79a9205dffc8c.png_pic_center]
 *  还要证明为什么以这样的方式进行拼接能得到最小的字典序。
    
    \[…a…b…\] → \[…b…a…\]
    
     *  a、b挨着的情况最好证，我们有天然的结论a.b ≤ b.a
     *  a、b隔开的情况
        
        本质一样，依次交换下去就行了【数学归纳】

证明贪心策略可能是件非常腌心的事情。平时当然推荐你搞清楚所有的来龙去脉，但是笔试时用对数器的方式！

###### 7.2.3 贪心策略在实现时，经常使用到的技巧 ######

1.  根据某标准建立一个比较器来排序
2.  根据某标准建立一个比较器来组成堆

##### 7.3 一些题目 #####

###### 7.3.1 分金条【经典哈夫曼编码问题】 ######

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

一群人想整分整块金条，怎么分最省铜板? 例如,给定数组\{10,20,30\}，代表一共三个人，整块金条长度为10+20+30=60。 金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50，花费60； 再把长度50的金条分成20和30，花费50；一共花费110铜板。 但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20， 花费30；一共花费90铜板。

输入一个数组，返回分割的最小代价。

Java代码实现：

public static int lessMoney(int[] arr) {
        
       PriorityQueue<Integer> pQ = new PriorityQueue<>();
       for (int i = 0; i < arr.length; i++) {
        
          pQ.add(arr[i]);
       }  // 所有数字扔进小根堆
       int sum = 0;
       int cur = 0;
       while (pQ.size() > 1) {
        
          cur = pQ.poll() + pQ.poll(); // 每次从小根堆中弹出两个数字结合一下
          sum += cur; // 累加到总代价中
          pQ.add(cur); // 将结合出的数扔回小根堆
       }
       return sum;
    }
    
    public static class MinheapComparator implements Comparator<Integer> {
        
    
       @Override
       public int compare(Integer o1, Integer o2) {
        
          return o1 - o2; // < 0  o1 < o2  负数
       }
    
    }
    
    public static class MaxheapComparator implements Comparator<Integer> {
        
    
       @Override
       public int compare(Integer o1, Integer o2) {
        
          return o2 - o1; // <   o2 < o1
       }
    
    }

###### 7.3.2 会议问题 ######

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

【思路】

1.  开始时间越早的越先安排。【不能得到最优解】
2.  持续时间越短越先安排。【也不能】
3.  正确的贪心策略：哪一个会议结束的时间早，就先安排。【可以得到最优解】

Java代码实现：

public static class Program {
        
       public int start; // 开始时间
       public int end; // 结束时间
    
       public Program(int start, int end) {
        
          this.start = start;
          this.end = end;
       }
    }
    
    public static class ProgramComparator implements Comparator<Program> {
         // 自定义比较器
    
       @Override
       public int compare(Program o1, Program o2) {
        
          return o1.end - o2.end;
       }
    
    }
    
    public static int bestArrange(Program[] programs, int start) {
        
       Arrays.sort(programs, new ProgramComparator());
       int result = 0;
       for (int i = 0; i < programs.length; i++) {
         // 从左到右依次遍历所有的会议
          if (start <= programs[i].start) {
        
             result++;
             start = programs[i].end;
          }
       }
       return result;
    }

> 别去纠结它为什么对

###### 7.3.3 最大利润 ######

输入：

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

含义： costs\[i\]表示i号项目的花费 profits\[i\]表示i号项目在扣除花费之后还能挣到的钱(利润) k表示你只能串行的最多做k个项目 m表示你初始的资金

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

输出： 你最后获得的最大钱数。

> 【大小根堆一起用】

public static class Node {
        
       public int p; // 利润
       public int c; // 花费
    
       public Node(int p, int c) {
        
          this.p = p;
          this.c = c;
       }
    }
    
    public static class MinCostComparator implements Comparator<Node> {
        
    
       @Override
       public int compare(Node o1, Node o2) {
        
          return o1.c - o2.c;
       }
    
    }
    
    public static class MaxProfitComparator implements Comparator<Node> {
        
    
       @Override
       public int compare(Node o1, Node o2) {
        
          return o2.p - o1.p;
       }
    
    }
    
    public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        
       Node[] nodes = new Node[Profits.length];
       for (int i = 0; i < Profits.length; i++) {
        
          nodes[i] = new Node(Profits[i], Capital[i]);
       }
    
       PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator()); // 花费的小根堆
       PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator()); // 利润的大根堆
        
       // 所有项目扔到被锁池中，花费组织的小根堆
       for (int i = 0; i < nodes.length; i++) {
         
          minCostQ.add(nodes[i]);
       }
       for (int i = 0; i < k; i++) {
         // 进行k 轮
          // 所有力所能及的项目，全解锁
          while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
        
             maxProfitQ.add(minCostQ.poll()); // 从花费小根堆中弹出进入利润大根堆
          }
          if (maxProfitQ.isEmpty()) {
         // 没有项目可挑了
             return W;
          }
          W += maxProfitQ.poll().p;
       }
       return W;
    }

###### 7.3.4 数据流中位数 ######

一个数据流中，随时可以取得中位数【源源不断的给数据，维持这个结构，随时可以取到中位数】

【这个题和贪心没关系，就是一个堆的应用】

大小根堆配合，第一个数字直接进大根堆，后面给来的数字

1.  先看给的当前数字是否 ≤ 大根堆堆顶
    
     *  是，当前数字入大根堆
     *  不是，当前数字入小根堆
2.  看看大根堆和小根堆的大小
    
     *  如果哪一个的大小超过了另一个，size 较大的比size 较小的，差值到达了2，就较大的堆顶弹出进较小的那个

这样最后达到的效果就是较小的n/2 个数在大根堆里，较大的n/2 个数在小根堆里，各自维持的堆顶就总能得到中位数。

Java代码实现：

public static class MedianHolder {
        
       private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
       private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new MinHeapComparator());
    
       private void modifyTwoHeapsSize() {
        
          if (this.maxHeap.size() == this.minHeap.size() + 2) {
        
             this.minHeap.add(this.maxHeap.poll());
          }
          if (this.minHeap.size() == this.maxHeap.size() + 2) {
        
             this.maxHeap.add(this.minHeap.poll());
          }
       }
    
       public void addNumber(int num) {
        
          if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
        
             maxHeap.add(num);
          } else {
        
             minHeap.add(num);
          }
          modifyTwoHeapsSize();
       }
    
       public Integer getMedian() {
        
          int maxHeapSize = this.maxHeap.size();
          int minHeapSize = this.minHeap.size();
          if (maxHeapSize + minHeapSize == 0) {
        
             return null;
          }
          Integer maxHeapHead = this.maxHeap.peek();
          Integer minHeapHead = this.minHeap.peek();
          if (((maxHeapSize + minHeapSize) & 1) == 0) {
        
             return (maxHeapHead + minHeapHead) / 2;
          }
          return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
       }
    
    }
    
    public static class MaxHeapComparator implements Comparator<Integer> {
        
       @Override
       public int compare(Integer o1, Integer o2) {
        
          if (o2 > o1) {
        
             return 1;
          } else {
        
             return -1;
          }
       }
    }
    
    public static class MinHeapComparator implements Comparator<Integer> {
        
       @Override
       public int compare(Integer o1, Integer o2) {
        
          if (o2 < o1) {
        
             return 1;
          } else {
        
             return -1;
          }
       }
    }

[LeetCode_100_BTAJ]: https://www.bilibili.com/video/BV13g41157hK
[7a4b72b8a00d446c895c1fb97ec97dc6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3471fa334a6146288b39d02ef88a68a1.png
[09783977004e44989c47fd52b17ad778.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/bdcda9955b5643bea990c94f0d8ad394.png
[7f9ff86e3d1f410796e79a9205dffc8c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/25bcb88612fe4a489e1897e6655035d5.png