苏州建网站必去苏州聚尚网络,网线制作方法及步骤,简单网页制作源代码,作文网网址文章目录 分金条题目思路代码实现测试用例以及结果输出 花费资金做项目最大收益题目思路代码实现测试用例以及结果输出 预定会议室题目思路代码实现测试用例以及结果输出 取中位数题目思路代码实现测试用例以及结果输出 最低字典序题目思路代码实现测试用例以及结果输出 结语 分… 文章目录 分金条题目思路代码实现测试用例以及结果输出 花费资金做项目最大收益题目思路代码实现测试用例以及结果输出 预定会议室题目思路代码实现测试用例以及结果输出 取中位数题目思路代码实现测试用例以及结果输出 最低字典序题目思路代码实现测试用例以及结果输出 结语 分金条
题目
一块金条切成两半是需要花费和长度数值一样的铜板的。比如 长度为20的 金条不管切成长度多大的两半都要花费20个铜 板。一群人想整分整块金 条怎么分最省铜板
例如,给定数组{10,20,30}代表一共三个人整块金条长度为 10203060. 金条要分成10,20,30三个部分。 如果 先把长 度60的金条分成10和50花费60 再把长度50的金条分成20和30 花费50 一共花费110铜板。 但是如果 先把长度60的金条分成30和30花费60 再把长度30 金条分成10和20花费30 一共花费90铜板。
输入一个数组返回分割的最小代价。
思路
哈夫曼树带权路径计算问题更多了解可参考哈夫曼树及其应用
先将给定数组进行排序这里可以使用优先级队列处理【优先级堆结构】将数组依次丢入优先级队列中每次从优先级队列中取出较小的值相加记录计算结果同时将结果重新丢入到队列中直到队列中没有元素将过程中的所有计算结果相加结果即为分割最小代价
代码实现 private static int lessMoney(int[] aar) {PriorityQueueInteger pQ new PriorityQueue();for (int i 0; i aar.length; i) {pQ.add(aar[i]);}int result 0;int cur 0;while (pQ.size() 1) {cur pQ.poll() pQ.poll();result cur;pQ.add(result);}return result;}测试用例以及结果输出 public static void main(String[] args) {int[] aar new int[]{30, 10, 20};System.out.println(lessMoney(aar));}输出结果
90花费资金做项目最大收益
题目
输入 参数1正数数组costs 参数2正数数组profits 参数3 正数k 参数4正数m
其中costs[i]表示i号项目的花费profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多做k个项目 m表示你初始的资金 说明你每做完一个项目马上获得的收益可以支持你去做下一个 项目。 输出你最后获得的最大钱数。
思路
基本原则结合生活中的实际生产每次选花费最小收益最高的项目去做最终得到的收益肯定是最大的
新定义Node类包含每个项目对应的花费以及收益分别定义两个优先级队列按照最小花费和最大收益优先级取元素将根据花费以及收益数组生成的Node数组丢入到最小花费优先级队列中进行K次遍历【最多可以做K个项目】不断从最小花费优先级队列中取出项目丢入到最大收益优先级队列中【注意资金问题】在根据最大收益去做项目【即从最大收益队列中取项目做】计算过程中获取的收益之和
代码实现
/*** 计算最大收益** param k 表示能做K个项目* param m 表示启动资金* param profits 表示做每个项目去除花费后的利润* param costs 表示做每个项目对应的花费* return*/private static int getMaxProfit(int k, int m, int[] profits, int[] costs) {//将项目对应花费以及收益包装成Node类,添加到Node[]数组中Node[] nodes new Node[costs.length];for (int i 0; i costs.length; i) {nodes[i] new Node(costs[i], profits[i]);}// 最小花费优先级队列PriorityQueueNode minConstQ new PriorityQueue(new MinComparator());// 最大收益优先级队列PriorityQueueNode maxProfitQ new PriorityQueue(new MaxComparator());//添加到最小花费优先级队列中for (int i 0; i nodes.length; i) {minConstQ.add(nodes[i]);}// k表示最多可以做k个项目for (int i 0; i k; i) {//只要花费不超过启动资金按照最小花费不断从队列中取丢入到收益队列中while (!minConstQ.isEmpty() minConstQ.peek().cost m) {maxProfitQ.add(minConstQ.poll());}//如果收益队列为空就返回最终资金否则每次从收益队列中取最大收益的项目去做if (maxProfitQ.isEmpty()) {return m;}m m maxProfitQ.poll().profit;}return m;}private static class Node {/*** 花费*/public int cost;/*** 利润*/public int profit;public Node(int cost, int profit) {this.cost cost;this.profit profit;}}/*** 花费最小排序*/private static class MinComparator implements ComparatorNode {Overridepublic int compare(Node o1, Node o2) {return o1.cost - o2.cost; //0表示o1o2}}/*** 利润最大排序*/private static class MaxComparator implements ComparatorNode {Overridepublic int compare(Node o1, Node o2) {return o2.profit - o1.profit; // 0 表示o2o1}}测试用例以及结果输出 public static void main(String[] args) {int k 3;int m 5;int[] profits new int[]{1, 3, 4, 6, 8};int[] costs new int[]{3, 6, 4, 2, 6};System.out.println(getMaxProfit(k, m, profits, costs));}
输出结果
23预定会议室
题目
一些项目要占用一个会议室宣讲会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间(给你一个数组里面是一个个具体的项目)你来安排宣讲的日程
要求会议室进行的宣讲的场次最多返回这个最多的宣讲场次。
思路
优先做最早结束的项目保证开始时间小于或等于要做项目的开始时间即可
代码实现 private static int getMaxProgram(Program[] program, int start) {Arrays.sort(program, new ProgramComparator());int result 0;for (int i 0; i program.length; i) {if (start program[i].start) {result;start program[i].end;}}return result;}/*** 定义项目会议 包含开始和结束时间*/private static class Program {public int start;public int end;public Program(int start, int end) {this.start start;this.end end;}}/*** 按哪个项目先结束排序*/private static class ProgramComparator implements ComparatorProgram {Overridepublic int compare(Program o1, Program o2) {return o1.end - o2.end;}}测试用例以及结果输出 public static void main(String[] args) {Program p1 new Program(6, 10);Program p2 new Program(7, 8);Program p3 new Program(11, 13);Program p4 new Program(13, 15);Program[] programs new Program[]{p1, p2, p3, p4};System.out.println(getMaxProgram(programs, 6));}输出结果
3取中位数
题目
一个数据流中随时可以取得中位数
思路
分别定义大根堆和小根堆以下述逻辑进行存放和调整
当大根堆为空时元素直接添加到大根堆中当大根堆不为空时如果元素小于或等于大根堆堆顶元素则添加到大根堆中否则添加到小根堆中当大根堆和小根堆元素个数相差为2时需要进行堆调整将元素个数多的堆堆顶元素放入元素个数少的堆中计算中位数当大根堆和小根堆元素个数相等则中位数为取两个堆的堆顶元素之和除以2如果元素个数不相等则中位数为元素个数多的堆的堆顶元素
下面以以图进行举例说明这里简单以队列表示大小根堆 可以理解成通过堆对元素进行排序只不过利用大小根队的性质保证中位数可以通过堆顶数据进行计算得出也避免了每次添加元素时进行排序问题时间复杂度更低
代码实现 private static class MedianHelper {private PriorityQueueInteger minQ new PriorityQueue(new MinComparator());private PriorityQueueInteger maxQ new PriorityQueue(new MaxComparator());public int getMedian() {int maxQSize maxQ.size();int minQSize minQ.size();if (maxQSize 0) {return 0;}//元素个数相等取两者堆顶元素/2if (maxQSize minQSize) {return (maxQ.peek() minQ.peek()) / 2;}//元素个数不相等取元素多的堆顶元素return maxQSize minQSize ? maxQ.peek() : minQ.peek();}//插入元素public void addNum(int num) {if (maxQ.isEmpty()) {maxQ.add(num);} else {if (maxQ.peek() num) {maxQ.add(num);} else {minQ.add(num);}}modifyQSize();}/*** 调整两个堆的大小 一旦发现两个堆数据个数相差为2则取多的丢到少的里面*/private void modifyQSize() {int minQSize minQ.size();int maxQSize maxQ.size();if (minQSize - maxQSize 2) {maxQ.add(minQ.poll());}if (maxQSize - minQSize 2) {minQ.add(maxQ.poll());}}}测试用例以及结果输出 public static void main(String[] args) {int[] aar new int[]{8, 6, 13, 10, 11, 19};MedianHelper helper new MedianHelper();for (int i : aar) {helper.addNum(i);}System.out.println(helper.getMedian());}输出结果
10最低字典序
题目
给定一个字符串类型的数组strs找到一种拼接方式使得把所有字符串拼起来之后形成的字符串具有最低的字典序。
思路
保证每次拼接后的字符串都是最低字典序的即可
代码实现 private static String lowestString(String[] strs) {if (strs null || strs.length 0) {return ;}Arrays.sort(strs, new LowestComparator());StringBuilder result new StringBuilder();for (int i 0; i strs.length; i) {result.append(strs[i]);}return result.toString();}/*** 定义两个字符拼接最小字典序比较器*/private static class LowestComparator implements ComparatorString {Overridepublic int compare(String o1, String o2) {return (o1 o2).compareTo(o2 o1);}}测试用例以及结果输出 public static void main(String[] args) {String[] strs2 {b, ab, ac};System.out.println(lowestString(strs2));}结果输出
abacb结语
如果以上文章对您有一点点帮助希望您不要吝啬的点个赞加个关注您每一次小小的举动都是我坚持写作的不懈动力ღ( ´ᴗ )
