admin管理员组文章数量:1565361
贪心算法
一、安排会议
一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目的宣讲。给你每个项目开始的时间和结束的时间(给你一个数组,里面是一个个具体的项目),你来安排宣讲的日程,要求会议室进行的宣讲次数最多,返回这个最多的宣讲次数。
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 timePoint){
//按会议结束时间从早到晚来排序
Arrays.sort(programs, new ProgramComparator());
int result = 0;
//从左往右依次遍历所有会议来选择可以安排的场次
for(int i = 0; i < programs.length; i++){
//如果当前结束时间点在下一个项目时间开始或开始之前
if(timePoint <= programs[i].start){
//就安排这场,并且安排场次数++
result++;
//然后结束时间点来到这个场次的结束时间,继续遍历
timePoint = programs[i].end;
}
}
return result;
}
二、分金条问题(哈夫曼编码问题:求非叶子节点值的最小累加和问题)
分金条,为得到目标部分的金条,如原本有一条60质量的金条,要分成[10,20,30]的部分,每次切割都要金条质量相等的铜板数,如切60质量的金条要花费60铜板,求怎么切花费最少?
//利用小根堆,每次选最小的两个代价来结合,然后向上求出每次切割的最小代价
public static int lessMoney(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;
}
三、选择利润最大项目问题
最多只能串行做K个项目,有m的初始资金,项目包含consts[i]花费和profit[i]利润,求赚的最大钱数。
//花费3 利润1的项目 做了之后 一共返回4
//小根堆存放:花费从小到大的项目
//大根堆存放:利润从大到小的项目
public static class Node{
public int p;//利润
public int c;//花费
public Node(int p, int c){
this.p = p;
this.c = c;
}
}
//花费小根堆比较器
public static class MinCostComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2){
return o1.c - o2.c;
}
}
//利润大根堆比较器
public static class MaxProfitProfitComparator implements Comparator<Node>{
@override
public int compare(Node o1, Node o2){
return o2.p - o1.p;
}
}
//k是可选项目数,W的本金
public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital){
PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
//把所有项目放进花费小根堆,锁住
for(int i = 0; i < Profits.length; i++){
minCostQ.add(new Node(Profits[i],captical[i]));
}
for(int i = 0; i < k; i++){
//如果小根堆不为空,并且小根堆里有项目的花费小于本金,都弹出并加入利润大根堆里
while(!minCostQ.isEmpty() && minCostQ.peek().c <= W){
maxProfitQ.add(minCostQ.poll());
}
//当做完了解锁到大根堆里的项目但遍历还没完,就是小根堆里的项目已经永远无法够钱解锁了,就直接返回W
if(maxProfitQ.isEmpty()){
return W;
}
//w不断累加大根堆里利润最高的项目的利润
W += maxProfitQ.poll().p;
}
return W;
}
暴力递归
一、汉诺塔问题
打印n层汉诺塔从最左移动到最右的全部过程
//尝试保证局部是正确的,那么递归出来的整体大概率也是正确的
public static void hanoi(int n){
if(n > 0){
func(n,"左","右","中");
}
}
//1~i圆盘目标是from -> to , other是另外一个
//分三步
public static void func(int i, String start, String end, String other){
if(i == 1){
System.out.println("Move 1 from " + start + " to " + end);
} else {
//因为只能小的在大的上面,所以先把i-1前的圆盘放到other
func(i - 1, start, other, end);
//再将i从start移到end,打印
System.out.println("Move " + i + " from " + start + " to " + end);
//最后将other的圆盘全部移到end上
func(i - 1, other, end, start);
}
}
二、打印一个字符串的全部子序列,包含空字符串
把字符串每个字符要和不要的情况组成一棵树:
//字符串从左往右每个字符要跟不要做决策
//分割字符串
public static void printAllSubsquence(String str){
char[] chs = str.toCharArray();
process(chs, 0, new ArrayList<Character>());
}
//当前来到i位置时,走要跟不要两条路
//res是之前的选择所形成的字符串
public static void process(char[] str,int i; List<Character> res){
//i等于字符串长度时,就表示其中一种情况出现了,打印
if(i == str.length){
printList(res);
return;
}
//要当前i位置字符的情况
List<Character> resKeep = copyList(res);
//添加i位置字符到keep里
resKeep.add(str[i]);
//走要的深度遍历
process(str, i+1 , resKeep);
//不要当前i位置字符的情况
List<Character> resNoInclude = copyList(res);
//走不要的深度遍历
process(str, i+1, resNoInclude);
}
public static void printList(List<Character> res){
for(int i = 0; i < res.size(); i++){
System.out.print(res.get(i));
}
}
三、打印一个字符串的全部排列(去重版本)
public static ArrayList<String> Permutation(String str){
//res存所有存放结果
ArrayList<String> res = new ArrayList<>();
if(str == null || str.length() == 0){
return res;
}
char[] chs = str.toCharArray();
process(chs, 0, res);
return res;
}
//str[i...]范围上,所有的字符都可以在i位置上,比如abcd,有四个位置,第一次大循环控制第一个位置上的字母是什么,然后确定第一个位置的字母后,开始递归,第二个位置上的字母从剩下的字母里挑,然后不断深度递归确定后面位置的字母...
//str[0...i-1]范围上是这一个深度遍历,遍历到i位置,之前位置确定的字符串
public static void process(char[] str, int i, ArrayList<String> res){
if(i == str.length){
res.add(String.valueOf(str));
}//base case:当遍历到字符串长度,表示找到一种排列,将其加入res
//记录26个字母是否试过的情况,,visit[0]代表a是否被试过
boolean[] visit = new boolean[26];
//j从i位置开始,在i位置有str.length - j种交换可能
for(int j = i; j < str.length; j++){
//如果在该种可能下str[j]字母没被试过
if(!visit[str[j] - 'a']){
//先标记这次试过了
visit[str[j] - 'a'] = true;
//交换i和j的位置
swap(str, i, j);
//走该次交换下字符排列的深度
process(str, i+1, res);
//走完深度回来交换回来,为下一个交换做准备
swap(str, i, j);
}
}
}
public static void swap(char[] chs, int i, int j){
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
四、手牌游戏
public static int win1(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
//返回先手玩家和后手玩家获胜的那个
return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
//先手玩家
public static int f(int[] arr, int i, int j){
//base case:还剩一张卡牌时,先手玩家选择
if(i == j){
return arr[i];
}
//返回先手玩家拿最左边牌和最右边牌获得数值更大的那个
return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
//后手玩家
public static int s(int[] arr, int i, int j){
//base case:还剩一张卡牌时,后手玩家没得选,只能给先手玩家选
if(i == j){
return 0;
}
//当先手选完后,后手玩家就变成了先手
//因为后手玩家的选择是先手玩家决定的,所以先手玩家选了最优选择后,后手玩家的选择就变成最差的,所以是返回后手玩家拿最左边牌和最右边牌获得数值更小的那个
return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}
五、逆序栈
给你一个栈,请你逆序这个栈,不能申请额外的数据结构,只能使用递归函数。如何实现?
//反转栈
public static void reverse(Stack<Integer> stack){
if(stack.isEmpty()){
return;
}
int i = f(stack);
reverse(stack);
stack.push(i);
}
//将栈底元素弹出,仍保持栈结构
public static int f(Stack<Integer> stack){
int result = stack.pop();
if(stack.isEmpty()){
return result;
} else {
int last = f(stack);
stack.push(result);
return last;
}
}
六、数字字符转化成字符串
// i之前的位置,如何转化已经做过决定了
// i... 有多少种转化结果
public static int process(char[] str, int i){
//没有遇见不可转换的字符并遍历来到字符串长度末尾,发现一种转化结果
if(i == str.length){
return 1;
}
if(str[i] == '0'){
return 0;
}
//i为1的结果
if(str[i] == '1'){
int res = process(str, i + 1);// i自己作为单独的部分,后续有多少种方法
if(i + 1 < str.length){
res += process(str, i + 2);// (i和i+1)作为组合的部分,后续有多少种方法
}
return res;
}
//i作为2的结果
if(str[i] == '2'){
int res = process(str, i + 1);// i自己作为单独部分,后续有多少种方法
//(i和i+1)作为单独的部分并且没有超过26,后续有多少种方法
if(i + 1 < str.length && (str[i + 1] >= '0' && str[i+1] <= '6')){
res += process(str, i+2);
}
return res;
}
// str[i] == '3'~'9'时,只有i作为单独部分
return process(str, i+1);
}
七、袋子装货物问题
// i... 的货物自由选择,形成的最大价值返回
// 重量永远不要超过bag
// 之前做的决定,所达到的重量,alreadyweight
public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag){
if(alreadyweight > bag){
return 0;
}
if(i == weights.length){
return 0;
}
//返回要i号货物和不要i号货物更优的那个选择
return Math.max(
process1(weights, values, i + 1, alreadyweight, bag),
values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
}
版权声明:本文标题:左神算法笔记之贪心算法和暴力递归 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1726763937a1083386.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论