最大收益问题以及求数据流中的中位数

78 阅读 0 评论 52 点赞

我是靠谱客的博主含糊香菇，最近开发中收集的这篇文章主要介绍最大收益问题以及求数据流中的中位数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

那个是纯利润，收回来的钱=费用加上纯利润
最多能做k个项目，w为项目启动资金。
讲花费放到小根堆里面，再将小于等于初始启动资金的项目放到大根堆里面
在这里插入图片描述做完第一个项目后资金=原有资金+纯利。再解锁小根堆里面小于等于启动资金的项目放到大根堆里面。挑选利润最大的项目去做

无法完成指定任务就必须要返回的情况（没有项目可以挑了）
在这里插入图片描述

总结：
1、先将小根堆里面符合条件的解锁到大根堆里面
2、判断大根堆是否为空，为空说明没有满足的项目可以去执行，提前返回。不为空，将堆顶元素弹出，并且启动资金=原启动资金+利润收入

在这里插入图片描述核心代码：

import java.util.*;

//将项目启动资金和利润捆绑
      class Program{
        int cost;
        int profit;

        public Program(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 表示你只能串行的最多做k个项目
     * @param m int整型 表示你初始的资金
     * @param costs int整型一维数组 costs[i]表示i号项目的花费
     * @param profits int整型一维数组 profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
     * @return int整型
     */
    public static int findMaximizedCapital (int k, int m, int[] costs, int[] profits) {
        // write code here
        //创建小根堆
        PriorityQueue<Program> pQ_min=new PriorityQueue<>(new Comparator<Program>() {
            @Override
            public int compare(Program o1, Program o2) {
                return o1.cost-o2.cost; //按照项目的花费升序排列
            }
        });
        //创建大根堆,改写比较器
        PriorityQueue<Program> pQ_max=new PriorityQueue<>(new Comparator<Program>() {
            @Override
            public int compare(Program o1, Program o2) {
                return o2.profit-o1.profit;//按照利润降序排列
            }
        });


        for (int i = 0; i <costs.length ; i++) {//将每个项目的花费添加到小根堆
            pQ_min.add(new Program(costs[i],profits[i]));
        }
        //比较项目启动资金和小根堆的堆顶
        for (int i = 0; i <k ; i++) {
            while(!pQ_min.isEmpty() && m>=pQ_min.peek().cost){//小根堆不为空,并且启动资金大于小根堆的堆顶
                //解锁小根堆中可以做的项目到大根堆
                //添加到大根堆
                pQ_max.add(pQ_min.poll());

            }
            //先判断大根堆是否为空（即看上一步有没有成功解锁项目）
            if(pQ_max.isEmpty()){
                return m;//为空说明没有可以执行的任务，提前返回
            }
            //解锁完之后从大根堆中挑出最大利润的项目
            m+=pQ_max.poll().profit;

        }

        return m;

    }
}

题目二：取得中位数

![在这里在这里插入图片描述

代码：

import java.util.*;

public class Solution {

    private ArrayList<Integer> list = new ArrayList<>();
    public void Insert(Integer num) {
        list.add(num);
    }

    public Double GetMedian() {
        int len = list.size();
        Collections.sort(list);
        if(len % 2 != 0)
            return (double)list.get(len/2);
        else
            return ((double)list.get(len/2) + (double)list.get(len/2-1))/2;
    }


}