数据结构与算法之花费铜板最小和利润最大题目

深藏阁楼爱情的钟 2021-12-18 06:25 157阅读 0赞

# 数据结构与算法之花费铜板最小和利润最大题目 #

--------------------

## 目录 ##

1.  花费铜板最小
2.  获得利润最大

--------------------

### 1. 花费铜板最小 ###

1.  题目描述  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]
2.  注：PriorityQueue(优先队列)，一个基于优先级堆的无界优先级队列。**实际上是一个堆**（不指定Comparator时默认是小顶堆），通过传入自定义的compara函数可以实现大顶堆。
3.  思路
    
    1.  生成优先级队列，默认是最小堆
    2.  创建sum记录总和，cur表示每次弹出两个之和
    3.  当pQ.size()>1时，从中取两个相加，用sum记录，cur再放回堆。
4.  代码实现

import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class Code_02_Less_Money {
        
    
    	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
    		}
    
    	}
    
    	public static void main(String[] args) {
        
    		// solution
    		int[] arr = {
         6, 7, 8, 9 };
    		System.out.println(lessMoney(arr));
    
    		int[] arrForHeap = {
         3, 5, 2, 7, 0, 1, 6, 4 };
    
    		// min heap
    		PriorityQueue<Integer> minQ1 = new PriorityQueue<>();
    		for (int i = 0; i < arrForHeap.length; i++) {
        
    			minQ1.add(arrForHeap[i]);
    		}
    		while (!minQ1.isEmpty()) {
        
    			System.out.print(minQ1.poll() + " ");
    		}
    		System.out.println();
    
    		// min heap use Comparator
    		PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinheapComparator());
    		for (int i = 0; i < arrForHeap.length; i++) {
        
    			minQ2.add(arrForHeap[i]);
    		}
    		while (!minQ2.isEmpty()) {
        
    			System.out.print(minQ2.poll() + " ");
    		}
    		System.out.println();
    
    		// max heap use Comparator
    		PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxheapComparator());
    		for (int i = 0; i < arrForHeap.length; i++) {
        
    			maxQ.add(arrForHeap[i]);
    		}
    		while (!maxQ.isEmpty()) {
        
    			System.out.print(maxQ.poll() + " ");
    		}
    	}
    }

--------------------

### 2. 获得利润最大 ###

1.  题目描述  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]
2.  思路
    
    1.  创建好所有的项目，加入Node\[\]
    2.  准备一个存放花费的小根堆，和准备一个利润的大根堆。
    3.  将所有的项目放入小根堆
    4.  for循环表示做项目次数不超过k，如果小根堆的堆顶的钱小于当前的钱，说明项目可以做，加入利润大根堆
    5.  如果大根堆空了，说明项目做不下去了，返回当前的钱数M
    6.  每次循环需要当前的钱加上做当前项目的利润。
3.  代码实现

import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class Code_03_IPO {
        
    	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++) {
        
    			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
        
    				maxProfitQ.add(minCostQ.poll());
    			}
    			if (maxProfitQ.isEmpty()) {
        
    				return W;
    			}
    			W += maxProfitQ.poll().p;
    		}
    		return W;
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211218/49d0c1c83eae42ae8e63286ef7ed6625.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211218/a784ccd79d0b42fb91574a56ff3bbee4.png