哈夫曼编码
现在要解决这么一个问题，假设有一根长度为n的金条，要切成[x,y,z,....](x+y+z+....=n)的长度，并且每次切都要花费当前长度的代价，问：怎么切代价最小
举个例子：假设金条长度为60，要切成[10,20,30]的，如果我先把金条切成[10,50]，那么花费就是60，然后再将50切成[20,30]，花费是50，最后加起来总花费就是110，如果用另一种方法，先切成[30,30]，花费是60，然后将30切成[10,20]，花费是30，最后花费总和就是90，这种方法的代价是最小的
题解
典型的哈夫曼编吗问题。构建一个小根堆，将所有要求的值放进去，然后依次取出两个值，将其和累加到代价中，并且将其和再次放入小根堆，不断执行此操作直到堆中元素不大于1
代码import java.util.*;
public class Main {
public static int lessMoney(int[] arr) {
PriorityQueue minMoney = new PriorityQueue<>();
for(int i:arr)
minMoney.add(i);
int sum = 0;
while(minMoney.size() > 1) {
int a = minMoney.poll();
int b = minMoney.poll();
int c = a + b;
sum += c;
minMoney.add(c);
}
return sum;
}
public static void main(String[] args) {
System.out.println(lessMoney(new int[] {10,20,30}));
}
}
给定一个字符串数组，要求将其拼接后字典序最小
题解
假设字符串数组是str[] = {"ab","cd","ef"}，很明显答案就是”abcdef“最小，其实这是一道贪心问题，我的想法是将字符串数组进行内的字符串数组进行排序，这个大思路是没错的，但问题是怎么排序，str[i] < str[j]?这样其实不行，举个反例str[] = {"b","ba"}，如果按照那个贪心策略排序，得到的答案是"bba"，但实际上“bab”更小，后来仔细以想，贪心策略应该是str[i] + str[j] < str[j] + str[i]，有兴趣的大家可以下去证明，还是比较好证的
代码import java.util.*;
public class Main {
public static class MyCompara implements Comparator {
public int compare(String s1, String s2) {
String tmp1 = s1 + s2;
String tmp2 = s2 + s1;
return tmp1.compareTo(s2);
}
}
public static String minString(String[] str) {
String res = "";
Arrays.sort(str,new MyCompara());
for(int i = 0;i < str.length;i++)
res += str[i];
return res;
}
public static void main(String[] args) {
System.out.println(minString(new String[] {"ab","ef","cd"}));
}
}
题解
这道题贪心策略很直白，首先定义出一个结构，结构中包含利润和成本，然后按照成本最低构建一个小根堆，按照利润最高构建一个大根堆，依次将小根堆中成本小于等于当前资金的项目都添加到大根堆去，然后依次将大根堆中的项目弹出，获取利润即可
代码class Solution {
class Node {
int c;//成本
int p;//利润
Node(int c,int p) {
this.c = c;
this.p = p;
}
}
public static class MinC implements Comparator {
public int compare(Node node1,Node node2) {
return node1.c - node2.c;
}
}
public static class MaxP implements Comparator {
public int compare(Node node1,Node node2) {
return node2.p - node1.p;
}
}
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue minQueue = new PriorityQueue<>(new MinC());
PriorityQueue maxQueue = new PriorityQueue<>(new MaxP());
Node[] node = new Node[Profits.length];
for(int i = 0;i < Profits.length;i++) {
node[i] = new Node(Capital[i],Profits[i]);
minQueue.add(node[i]);
}
for(int i = 0;i < k;i++) {
while(!minQueue.isEmpty() && minQueue.peek().c <= W)
maxQueue.add(minQueue.poll());
if(maxQueue.isEmpty())//资金永远不够做某个项目
return W;
W += maxQueue.poll().p;
}
return W;
}
}
题解
三种贪心策略，按照开始时间小的，按照结束时间小的，按照总的时间短的，事实证明按照结束时间小的进行贪心的策略是对的
代码import java.util.*;
class Node {
int start;
int end;
Node(int start,int end) {
this.start = start;
this.end = end;
}
}
public class Main {
public static class MyCompare implements Comparator {
public int compare(Node node1,Node node2) {
return node1.end - node2.end;
}
}
public static int bestArray(Node[] node,int start) {
Arrays.sort(node,new MyCompare());
int sum = 0;;
for(int i = 0;i < node.length;i++) {
if(start <= node[i].start) {
sum++;
start = node[i].end;
}
}
return sum;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
Node[] node = new Node[n];
for(int i = 0;i < n;i++) {
int start = cin.nextInt();
int end = cin.nextInt();
node[i] = new Node(start,end);
}
System.out.println(bestArray(node,-10000));
}
}