- 最小字典序
- 金条切割问题
- 会议室宣讲次数问题
- 获得最大钱数
给定一个字符串类型的数组strs,找到一种拼接方式,使得把所有字符串拼接起来以后形成的字符串具有最小的字典序
public class LowestLexicography { public static class MyComparator implements Comparator金条切割问题{ @Override public int compare(String o1, String o2) { return (o1+o2).compareTo(o2+o1); } } public static String lowestString(String[] strs){ if (null == strs || strs.length == 0){ return ""; } Arrays.sort(strs,new MyComparator()); String str = ""; for (int i = 0; i < strs.length; i++) { str += strs[i]; } return str; } public static void main(String[] args) { String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" }; System.out.println(lowestString(strs1)); String[] strs2 = { "ba", "b" }; System.out.println(lowestString(strs2)); } }
一块金条切成两半,需要花费和长度数值一样的铜板,比如长度为20的金条,不管切成长度为多大的两半,都需要20个铜板
一群人想分一块金条,怎样分最省铜板
例如,给定数组{10,20,30},代表一共3个人,整块金条长度是10+20+30=60,
金条要分成10,20,30三个部分
如果先把长度为60的金条分成10和50,需要花费60铜板,再将50分成20和30,需要花费50个铜板,一共花费110个铜板
如果先把长度为60的金条分成2条30的,则花费60个铜板,再将其中一个30的金条分成10和20,花费30个铜板,一共花费90个铜板
输入一个数组,返回分割最小的代价(哈夫曼算法)
【思路】准备一个小根堆,取2个最小的元素相加,再放入小根堆,再取出2个最小值,相加,放回小根堆,循环,直至小根堆只有一个元素,就是最后的结果
public class LessMoneySplitGold { public static int lessMoney(int[] arr){ PriorityQueue会议室宣讲次数问题queue = new PriorityQueue<>(); for (int i : arr) { queue.add(i); } int sum = 0; int cur = 0; while (queue.size() > 1){ int a = queue.poll(); int b = queue.poll(); cur = a + b; sum = sum + cur; queue.add(cur); } return sum; } public static void main(String[] args) { int[] arr = {10,20,30}; int money = lessMoney(arr); System.out.println(money); } }
一些项目需要占用一个会议室宣讲,会议室不能同时容纳2个项目的宣讲,给每个项目的开始时间和结束时间,安排宣讲日程,要求会议室进行的宣讲次数最多。返回最多的宣讲场次
【思路】选择小于指定开始时间的项目,选出结束时间最早的,循环,找出所有的项目,返回项目的个数
public class Code04_BestArrange { 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获得最大钱数{ @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 res = 0; for (int i = 0; i < programs.length; i++) { if (start <= programs[i].start){ System.out.println(programs[i].start+","+programs[i].end); res++; start = programs[i].end; } } return res; } public static void main(String[] args) { Program program1 = new Program(6, 8); Program program2 = new Program(7, 9); Program program3 = new Program(9, 12); Program program4 = new Program(11, 13); Program program5 = new Program(14, 16); Program program6 = new Program(15, 18); Program program7 = new Program(17, 18); Program[] programs = {program1,program2,program3,program4,program5,program6,program7}; int arrange = bestArrange(programs, 6); System.out.println(arrange); } }
输入正数数组costs costs[i]表示i号项目的花费
输入正数数组profits profits [i]表示i号项目的利润
正数k 最多能串行k个项目
正数m 初始资金
每做完一个项目,立马获得收益,可以支持去做下一个项目
输出:最后获得的最大钱数
【思路】准备两个根堆,一个大根堆,一个小根堆,小根堆是用来存放按成本的小根堆,大根堆是从小根堆中拿出来的数据按照利润大根堆排序
先从小根堆中选出符合本金的项目,放入大根堆中,取出利润最大的项目,获得最大了利润后,再从小根堆中取出符合已获得利润后的本金,放入大根堆中,再次取出利润最大的项目,周而复始,直到没有项目可以做,返回最大钱数
public class 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 MaxHeapComparator implements Comparator{ @Override public int compare(Node o1, Node o2) { return o2.p - o1.p; } } public static class MinHeapComparator implements Comparator { @Override public int compare(Node o1, Node o2) { return o1.c - o2.c; } } public static int findMaximizedCapital(int k, int m, int[] profits, int[] costs){ Node[] nodes = new Node[profits.length]; for (int i = 0; i < profits.length; i++) { nodes[i] = new Node(profits[i], costs[i]); } PriorityQueue minHeapQueue = new PriorityQueue<>(new MinHeapComparator()); PriorityQueue maxHeapQueue = new PriorityQueue<>(new MaxHeapComparator()); for (Node node : nodes) { minHeapQueue.add(node); } for (int i = 0; i < k; i++) { while (!minHeapQueue.isEmpty() && minHeapQueue.peek().c <= m){ maxHeapQueue.add(minHeapQueue.poll()); } if (maxHeapQueue.isEmpty()){ return m; } m += maxHeapQueue.poll().p; } return m; } public static void main(String[] args) { int k = 3; int m = 4; int[] profits = {5,3,6,7}; int[] costs = {4,2,6,8}; int capital = findMaximizedCapital(k, m, profits, costs); System.out.println(capital); } }
常用方法:
- 根据某标准建立比较器来排序
- 根据某标准建立比较器来组成堆
声明一下,上面的代码都是根据左程云老师的算法课程整理的。有兴趣的自己去b站看相应的免费课程
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)