贪心算法
概念：
贪心算法（greedy algorithm [8] ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 [1] 。
题目：
字典序拼接字符串
题目描述:字符串数组，将各字符串拼接，使得最低词典顺序。如：“ab”,“cd”,“ef”,拼接成“abcdef”最小，其他方式都比它大。
思路：
-
首先按照首字母最小的顺序排序，b，ba，1,10不满足条件
-
两个字符串相加，谁小谁在前面的原则
- 直接用Array.sort，进行排序
- 直接用Priority队列
public static String lowestString1(String[] strs){
if(strs==null || str.length == 0){
return "";
}
Arrays.sort((strs,(o1,o2)-> (o1+o2).compareTo(o2+o1)));
StringBuffer str = new StringBuffer();
for(String s : strs){
strs.append(s);
}
return str.toString();
}
暴力递归：
思路：
- 对每个字符串都进行拼接，把所有可能的字符串放入TreeSet(Priority)中
- 首先先对字符串集合做一个循环，然后每一个循环的字符串后，删除该集合中的字符串，放入下一个该程序中，然后接着重复递归，直到没有该集合，则直接返回"",然后对返回的set做一个拼接
public static String lowestString2(String[] strs){
if(strs == null || strs.length == 0){
return "";
}
TreeSet<String> ans = process(strs);
return ans.pollFirst();
}
public static TreeSet<String> process(String[] strs){
TreeSet<String> ans = new TreeSet<>();
if(strs.length == 0){
//当前传入的数组长度为0，说明没有数组，
ans.add("");
return ans;
}
for(int i = 0;i < strs.length;i++){
String first = strs[i];
//返回删除当前字段的集合
String[] nexts = removeIndexString(strs,i);
//这个返回的是当前元素除外，所有后面元素拼接的总量set
TreeSet<String> next = process(nexts);
//然后和他进行拼接
for(String cur : next){
ans.add(first + cur);
}
}
return ans;
}
public static String[] removeIndexString(String[] arr,int index){
int N = arr.length;
String[] ans = new String[N-1];
int ansIndex = 0;
for(int i = 0;i < N;i++){
if(i != index){
ans[ansIndex++] = arr[i];
}
}
return ans;
}
public static String[] generateRandomStringArr(int arrLen,int strLen){
String[] strArr = new String[(int)Math.random()*arrLen];
for(int i = 0;i < strArr.length;i++){
strArr[i] = generateRandomString(strLen);
}
return strArr;
}
public static String generateRandomString(int strLen){
char[] ans = new char[(int) (Math.random()*strLen) + 1];
for(int i = 0;i < ans.length;i++){
int value = (int) (Math.random() * 10);
ans[i] = Math.random() <= 0.5?(char)('a' + value) : (char)('A' + value);
}
return String.valueOf(ans);
}
public static String[] copyStringArr(String[] arr){
String[] ans = new String[arr.length];
for(int i = 0;i < ans.length;i++){
ans[i] = String.valueOf(arr[i]);
}
return ans;
}
public static void main(String[] args){
int testTimes = 10000;
int strLen = 10;
int arrLen = 10;
for(int i = 0;i < testTimes; i++){
String[] test1 = generateRandomStringArr(arrLen,strLen);
String[] test2 = copyStringArr(test1);
String ans1 = lowerString1(test1);
String ans2 = lowerString2(test2);
if(!ans1.equals(ans2)){
System.out.println("Oops");
}
System.out.println("finish");
}
}
点灯问题
题目：给定一个字符串str，只由‘X’和‘.’两种字符构成。‘X’表示墙，不能放灯，也不需要点亮。‘.’表示居民点，可以放灯，需要点亮。如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮。返回如果点亮str中所有需要点亮的位置，至少需要几盏灯。
贪心：
思路：
-
X是墙，不需要放灯，.表示居民，可以放灯，也可以不放灯，但是所有的居民点必须被点亮
-
对当前字符串进行循环，i位置是x，跳过
-
当前i位置是.
- .i+1位置是x，则i位置点灯
- i+1位置是.则判断i+2位置
- 如果i+2位置是.,则i+1位置点灯，跳到i+3
- 如果i+2位置是x,则i+1位置点灯，跳到i+3、
-
因此，只要i+1位置是.,则直接在i+1位置点灯，ans+1，然后跳到i+3;只要i+1位置是;只要i位置是x，跳到i+1位置
public static int minLight1(String road){ int ans = 0; int i = 0; char[] roadArr = road.toCharArray(); while(i < roadArr.length){ //1.当前i位置是x if(roadArr[i] == 'x'){ i++; } else { ans++; //如果当前i到了尽头，则直接退出当前循环 if(i + 1 == roadArr.length){ break; } else { //当前i位置是. //当前i+1位置是x，则i位置点灯，同时跳到i+2位置 if(radArr[i + 1] == 'x'){ i = i + 2; } else { i = i + 3; } } } } return ans; }暴力递归：
思路：
- hashSet记录当前灯点亮的位置，index记录当前灯的位置放入hashSet中
public static int minLight2(String road){ if(road == null || road.length() == 0){ return 0; } return process(road.toCharArray(),0,new HashSet<>()); } public static int process(char[] str,int index,HashSet<Integer> lights){ //当前遍历的位置到了str的末尾 if(index == str.length){ for(int i = 0;i < str.length; i++){ if(str[i] != 'x'){ //判断当前点灯情况是否满足全部居民亮的情况，不满足，返回最大值 if(!lights.contains(i-1)&&!lights.contains(i)&&!lights.contains(i+1)){ return Integer.MAX_VALUE; } } } return ligth.size(); } else { //no 表示当前位置没有点灯 int no = process(str,index + 1,lights); //yes有两种情况，一种情况是墙，则直接赋最大值 int yes = Integer.MAX_VALUE; //第二种是.,则lights添加灯，然后传入process if(str[index] == '.'){ lights.add(index); yes = process(str,index+1,lights); lights.remove(index); } return Math.min(yes,no); } }公式：
思路：
- 两个x之间，数一下.的数量，然后除以3，向上取整
public static int minLight3(String road){ char[] str = road.toCharArray(); //cur 表示当前两个x之间的数量 int cur = 0; int light = 0; for(char c : str){ //遇到第一个x结束cur计数 //同时统计当前需要点灯的数量，cur+2是为了向上取整 if(c == 'x'){ light += (cur+2)/3; cur = 0; } else { cur++; } } //最后统计到末尾的情况 light += (cur+2)/3; return ligth; } public static String generateRandomString(int len){ char[] charArr = new char[(int)(Math.random() * len)]; for(int i = 0;i<charArr.length;i++){ charArr[i] = Math.random() < 0.5 ? 'x' : '.'; } return String.valueOf(charArr); } public static void main(String[] args){ int testTimes = 1000; int len = 10; for(int i = 0;i < testTimes;i++){ String test = generateRandomString(len); int a1 = minLight1(test); int a2 = minLight2(test); int a3 = minLight3(test); if(a1 != a2 || a2 != a3){ System.out.println("Oops"); System.out.println(test); } } System.out.println("finish"); }
分割金条
题目： 一块金条切成两半，是需要花费和长度数值一样的铜板，比如长度为20的金条，不管怎么切都要花费20个铜板，一群人想整分整块金条，怎么分最省铜板? 例如，给定数组{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 lessMoney1(int[] arr){
PriorityQueue<Integer> pq = new Priority<Queue>();
for(int i : arr){
pq.add(i);
}
int ans = 0;
int p1 = 0;
int p2 = 0;
while(pq.size() > 1){
p1 = pq.poll();
p2 = pq.poll();
ans += p1+p2;
pq.add(p1+p2);
}
return ans;
}
递归：
思路：
- 每种可能都尝试一边
public static int lessMoney2(int[] arr){
if(arr == null||arr.length == 0){
return 0;
}
return process(arr,0);
}
public static int process(int[] arr,int pre){
if(arr.length == 1){
return pre;
}
int ans = Integer.MAX_VALUE;
for(int i = 0;i< arr.length;i++){
for(int j = i+1;j<arr.length;j++){
int[] newArr = copyAndMergeTwo(arr,i,j);
ans = Math.min(ans,process(newArr,pre+arr[i] + arr[j]));
}
}
return ans;
}
public static int[] copyAndMergeTwo(int[] arr,int i,int j){
int[] ans = new int[arr.length-1];
int ansi = 0;
for(int arri=0;arri<arr.length;arri++){
if(arri != i && arri != j){
ans[ansi++] = arr[arri];
}
}
ans[ansi] = arr[i] + arr[j];
return ans;
}
会议室宣讲
题目：
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲，给你每一个项目开始的时间和结束的时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多，返回最多的宣讲场次
贪心：
思路：
- 按每个项目的结束时间做排序，每次都挑选能最早结束的时间会议，返回这个会议数量
public static class Program{
public int start;
public int end;
public Program(int start,int end){
this.start = start;
this.end = end;
}
}
public static int bestArrange2(Program[] programs){
Arrays.sort(programs,(o1,o2) -> o1.end - o2.end);
int ans = 0;
int timeLine = 0;
for(int i = 0;i<programs.length;i++){
if(timeLine <= programs[i].start){
ans++;
timeLine = programs[i].end;
}
}
return ans;
}
递归：
思路：
- 遍历每个会议，找出最小值
public static int bestArrange3(Program[] programs){
if(programs.length == 0|| programs == null){
return 0;
}
return process(programs,0,0);
}
public static int process(Program[] programs,intt done,int timeLine){
if(programs.length == 0){
return done;
}
int max = done;
for(int i = 0;i<programs.length;i++){
if(programs[i].start >= timeLine){
Program[] next = copyButExcept(programs,i);
max = Math.max(max,process(next,done+1,programs[i].end));
}
}
return max;
}
项目收益
题目：
输入：正数数组costs正数数组profits正数k
正数k含义：能串行的最多做k个项目
costs[i] 表示 i 号项目的花费
profits[i] 表示 i 号项目在扣除花费之后还能挣到的钱(利润)
w表示你初始的资金
说明：
你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出：你最后获得的最大钱数。
贪心：
思路：
- 每次都选择能做项目当中的最大收益的项目，然后要么k次做完，要么本金不够，最后返回最大钱数
- 可以用两个队列，一个队列放最小的花费的项目minCost，一个队列存放最大的利润
public static class Program{
public int p;
public int c;
public Program(int p , int c){
this.p = p;
this.c = c;
}
}
public static int findMaximizedCapital(int K,int W,int[] profits,int[] Capital){
PriorityQueue<Program> minCost = new Priority<>((o1,o2) -> o1.c-o2.c);
PriorityQueue<Program> maxPro = new Priority<>((o1,o2) -> o2.p - o1.p);
//1.minCost塞满
for(int i = 0;i < Profits.length;i++){
minCost.add(new Program(Profits[i],Capital[i]));
}
//对k次项目做循环
for(int i = 0;i < K;i++){
//往mmaxPro里放满足条件能够花费的项目
while(!minCost.isEmpty() minCost.peek().c <= W){
maxPro.add(minCost.poll());
}
//表示当前项目没有能够消费的
if(maxPro.isEmpty()){
break;
}
W += maxPro.poll().p;
}
return W;
}