年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容，转移简书）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：前缀树
实例2：贪心算法理解，例题字典序字符串拼接
实例3：黄金分割问题
实例4：项目收益问题
实例5：会议时间安排问题
从实例2开始都是贪心算法问题
实例1
前缀树
初始化一个头结点
每次新进一个字符串都是从头结点开始查
插入"abc"
查看 有指向 a 的路吗？
没有，添加
有，复用
注意：不是将a添加到节点上，而是路径上。
重复上述过程，建立前缀树如下图
此时，再加上一个字符串怎么办？如"bce"，同样过程
查看 有指向b 的路吗？
没有，添加
有，复用
...
添加后如图
继续添加"abd"
查看 有指向 a 的路吗？
没有，添加
有，复用
具体过程如图
1_1_前缀树建立过程.png
一个字符串加入前缀树的过程，总是从头结点开始，然后依次看有没有沿途的路
有，复用
没有，新建
前缀树作用
比如已经添加了N个字符串，查看N个字符串中，是否某一个字符串是以 "be" 开头的
扩展1：你加入的字符串有 "be"吗？
这个问题，上述形成的前缀树，已经无法满足现在的需求了，如上图，你无法确定-b-e-路是你添加字符串"bef"形成的还是添加"be"形成的
解决：给每个节点添加上数据项。数据项：有多少个字符串是以当前节点结尾的。
加上这个数据项好处
1、前缀树是否加入了某个字符串
2、某个字符串在前缀树中添加的次数
1_2_数据项扩展.png
如图
加上数据项（有多少个字符串是以当前节点结尾的）后可以轻松查看1、是否存在某个字符2、某个字符串在前缀树中的个数
如图：abd 3个 be 2个 其他字符串都是一个
扩展2：有多少个节点以某字符串作为前缀？
解决：再添加一个数据项：添加字符串时当前节点被滑过了几次
比如依次添加字符串：["abc", "abd", "ace"],统计有多少以"ab"为前缀的字符串
在添加的时候每次滑过某个节点，都记录滑过次数
abc
a 1
b 1
c 1
abd
a 2
b 2
d 1
ace
a 3
c 1
e 1
很清晰的查出以ab 为前缀的字符串有 2 个，以 a 为前缀的有3 个，以ac 为前缀的有 1个
前缀树在添加，和查的过程中代价都非常的低，跟样本量N没有关系，和样本的长度有关。
/**
* @description:
* @version: 1.0
*/
public class Code_36_TrieTree {
// 前缀树数据项结构
public static class TrieNode {
public int pathNum; // 字符串滑过当前节点是次数
public int endNum; // 以此节点结尾的字符串个数
// public HashMap<Character, TrieNode> nexts; // 结构复杂使用map
public TrieNode[] nexts; // 这里为了方便使用数组，假设涉及数据都是小写的26个字母
public TrieNode() {
this.pathNum = 0;
this.endNum = 0;
this.nexts = new TrieNode[26];
}
}
// 前缀树
public static class Trie {
private TrieNode root; // 前缀树加上数据项
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
if (word == null) return;
TrieNode node = this.root;
char[] chars = word.toCharArray();
int index = 0; // 用来标记路线，默认26个字母，每个节点26条路线
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
node.pathNum++;
}
node.endNum++;// 结尾节点
}
public void delete(String word) {
if (search(word) != 0) {
TrieNode node = this.root;
char[] chars = word.toCharArray();
int index = 0;
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if (--node.nexts[index].pathNum == 0) { // 如果节点滑过次数只有一次，直接置为null，后序节点无需再遍历
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.endNum--;
}
}
// 查找是否存在某个字符串
public int search(String word) {
if (word == null) return 0;
TrieNode node = this.root;
char[] chars = word.toCharArray();
int index = 0;
for (int i = 0; i < chars.length; i++) {
index = chars[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.endNum;
}
public int prefixNumber(String pre) {
if (pre == null) {
return 0;
}
char[] chs = pre.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return 0;
}
node = node.nexts[index];
}
return node.pathNum;
}
}
public static void main(String[] args) {
Trie trie = new Trie();
System.out.println(trie.search("test"));
trie.insert("test");
System.out.println(trie.search("test"));
trie.delete("test");
System.out.println(trie.search("test"));
trie.insert("test");
trie.insert("test");
trie.delete("test");
System.out.println(trie.search("test"));
trie.delete("test");
System.out.println(trie.search("test"));
trie.insert("testa");
trie.insert("testac");
trie.insert("testab");
trie.insert("testad");
trie.delete("testa");
System.out.println(trie.search("testa"));
System.out.println(trie.prefixNumber("test"));
}
}
实例2
贪心算法：对问题进行求解时，总是做出当前来看是最好的选择。
笔试解决贪心算法的技巧
提出什么策略很容易，但是证明一个贪心策略是对的很难，最简单的证明就是使用对数器验证，
在对数器的样本（如5000个）是对的，那就认为它是对的。
举例一个非常难的贪心算法问题：做法简单，证明难。
字符串字典排序拼接
给你一个字符串数组，目的是把所有的字符串拼起来，不能遗漏，这样会得到很多
拼接的结果，请你找到拼接的字符串，字典序最小的结果。
如："ab", "cd", "ef"
拼接结果
abcdef
abefcd
cdabef
cdefab
efabcd
efcdab
这六种结果，其中，字面值最小的是abcdef。
理解一个概念：字典序
长度一样，当做26进制的数，比较大小，小在前
长度不等，补全，补位为字面值最小的数 如 "abc" 和 "b" 比较，补位 "b00"。a < b
所以"abc"在前，"b"在后
贪心策略:两个字符串排序时先拼接再比较
str1 + str2 <= str2 + str1 ？ str1 : str2
import java.util.Arrays;
import java.util.Comparator;
/**
* @description: 字符串字典序拼接
* 给你一个字符串数组，目的是把所有的字符串拼起来，不能遗漏，这样会得到很多
* 拼接的结果，请你找到拼接的字符串，字典序最小的结果。
* 如："ab", "cd", "ef"
* 拼接结果
* abcdef
* abefcd
*
* cdabef
* cdefab
*
* efabcd
* efcdab
*
* 这六种结果，其中，字面值最小的是abcdef。
*
* 理解一个概念：字典序
* 长度一样，当做26进制的数，比较大小，小在前
* 长度不等，补全，补位为字面值最小的数 如 "abc" 和 "b" 比较，补位 "b00"。a < b
* 所以"abc"在前，"b"在后
*
*
*
* 思路：进行字典排序
* @version: 1.0
*/
public class Code_37_TX_LowestLexicography {
// 贪心策略:两个字符串排序时先拼接再比较
// str1 + str2 <= str2 + str1 ？ str1 : str2
public static class MyComparator implements Comparator<String>{
@Override
public int compare(String strA, String strB) {
return (strA + strB).compareTo((strB + strA));
}
}
public static String lowestLexicography(String[] str){
if (str == null || str.length == 0)
return "";
Arrays.sort(str, new MyComparator());
String res = "";
for (int i = 0; i < str.length; i++) {
res += str[i];
}
return res;
}
public static void main(String[] args) {
String[] strs1 = { "abc", "bc", "ac", "aa", "abb" };
System.out.println(lowestLexicography(strs1));
String[] strs2 = { "ba", "b" };
System.out.println(lowestLexicography(strs2));
}
}
实例3
黄金分割问题
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如 长度为20的 金条，不管切成长度多大的两半，都要花费20个铜 板。一群人想整分整块金 条，怎么分最省铜板？ 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分。
如果， 先把长 度60的金条分成10和50，花费60 再把长度50的金条分成20和30， 花费50 一共花费110铜板。
但是如果， 先把长度60的金条分成30和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板。
输入一个数组，返回分割的最小代价
从题意中提取出两个信息
1、花费和长度数值一样
2、总和要最小，且总和是由一个个子金额累加的
哈夫曼编码策略
总代价是由子带价累加，累乘的这类问题，都可以使用哈夫曼编码来进行求解。
理解哈夫曼建树过程
3_1_哈法曼编码.png
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* @description: 黄金分割
* 一块金条切成两半，是需要花费和长度数值一样的铜板的。
* 比如 长度为20的 金条，不管切成长度多大的两半，都要花费20个铜 板。
* 一群人想整分整块金 条，怎么分最省铜板？
* 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分。
* 如果， 先把长 度60的金条分成10和50，花费60 再把长度50的金条分成20和30， 花费50 一共花费110铜板。
* 但是如果， 先把长度60的金条分成30和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板。
*
* 输入一个数组，返回分割的最小代价。
* @version: 1.0
*/
public class Code_38_TX_LessMoney {
public static int lessMoney(int[] arr) {
// 堆，小根堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
minHeap.add(arr[i]); // 如小根堆
}
int res = 0;
int cur = 0;
while (minHeap.size() > 1) {
cur = minHeap.poll() + minHeap.poll();
res += cur;
minHeap.add(cur);
}
return res;
}
// 小根堆比较器
public static class MinHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2; // < 0 o1 < o2 负数
}
}
//大根堆比较器
public static class MaxHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; // < o2 < o1
}
}
public static void main(String[] args) {
// solution
int[] arr = {6, 7, 8, 9};
System.out.println(lessMoney(arr));
int[] arrForHeap = {3, 5, 2, 7, 0, 1, 6, 4};
// 测试大根堆，小根堆，优先级队列（实际就是小根堆）
// min heap 默认情况下，PriorityQueue 就是小根堆
PriorityQueue<Integer> minQ1 = new PriorityQueue<>();
for (int i = 0; i < arrForHeap.length; i++) {
minQ1.add(arrForHeap[i]);
}
while (!minQ1.isEmpty()) {
System.out.print(minQ1.poll() + " ");
}
System.out.println();
// min heap use Comparator
System.out.println("min heap use Comparator");
PriorityQueue<Integer> minQ2 = new PriorityQueue<>(new MinHeapComparator());
for (int i = 0; i < arrForHeap.length; i++) {
minQ2.add(arrForHeap[i]);
}
while (!minQ2.isEmpty()) {
System.out.print(minQ2.poll() + " ");
}
System.out.println();
// max heap use Comparator
System.out.println("max heap use Comparator");
PriorityQueue<Integer> maxQ = new PriorityQueue<>(new MaxHeapComparator());
for (int i = 0; i < arrForHeap.length; i++) {
maxQ.add(arrForHeap[i]);
}
while (!maxQ.isEmpty()) {
System.out.print(maxQ.poll() + " ");
}
}
}
实例4
项目收益
输入： 参数1，正数数组costs
参数2，正数数组profits
参数3，正数k
参数4，正数m
costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
k表示你不能并行、只能串行的最多做k个项目
m表示你初始的资金
说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个 项目。
输出： 你最后获得的最大钱数。
贪心策略
每次从可选择的项目中，选取花费最小的几个；从这几个中选取收益最高的项目。
4_1.png
项目收益
4_2_项目收益.png
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code_39_IPO {
// 构建项目数据结构
public static class Node{
public int cost; // 花费
public int profits; // 利润
public Node(int cost, int profits){
this.cost = cost;
this.profits = profits;
}
}
// 最小花费，小根堆
public static class MinCostHeapComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.cost - o2.cost;
}
}
// 最大收益，大根堆
public static class MaxProfitsHeapComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o2.profits - o1.profits;
}
}
/**
*
* @param k 表示你不能并行、只能串行的最多做k个项目
* @param m 表示你初始的资金
* @param profits profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
* @param costs costs[i]表示i号项目的花
* @return 你最后获得的最大钱数。
*
* @Description 说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个 项目
*/
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(costs[i], profits[i]);
}
// 使用自定义的排序规则，即自定义的比较器，建立最小花费小根堆，最大收益大根堆
PriorityQueue<Node> minCostsHeap = new PriorityQueue<>(new MinCostHeapComparator());
PriorityQueue<Node> maxProfitsHeap = new PriorityQueue<>(new MaxProfitsHeapComparator());
for (int i = 0; i < nodes.length; i++) {
minCostsHeap.add(nodes[i]);
}
for (int i = 0; i < k; i++) { // 表示最多可以做 k 个项目
while (!minCostsHeap.isEmpty() && minCostsHeap.peek().cost <= m){ // 小根堆不为空且存在花费小于当前可用的金额
maxProfitsHeap.add(minCostsHeap.poll());
}
if (maxProfitsHeap.isEmpty()){
return m; // 大根堆为空，表示没有花费小于当前可用金额的项目进入大根堆
}
m += maxProfitsHeap.poll().profits;
}
return m;
}
}
实例5
会议时间安排
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目 的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面 是一个个具体的项目)，你来安排宣讲的日程，要求会 议室进行 的宣讲的场次最多。返回这个最多的宣讲场次。
贪心策略：每次选取会议结束时间最早的
5_1_会议选取方案.png
import java.util.Arrays;
import java.util.Comparator;
/**
* @description: 会议时间安排
*
* 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目 的宣讲。
*
* 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面 是一个个具体的项目)，
* 你来安排宣讲的日程，要求会 议室进行 的宣讲的场次最多。
* 返回这个最多的宣讲场次。
*
* 贪心策略：每次选取结束时间最早的
* @version: 1.0
*/
public class Code_40_TX_BestArrange {
// 构建会议数据结构
public static class Program{
public int startTime;
public int endTime;
public Program(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
}
// 会议比较器，按照项目结束时间进行排序，结束时间早放前
public static class ProgramComparator implements Comparator<Program> {
@Override
public int compare(Program o1, Program o2) {
return o1.endTime - o2.endTime;
}
}
/**
* @param programs 具体的会议信息
* @param curTime 当前时间
* @return 返回这个最多的宣讲场次
*/
public static int bestArrange(Program[] programs, int curTime){
if (programs == null || programs.length == 0) return 0;
Arrays.sort(programs, new ProgramComparator()); // 按照结束时间排序
int res = 0;
for (int i = 0; i < programs.length; i++) {
if (curTime <= programs[i].startTime){ // 可以进行的会议，其他都排除
res++;
curTime = programs[i].endTime; // 重置当前时间为会议结束时间
}
}
return res;
}
public static void main(String[] args) {
Program[] programs = new Program[9];
int[] startTime = {7, 7, 8, 9, 10, 10, 12, 14, 16};
int[] endTime = {9, 8, 11, 10, 12, 13, 15, 19, 17};
for (int i = 0; i < startTime.length; i++) {
programs[i] = new Program(startTime[i], endTime[i]);
}
int res = bestArrange(programs, 6);
System.out.println(res);
}
}
以上均为学习总结
网友评论