# 二、哈弗曼树&&切金条

//最小堆的比较器
public static class minHeapComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}

public static int lessMoney(int[] arr) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new minHeapComparator());
for (int num : arr){
}
int sum = 0;
int cur = 0;
while (priorityQueue.size()>1){
cur = priorityQueue.poll() + priorityQueue.poll();
sum += cur;
priorityQueue.offer(cur);
}
return sum;
}

# 三、Leetcode502 IPO

Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation:
Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project
indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

public static class psNode{
int profits;
int costs;
public psNode(int profits, int cotes) {
this.profits = profits;
this.costs = cotes;
}
}

public static class ProfitsMaxHeap implements Comparator<psNode>{
@Override
public int compare(psNode o1, psNode o2) {
return o2.profits - o1.profits;
}
}

public static class CostsMinHeap implements Comparator<psNode>{
@Override
public int compare(psNode o1, psNode o2) {
return o1.costs - o2.costs;
}
}

public int findMaximizedCapital(int k, int W, int[] Profits, int[] Costs) {
psNode [] psNodes = new psNode[Profits.length];
for ( int i = 0;i < Profits.length;i++){
psNodes[i] = new psNode(Profits[i],Costs[i]);
}

PriorityQueue<psNode> profitsHeap = new PriorityQueue<>(new ProfitsMaxHeap());
PriorityQueue<psNode> costsHeap = new PriorityQueue<>(new CostsMinHeap());

for (psNode node : psNodes){
costsHeap.offer(node);
}

for (int i = 0; i < k; i++) {
while (!costsHeap.isEmpty() && costsHeap.peek().costs <= W){
profitsHeap.offer(costsHeap.poll());
}
if (profitsHeap.isEmpty()) return W;
W += profitsHeap.poll().profits;
}
return W;
}

143 篇文章24 人订阅

0 条评论