11、算法与数据结构 - 实战：贪心问题
给定一个字符串数组，把数组里的所有字符串拼接起来，返回所有拼接结果中字典序最小的拼接结果
贪心解题方法论：
- 贪心解法无需证明正确性
- 写一个暴力解，与之进行比较，如果在任何样本下出来的结果都是一样的，则这个贪心策略就是正确的
错误的贪心策略：
比较两个字符串的字典序，字典序小的优先拼接。在这种贪心策略下，“b"和"ba"的拼接就是错误的，因为会得出"bba”，而实际是"ba"先拼接会更小"bab"，但是因为"b"的字典序比"ba"的字典序小，所有"b"会先拼接。
正确的贪心策略：
假如有字符串a和b，a拼接b表示为a.b，b拼接a表示b.a，如果a.b<=b.a，则a排前面，先拼接，否则b排前，先拼接。
/**
* 给定一个字符串数组，把数组里的所有字符串拼接起来，返回所有拼接结果中字典序最小的拼接结果
*/
public class Greed01 {
public static String findLowestDictionaryOrderAppend(String[] strs) {
if (strs == null || strs.length == 0) return "";
Arrays.sort(strs, (str1, str2) -> (str1 + str2).compareTo(str2 + str1));
String result = "";
for (String str : strs) {
result += str;
}
return result;
}
}
会议安排问题
一个会议室，若干场会议，会议室同一时间只能安排一场会议，
每场会议都有开始时间和结束时间，安排会议日程，要求安排的场次最多。
错误的贪心策略：
1、 以会议开始时间排序，选开始时间早的；
2、 以会议持续时间排序，选持续时间短的；
正确的贪心策略：
以结束时间排序，选结束时间早的。
/**
* 会议安排问题
* 一个会议室，若干场会议，会议室同一时间只能安排一场会议，
* 每场会议都有开始时间和结束时间，安排会议日程，要求安排的场次最多
*/
public class Greed02 {
public static int process(Meeting[] meetings) {
if (meetings == null || meetings.length == 0) return 0;
int result = 0;
//根据结束时间早进行排序
Arrays.sort(meetings, (o1, o2) -> o1.endTime - o2.endTime);
int currentTime = 0;
for (int i = 0; i < meetings.length; i++) {
Meeting meeting = meetings[i];
if (meeting.startTime <= currentTime) {
result++;
currentTime = meeting.endTime;
}
}
return result;
}
public static class Meeting {
private int startTime;
private int endTime;
}
}
街道放灯问题
给定一个字符串，代表一条街道，字符串中只有"."或者"x"两种字符，
"."代表居民楼，需要照亮并且可以放灯，灯可以照亮当前位置，以及前面后后面一个位置，
"x"代表墙，不需要照亮并且无法放灯，
如何放置灯才使得放置数量最少，
返回最少放灯数。
贪心解法：
1、 如果当前位置i是"x"，直接跳到i+1；
2、 如果当前位置i是".“，先灯数light++，然后看要跳到哪里如果i+1是"x”，则跳到i+2（i位置放灯），如果i+1是".“，跳到i+3（i+1位置放灯，i和i+2都被照亮，或者i+2是"x”）；
/**
* 街道放灯问题
* 给定一个字符串，代表一条街道，字符串中只有"."或者"x"两种字符，
* "."代表居民楼，需要照亮并且可以放灯，灯可以照亮当前位置，以及前面后后面一个位置
* "x"代表墙，不需要照亮并且无法放灯
* 如果放置灯才使得放置数量最少
* 返回最少放灯数
*/
public class Greed03 {
public static int process(String road) {
char[] chars = road.toCharArray();
int result = 0;
int index = 0;
while (index < road.length()) {
//如果当前位置时墙，直接跳过
if (chars[index] == 'x') index++;
else {
//如果当前位置是灯，必然会放灯
result++;
//没有下一个位置，跳出循环
if (index + 1 == road.length()) break;
else {
//下一个位置是墙，那么等必须放在当前位置，然后跳到下下个位置
if (chars[index + 1] == 'x') index += 2;
//否则等放到下个位置，然后跳到下下下个位置
else index += 3;
}
}
}
return result;
}
}
金条切分
给定一块金条，切分它需要花费和金条长度值一样的铜板个数，
给定一个数组，代表每个人期望分得的金条，
如何切分才能使得铜板花费个数最小，
最后返回铜板个数。
解法：哈夫曼编码
1、 把数组的所有元素，放入小根堆；
2、 一开始代价sum是0，最后要返回这个总代价sum；
3、 只要小根堆不是只剩一个数，就弹出两个数累计为cur，cur累计到代价中，然后把cur放回小根堆；
/**
* 金条切分
* 给定一块金条，切分它需要花费和金条长度值一样的铜板个数
* 给定一个数组，代表每个人期望分得的金条
* 如何切分才能使得铜板花费个数最小，
* 最后返回铜板个数
*/
public class Greed04 {
public static int process(int[] arr) {
PriorityQueue<Integer> q = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
q.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (q.size() > 1) {
cur = q.poll() + q.poll();
sum += cur;
q.add(cur);
}
return sum;
}
}
一个人做项目
给定一个整形数组costArr，代表项目启动资金，
一个整形数组profitsArr，代表项目利润
一个整形k表示最多只能做k个项目，
一个整形w表示初始资金，
同一时间只能做一个项目（不能并行做），做完马上得到利润，然后去做下一个项目，
求最后获得的最大钱数。
解法：
1、 设置两个堆，一个小跟堆（按花费排序，代表待解锁的项目），一个大根堆（按利润排序，表示已解锁的项目）；
2、 每轮按照当前的金钱去解锁项目，把小跟堆中解锁的项目弹出放入大根堆，从大根堆拿出堆顶项目，代表选择做这个项目；
3、 直到完成k轮；
4、 返回累积的金钱数；
/**
* 一个人做项目
* 给定一个整形数组costArr，代表项目启动资金，
* 一个整形数组profitsArr，代表项目利润
* 一个整形k表示最多只能做k个项目，
* 一个整形w表示初始资金
* 同一时间只能做一个项目（不能并行做），做完马上得到利润，然后去做下一个项目
* 求最后获得的最大钱数
*/
public class Greed05 {
public static int process(int[] costArr, int[] profitsArr, int k, int w) {
//按照花费排序的小跟堆
PriorityQueue<Project> minCostProjects = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
//按照利润排序的大根堆
PriorityQueue<Project> maxProfitsProjects = new PriorityQueue<>((o1, o2) -> o2.profits - o1.profits);
//组装成项目放入小根堆
for (int i = 0; i < costArr.length; i++) {
Project project = new Project();
project.cost = costArr[i];
project.profits = profitsArr[i];
minCostProjects.add(project);
}
for (int i = 0; i < k; i++) {
//把启动资金小于等于当前资金的项目，全部放入大根堆
while (!minCostProjects.isEmpty() && w >= minCostProjects.peek().cost) maxProfitsProjects.add(minCostProjects.poll());
//没有项目可做，提前结束
if (maxProfitsProjects.isEmpty()) break;
//从大根堆中挑出利润最大的项目
w += maxProfitsProjects.poll().profits;
}
return w;
}
public static class Project {
private int cost; //项目花费
private int profits; //项目利润
}
}
补充-哈夫曼编码
哈夫曼编码
构造任意字符串的比特流最小化的单词查找树，把出现频率最高的字符用最小的编码表示，并且所有的字符编码都不会成为其他编码的前缀。
算法流程：
输出端
1、 读取输入；
2、 将输入中的每个字符与其出现频率进行映射，构造一个map；
3、 遍历map构造节点，并通过优先队列按频率从小到大排序；
4、 根据频率构造哈夫曼树（单词查找树）；
5、 根据哈夫曼树构造编码表，保存字符和编码间的映射；
6、 将哈夫曼树编码为比特流并写出；
7、 将字符总数编码为比特流并写出；
8、 将字符串编码为比特流并写出；
读取端
1、 读取哈夫曼树；
2、 读取字符数量；
3、 使用哈夫曼树将比特流解码；
如何构造哈夫曼树？
从优先队列中取出两个当前频率最小的节点，构成一个树，父节点的频率为两子节点频率值之和，在将该父节点入队列；重复该过程，最后得出根节点。
如果编码和解码哈夫曼树？
- 编码：前序遍历，遇到非叶子节点，则输出0，遇到叶子节点则输出1然后输出字符代表的字节流。
- 解码：前序遍历创建节点，遇到0则创建一个空节点并递归创建其左右子节点，遇到1则创建叶子节点保存后面读取的字符。
public class Huffman {
public static void main(String[] args) {
Huffman huffman = new Huffman();
String input = "it was the best of times it was the worst of times";
String compress = huffman.compress(input);
String unCompress = huffman.unCompress(compress);
System.out.println("result is: " + input.equals(unCompress));
}
private static class Node implements Comparable<Node> {
private char ch;
private int freq;
private Node left;
private Node right;
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
@Override
public int compareTo(Node that) {
return this.freq - that.freq;
}
public boolean isLeaf() {
return this.left == null && this.right == null;
}
}
/**
* 解压还原字符串
* @param codes 编码字符串
* @return 还原后的字符串
*/
public String unCompress(String codes) {
// 1.解析获取哈夫曼树
AtomicInteger indexCounter = new AtomicInteger(0);
Node root = parseHuffmanTree(codes, indexCounter);
// 2. 读取字符数量
int len = parseInputLen(codes, indexCounter);
System.out.println("input string length: " + len);
// 3. 使用哈夫曼树将比特流解码
StringBuilder res = new StringBuilder();
for (int i = 0; i < len; i++) {
char c = parseOneChar(root, codes, indexCounter);
res.append(c);
}
System.out.println("uncompress string: " + res.toString());
return res.toString();
}
/**
* 解析获取一个字符串：
* 判断二进制字符串当前下标的字符是0还是1，
* 0则递归左节点，1则递归右节点，
* 直到当前节点是叶子节点，则返回该节点对应的字符
* @param node 当前的哈夫曼节点
* @param codes 编码后的二进制字符串
* @param indexCounter 下标计数器，保存当前解析到的下标
* @return 解析后的字符
*/
private char parseOneChar(Node node, String codes, AtomicInteger indexCounter) {
if (node.isLeaf()) {
return node.ch;
} else {
int i = codes.charAt(indexCounter.getAndIncrement());
if (i == '0') {
return parseOneChar(node.left, codes, indexCounter);
} else {
return parseOneChar(node.right, codes, indexCounter);
}
}
}
/**
* 解析获取输入字符串的长度
* @param codes 编码后的二进制字符串
* @param indexCounter 下标计数器，保存当前解析到的下标
* @return 输入字符串长度
*/
private int parseInputLen(String codes, AtomicInteger indexCounter) {
String inputLenBianryStr = codes.substring(indexCounter.get(), indexCounter.addAndGet(32));
return Integer.valueOf(inputLenBianryStr.toString(), 2);
}
/**
* 解析获取哈夫曼树：
* 前序遍历创建节点，
* 遇到0则创建一个空节点并递归创建其左右子节点，
* 遇到1则创建叶子几点保存后面读取的字符
* @param codes 编码后的二进制字符串
* @param indexCounter 下标计数器，保存当前解析到的下标
* @return 哈夫曼树根节点
*/
private Node parseHuffmanTree(String codes, AtomicInteger indexCounter) {
if (codes.charAt(indexCounter.get()) == '1') {
String charBinaryStr = codes.substring(indexCounter.incrementAndGet(), indexCounter.addAndGet(8));
return new Node(new String(new byte[] {
Byte.valueOf(charBinaryStr, 2)}).charAt(0), 0, null, null);
} else {
indexCounter.incrementAndGet();
return new Node('\0', 0, parseHuffmanTree(codes, indexCounter), parseHuffmanTree(codes, indexCounter));
}
}
/**
* 利用哈夫曼压缩法压缩字符串
* @param input 输入字符串
* @return 压缩后的编码字符串
*/
public String compress(String input) {
// 1. 读取输入，构造一颗哈夫曼树
System.out.println("input string: " + input);
Node root = buildTree(input);
// 2.根据哈夫曼树构造编码表，保存字符和编码间的映射
Map<Character, String> huffmanCodeTable = new HashMap<>();
buildCodeTable(huffmanCodeTable, root, "");
System.out.println("huffmanCodeTable: " + huffmanCodeTable);
// 3.将哈夫曼树编码为比特流字符串
StringBuilder huffmanCodes = new StringBuilder();
codinghuffmanTree(root, huffmanCodes);
// 4.将字符总数编码为比特流字符串
huffmanCodes.append(getInputLenBinaryStr(input.length()));
// 5. 将字符串编码为比特流并字符串
codingInputStr(input, huffmanCodeTable, huffmanCodes);
System.out.println("compress string: " + huffmanCodes.toString());
return huffmanCodes.toString();
}
/**
* 将字符串编码为比特流并字符串
* @param input 输入字符串
* @param huffmanCodeTable 编码表
* @param huffmanCodes 编码后的二进制字符串
*/
private void codingInputStr(String input, Map<Character, String> huffmanCodeTable, StringBuilder huffmanCodes) {
for (int i = 0; i < input.length(); i++) {
huffmanCodes.append(huffmanCodeTable.get(input.charAt(i)));
}
}
/**
* 获取输入字符串长度的二进制字符串
* @param len 输入字符串长度
* @return 长度的二进制字符串
*/
private String getInputLenBinaryStr(int len) {
String binaryStr = Integer.toBinaryString(len);
int n = 32 - binaryStr.length();
StringBuilder binaryRes = new StringBuilder();
for (int i = n; i > 0; i--) binaryRes.append("0");
binaryRes.append(binaryStr);
return binaryRes.toString();
}
/**
* 获取字符对应的二进制字符串
* @param ch 输入字符
* @return 二进制字符串
*/
private String getBinaryStr(char ch) {
String binaryStr = Integer.toBinaryString(ch | 256);
binaryStr = binaryStr.substring(binaryStr.length()-8);
return binaryStr;
}
/**
* 把哈夫曼树编码为二进制字符串
* 前序遍历，遇到非叶子节点，则输出0，遇到叶子节点则输出1然后输出字符代表的二进制字符串
* @param root 哈夫曼树根节点
* @return 编码后的二进制字符串
*/
private void codinghuffmanTree(Node node, StringBuilder huffmanCodes) {
if (node.isLeaf()) {
huffmanCodes.append("1");
huffmanCodes.append(getBinaryStr(node.ch));
} else {
huffmanCodes.append("0");
codinghuffmanTree(node.left, huffmanCodes);
codinghuffmanTree(node.right, huffmanCodes);
}
}
/**
* 根据哈夫曼树构造编码表，保存字符和编码间的映射
* 左：0；右：1
* @param huffmanCodeTable 哈夫曼编码表
* @param root 哈夫曼树根节点
*/
private void buildCodeTable(Map<Character, String> huffmanCodeTable, Node node, String code) {
if (node.isLeaf()) {
huffmanCodeTable.put(node.ch, code);
return;
}
buildCodeTable(huffmanCodeTable, node.left, code+"0");
buildCodeTable(huffmanCodeTable, node.right, code+"1");
}
/**
* 构造哈夫曼树
* @param input 输入字符串
* @return 哈夫曼树根节点
*/
private Node buildTree(String input) {
// 1. 将输入中的每个字符与其出现频率进行映射，构造一个map
Map<Character, Integer> charTable = new HashMap<>();
for (int i = 0; i < input.length(); i++) {
if (charTable.containsKey(input.charAt(i))) {
charTable.put(input.charAt(i), charTable.get(input.charAt(i)) + 1);
} else {
charTable.put(input.charAt(i), 1);
}
}
// 2. 遍历map构造节点，并通过优先队列按频率从小到大排序
PriorityQueue<Node> queue = new PriorityQueue<>();
for (Entry<Character, Integer> entry : charTable.entrySet()) {
queue.offer(new Node(entry.getKey(), entry.getValue(), null, null));
}
/*
* 构造哈夫曼树:
* 从优先队列中取出两个当前频率最小的节点，构成一个树，
* 父节点的频率为两子节点频率值之和；
* 再将该父节点入队列；
* 重复该过程，最后得出返回根节点。
* */
while (queue.size() > 1) {
Node node1 = queue.poll();
Node node2 = queue.poll();
queue.offer(new Node('\0', node1.freq + node2.freq, node1, node2));
}
return queue.poll();
}
}