贪心算法
贪心算法是指，在对问题求解时，将整体的问题划分为一系列局部问题，对局部的问题求出最优解，再通过数学归纳法证明每一步贪心选择最终可以得到问题的一个整体的最优解。
问题一
给定一个字符串类型的数组strs;
找到一种拼接方式，可以使得将所有的字符串拼起来之后形成的字符串具有最低的字典序。
什么是字典序 ？将多个字符串同一位置的字符按照26个字母的顺序进行比对，得到的序列就是按照字典序排序的序列例如：
a < b; 按照字典序排序，即：a,b
aa < ab; 按照字典序排序，即：aa,ab
对于本题，贪心策略的本质在于比较上，如果贪心策略为：
贪心思路A:
如果有字符串a和字符串b
a < b
那么对于String[] strs = {a,b} 将字符串拼接后的字典序为 a+b
贪心思路A是错误的，因为可以找到反例：
String a = "b"
String b = "ba"
"b" < "ba"
如果对于贪心策略A正确，那么String strs = {"b","ba"} 将字符串拼接后的结果为"bba"
但是我们知道正确 的结果应该为"bab"
正确的比较部分的贪心策略为：
如果字符串a和字符串b有：
a.concat(b) < b.concat(a)
那么对于String[] strs = {a,b} 将字符串拼接后的字典序为 a+b
因为贪心算法的证明非常繁琐，这里不给予证明，代码如下：
import java.util.Arrays;
import java.util.Comparator;
public class LowestLexicographic {
public static class MyComparator implements Comparator<String> {
@Override
public int compare(String a,String b){
return (a + b).compareTo(b + a);
}
}
public static String getLowestLexicographic(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铜板;
输入一个数组，返回分割的最小代价
本题的思路为，将输入的数组放入至最小堆中，每次从最小堆中poll出两个数，构建出一个哈夫曼树,再将poll出的两个节点之和重新add至最小堆中，循环至最小堆的节点个数小于等于1为止，例如：
输入的数组为：{10,20,30,40}
将输入的数组依次添加到最小堆中，如下：
image.png
从最小堆中每次poll出两个节点，将两个节点相加构成一个新的节点，构建出哈夫曼树，同时将这个新构建的节点重新添加到最小堆中，重复上述步骤直至最小堆的节点个数小于等于1，新构建的节点和即为分割的最小代价：
本示例中构建出的哈夫曼树如下：
image.png
可以看出“新构建”出的节点和即为分割的最小代价，本示例中的分割最小代价为：190，本题代码如下：
import java.util.Comparator;
import java.util.PriorityQueue;
public class GetLessMoney {
public static int getLessMoney(int[] arr){
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MinheapComparator());
for(int i = 0;i < arr.length;i++){
priorityQueue.add(arr[i]);
}
int res = 0;
int cur = 0;
while(priorityQueue.size() > 1){
cur = priorityQueue.poll() + priorityQueue.poll();
priorityQueue.add(res);
res += cur;
}
return res;
}
public static class MinheapComparator implements Comparator<Integer>{
@Override
public int compare(Integer a,Integer b){
return a - b;
}
}
}
问题三
Leetcode 502：IPO问题
假设 力扣（LeetCode）即将开始其 IPO
为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本
由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目
帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目;
最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中
总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本
示例：
输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1]
输出: 4
解释:
由于你的初始资本为 0，你尽可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
来源：链接
解题思路：
首先创建一个Project类，Project类涵盖一个项目的cost花费，以及profits利润的信息。然后创建一个成本最小堆和利益最大堆；
image.png
首先，将所有的项目按照成本放入到最小堆，每次将目前的资金数和成本最小堆的堆顶做比较，如果资金数要比项目成本最小堆的堆顶还要大，那么将该项目poll到利益最大堆中，这样通过利益最大堆，就可以在k次范围内找到最大化资本的项目返回资金数。
import java.util.Comparator;
import java.util.PriorityQueue;
public class FindMaximizedCapital {
public static class MinHeapCompare implements Comparator<Project>{
@Override
public int compare(Project a,Project b){
return a.capital - b.capital;
}
}
public static class MaxHeapCompare implements Comparator<Project> {
@Override
public int compare(Project a,Project b){
return b.profits - a.profits;
}
}
public static class Project{
public int capital;
public int profits;
public Project(int capital,int profits){
this.capital = capital;
this.profits = profits;
}
}
public static int findMaximizedCapital(int k,int w,int[] profits,int[] capital){
Project[] projects = new Project[capital.length];
for(int i = 0;i < projects.length;i++){
projects[i] = new Project(capital[i],profits[i]);
}
PriorityQueue<Project> costMinHeap = new PriorityQueue<>(new MinHeapCompare());
PriorityQueue<Project> profitsMaxHeap = new PriorityQueue<>(new MaxHeapCompare());
for(int i = 0;i < projects.length;i++){
costMinHeap.add(projects[i]);
}
for(int i = 0;i < k;i++){
while(!costMinHeap.isEmpty() && costMinHeap.peek().capital <= w){
profitsMaxHeap.add(costMinHeap.poll());
}
if(profitsMaxHeap.isEmpty()){
return w;
}
w += profitsMaxHeap.poll().profits;
}
return w;
}
}
问题四
假设有一个流，它源源不断向外吐出数字，这些数字是没有规律的；
现在希望你设计一种数据结构，可以随时获取中位数
如果你用一个数组去接收流吐出的数字，那么收集流吐出的数字很简单，但是如果要获取中位数的话就要对数组进行一次排序，如果要求流每次吐出一个数字就获取一次中位数，那么就要频繁地对数组进行排序操作。解决的方法就是使用堆结构来解决这个问题：设计一个最大堆，和一个最小堆，每次流吐出数字的时候都和最大堆的堆顶作比较，如果小于等于最大堆堆顶就放入最大堆，如果大于最大堆的堆顶则放入最小堆。同时我们还需要保证最大堆的数据量不能比最小堆中的数据量大超过1，反之亦是如此,也就是要保持最大堆数据量N和最小堆的数据量M的关系为 |N-M| <= 1,如何保持这种关系呢？一旦破坏了这种关系的平衡，我们就让最大堆的顶部或者最小堆的顶部弹出，让这个最大的数字进入到最小堆里面，或者是让最小堆的最小的数字加到最大堆里面，如图示意：
image.png
假设这个数据流吐出的数字依次是 5->6->4->7->3->8->1
左侧为最大堆数字数量为N，右侧为最小堆数字数量为M,没有破坏过 |N-M| <= 1的规定，如果这个时候数据流吐出的数字为0，那么就要add到最大堆里面，这个时候N-M = 2破坏了两堆数量上的平衡，所以要把最大堆的堆顶弹入到最小堆中去，操作如下：
首先将数字0 add 到最大堆中
image.png
交换最大堆首尾数字
image.png
将最大堆末尾数字(5) add 到最小堆
image.png
接下来就是heapify操作了，对最大堆中的堆顶0进行heapify,首先要判断它的两个孩子谁更大，谁大跟谁交换，直到满足最大堆的结构为止
image.png
该数据结构的代码实现如下：
import java.util.Comparator;
import java.util.PriorityQueue;
public class MedianHolder {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new MaxHeapCompare());
private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinHeapCompare());
private void modify(){
if(maxHeap.si***Heap.size() + 2){
minHeap.add(maxHeap.poll());
}
if(minHeap.size() == maxHeap.size() + 2){
maxHeap.add(minHeap.poll());
}
}
public void add(int num){
if(maxHeap.isEmpty()){
maxHeap.add(num);
return;
}
if(num <= maxHeap.peek()){
maxHeap.add(num);
}else{
if(minHeap.isEmpty()){
minHeap.add(num);
return;
}
if(num < minHeap.peek()){
maxHeap.add(num);
}else{
minHeap.add(num);
}
}
modify();
}
public Integer getMedian(){
int maxHeapSize = maxHeap.size();
int minHeapSi***Heap.size();
if(maxHeapSize == 0 && minHeapSize == 0)
return null;
int maxHeapHead = maxHeap.peek();
int minHeapHead = minHeap.peek();
if(maxHeapSi***HeapSize){
return (maxHeapHead + minHeapHead)/2;
}
return maxHeapSize > minHeapSize ? maxHeapHead : minHeapHead;
}
public static class MinHeapCompare implements Comparator<Integer>{
@Override
public int compare(Integer a,Integer b){
return a - b;
}
}
public static class MaxHeapCompare implements Comparator<Integer>{
@Override
public int compare(Integer a,Integer b){
return b - a;
}
}
}
问题五
一些项目要占用一个会议室宣讲;
会议室不能同时容纳两个项目 的宣讲;
给你每一个项目开始的时间和结束的时间(数组，里面是一个个具体的项目)
你来安排宣讲的日程，要求会议室进行的宣讲的场次最多
返回：这个最多的宣讲场次
思路：
本题的贪心思路的设计应该是按照每场会议最早的结束时间来安排一天的宣讲顺序，示例：
image.png
如果按照每个会议结束的时间进行排序，并删除掉时间不允许的回忆的话，那么这一天的宣讲的项目应该是8点到10点的项目会议，11点到13点的项目会议，14点到17点的项目会议，即，最多的宣讲场次为3次。
本题的代码实现如下：
import java.util.Arrays;
import java.util.Comparator;
public class BestArrange {
public static class ProjectMeeting{
public int start;
public int end;
public ProjectMeeting(int start,int end){
this.start = start;
this.end = end;
}
}
public static class MyComparator implements Comparator<ProjectMeeting> {
@Override
public int compare(ProjectMeeting p1,ProjectMeeting p2){
return p1.end - p2.end;
}
}
public static int bestArrange(ProjectMeeting[] meetings,int currentTime){
Arrays.sort(meetings,new MyComparator());
int res = 0;
for(int i = 0;i < meetings.length;i++){
if(currentTime <= meetings[i].start){
res++;
currentTime = meetings[i].end;
}
}
return res;
}
}
投递快手等公司10个岗位 >