最小字典序

给定一个字符串类型的数组strs,找到一种拼接方式，使得把所有字符串拼接起来以后形成的字符串具有最小的字典序

public class LowestLexicography {public static class MyComparator implements Comparator<String>{@Overridepublic 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<Integer> 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<Program>{@Overridepublic 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<Node> {@Overridepublic int compare(Node o1, Node o2) {return o2.p - o1.p;}}public static class MinHeapComparator implements Comparator<Node> {@Overridepublic int compare(Node o1, Node o2) {return o1.c - o2.c;}}/**** @param k 最多能串行的k个项目* @param m 出初始资金* @param profits 项目利润集合* @param costs 项目花费集合* @return*/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<Node> minHeapQueue = new PriorityQueue<>(new MinHeapComparator());PriorityQueue<Node> 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);}
}

常用方法：

1. 根据某标准建立比较器来排序
2. 根据某标准建立比较器来组成堆