左神算法-基础06-前缀树&贪心算法
介绍前缀树
何为前缀树? 如何生成前缀树?
例子:
一个字符串类型的数组arr1，另一个字符串类型的数组arr2。
arr2中有哪些字符，是arr1中出现的？请打印。
arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印。
arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 arr2中出现次数最大的前缀。
public static class TrieNode {
public int pass;
public int end;
//HashMap<Char, Node> nexts
public TrieNode[] nexts;
public TrieNode() {
pass = 0;
end = 0;
//nexts[0] == null 没有走向‘a’的路
//nexts[0] ！= null 有走向‘a’的路
//nexts[25] ！= null 有走向‘z’的路
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;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
node.pass++;
}
node.end++;
}
public void delete(String word) {
if (search(word) == 0) {
return;
}
char[] chs = word.toCharArray();
TrieNode node = root;
int index= 0;
for (int i = 0; i < chs.length; i++) {
index = chs[i] - 'a';
if (--node.nexts[index].pass == 0) {
node.nexts[index] = null;
return;
}
node = node.nexts[index];
}
node.end--;
}
public int search(String word) {
if (word == null) {
return 0;
}
char[] chs = word.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.end;
}
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.pass;
}
}
贪心算法
在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。
也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优 -?-> 整体最优
贪心算法的在笔试时的解题套路
-
实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
-
脑补出贪心策略A、贪心策略B、贪心策略C...
-
用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
-
不要去纠结贪心策略的证明
从头到尾展示最正统的贪心策略求解过程
例子：
给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的字符串具有最小的字典序。
(证明贪心策略可能是件非常腌心的事情。平时当然推荐你搞清楚所有的来龙去脉，但是笔试时用对数器的方式！)
public static class MyComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
return (o1 + o2).compareTo(o2 + o1);
}
}
public static String lowestString(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
Arrays.sort(strs, new MyComparator());
String res = "";
for (int i = 0; i < strs.length; i++) {
res += strs[i];
}
return res;
}
贪心策略在实现时，经常使用到的技巧：
-
根据某标准建立一个比较器来排序
-
根据某标准建立一个比较器来组成堆
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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铜板。
输入一个数组，返回分割的最小代价。
public static int lastMoney(int[] arr) {
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。
返回这个最多的宣讲场次。
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> {//比较器类型
@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 result = 0;
for (int i = 0; i < programs.length; i++) {
if (start <= programs[i].start) {
result++;
start = programs[i].end;
}
}
return result;
}
输入：
正数数组costs
正数数组profits
正数k
正数m
含义：
costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
k表示你只能串行的最多做k个项目
m表示你初始的资金
说明：
你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出：
你最后获得的最大钱数。
public static class Node {
public int profit;
public int cost;
public Node(int profit, int cost) {
this.profit = profit;
this.cost = cost;
}
}
public static class MinCostComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.cost - o2.cost;
}
}
public static class MaxCostComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o2.profit - o1.profit;
}
}
public static int findMaximizedCapital(int k, int W, 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> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxCostComparator());
for (Node node : nodes) {
minCostQ.add(node);
}
for (int i = 0; i < k; i++) {//进行k轮
while (!minCostQ.isEmpty() && minCostQ.peek().cost <= W) {
maxProfitQ.add(minCostQ.poll());
}
if (maxProfitQ.isEmpty()) {
return W;
}
W += maxProfitQ.poll().profit;
}
return W;
}
一个数据流中，随时可以取得中位数
public static class MedianHolder {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapComparator());
private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinHeapComparator());
private void modifyTwoHeapsSize() {
if (this.maxHeap.size() == this.minHeap.size() + 2) {
this.minHeap.add(this.maxHeap.poll());
}
if (this.minHeap.size() == this.maxHeap.size() + 2) {
this.maxHeap.add(this.minHeap.poll());
}
}
public void addNumber(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
modifyTwoHeapsSize();
}
public Integer getMedian() {
int maxHeapSize = this.maxHeap.size();
int minHeapSize = this.minHeap.size();
if (maxHeapSize + minHeapSize == 0) {
return null;
}
Integer maxHeapHead = this.maxHeap.peek();
Integer minHeapHead = this.minHeap.peek();
if (((maxHeapSize + minHeapSize) & 1) == 0) {
return (maxHeapHead + minHeapHead) / 2;
}
return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
}
}
public static class MaxHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static class MinHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}