左神算法课笔记（七）贪心算法和暴力递归
public static int win1(int[] arr){
if(arr==null || arr.length < 1) return 0;
return Math.max(f(arr, 0, arr.length-1), s(arr, 0, arr.length-1));
}
public static int f(arr, L, R){
if(L==R) {
return arr[L];
}
return Math.max(arr[L] + s(arr, L+1, R), arr[R] + s(arr, L, R-1));
}
public static int s(arr, L, R){
if(L==R){
return 0;
}
return Math.min(f(arr, L+1, R), f(arr, L, R-1));
}
一、贪心算法
1、概念：
贪心算法可以看作基于某一标准进行排序
概念：在某一个标准下，优先考虑最满足标准的样本，最后考虑不满足标准的样本，最终得到一个答案的算法，叫做贪心算法
贪心算法不考虑整体最优，作出的是在某种意义上的局部最优解
【会议问题】一个项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给定一堆项目的开始和结束时间（数组），安排宣讲的日程，要求会议室进行的宣讲场次最多，返回这个最多场次。
解题思路：按照会议结束时间对所有项目进行排序，并逐个检查。维护一个timepoint变量记录当前可安排会议室的最早空闲时间。若某次会议的开始时间等于或晚于timepoint，则将该会议纳入安排，并更新timepoint为这场会议的结束时间。
public static class Program{
public int start;
public int end;
public Program(int s, int e){
this.start = s;
this.end = e;
}
}
public static ProgramComparator implements Comparator<Program>{
@Override
public int compare(Program p1, Program p2){
return p1.end - p2.end;
}
}
public static int bestArrage(Program[] programs){
Arrays.sort(programs, new ProgramComparator());
int res = 0;
int timePoint = 0;
for(int i = 0; i < programs.length; i++){
if(timePoint <= programs[i].start){
res += 1;
timePoint = programs[i].end;
}
}
return res;
}
2、贪心算法在笔试时的解题套路
1、实现一个不依靠贪心算法的解法X，可以用最暴力的尝试
2、脑补出贪心策略A、B、C....
3、用解法X和对数器，去验证每一个贪心策略，用实验的方法得知哪个贪心策略正确
4、不用纠结贪心策略的证明
【字符串拼接】
把字符串数组里的所有字符拼接起来，得到字典序最小的字符串
public static class MyComparator implements Comparator<String>{
@Override
public int compare(String s1, String s2){
return (a + b).compartTo(b + a);
}
}
public static String lowerstString(String[] strs){
if(strs==null || strs.length<1) {
return "";
}
Arrays.sort(strs, new MyComparator());
String res = "";
for(int i = 0; i < strs.length; i++){
res + strs[i];
}
return res;
}
3、贪心策略经常使用技巧
1、根据某一个标准建立一个比较器排序
2、根据某一个标准建立一个比较器来组成堆
【切金条】
一根金条切成两半，需要花费和长度一样的铜板，比如长度为20的金条，不管切成多大的两半，都小于花费20铜板，一群人想要整分整块金条，怎么切最省？
例：给定数组[10, 20, 30]，金条长度60，如何切满足第一个人要10，第二个人要20，第三个人要30
解题思路：对于第i个人来说，要花费最少，就尽可能地切小的金条，因此对于其之前的人来说，每次都要往大了切；即从叶节点构建树，非叶子节点即为花销
public static int lessMoney(int[] arr){
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for(Integer i: arr){
pQ.add(i);
}
int sum = 0;
int cur = 0;
while(pQ.size()>1){ //每次弹出两个，因此pQ的size必须大于1
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
【k个项目最大利润】
输入：
正数数组Costs
正数数组profits
正数k 最多能做多少个项目
正数m 初始启动资金
例：m=1，k=4时最大利润多少？
解法：先建立小根堆，以cost作为排序项，然后再建立大根堆，以profit作为排序项，弹出所有满足cost条件的项目再放入profit大根堆中
public static class Node{
public int p;
public int c;
public class Node(int p, int c){
this.p = p;
this.c = c;
}
}
public static MinComparator implements Comparator<Node>{
@Override
public int compare(Node n1, Node n2){
return n1.c - n2.c;
}
}
public static MaxComparator implements Comparator<Node>{
@Override
public int compare(Node n1, Node n2){
return n2.p - n1.p;
}
}
public static int getMaxProfit(int[] costs, int[] profits, int k, int m){
PriorityQueue<Integer> minPQ = new LinkedList<>(new MinComparator());
PriorityQueue<Integer> maxPQ = new LinkedList<>(new MaxComparator());
for(int i = 0; i < costs.length; i++){
minPQ.add(new Node(costs[i], profits[i]));
}
for(int i = 0; i < k; i++){ //进行k轮，最多能做几个项目
while(minPQ.peek().c <= m && !minPQ.isEmpty()){ //力所能及全部解锁
maxPQ.add(minPQ.poll());
}
if(maxPQ.isEmpty()){
return m;
}
m += maxPQ.poll().p;
}
return m;
}
【N皇后问题】
N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列、也不在同一条斜线上
给定一个整数，返回N皇后的摆法有多少种？
public static int num1(int n){
if(n<1) return 0;
int[] record = new int[n];
return process(0, record, n);
}
// record[0,...,i-1]的皇后，一定不共列、不共行、不共斜线
// 目前来到了第i行
// record[0,...,i-1]表示之前的行，放的皇后的位置
// n代表整体多少行
public static int process(int i, int[] record, int n){
if(i==n) return 1;
int res = 0;
for(int j=0; j<n; j++){ //当前在i行，尝试所有的列
// 当前i行的皇后，放在j列，会不会和之前(0,...,i-1)的皇后不共列、不共行或者不共斜线
// 如果是，认为有效
// 如果不是，认为无效
if(isValid(i, j, record)){
record[i] = j;
res += process(i+1, record, n);
}
}
return res;
}
// record[0,...,i-1]需要看，record[i..]不需要看
// 返回i行皇后，放在了j列，是否有效，能不能放，还没放
public static boolean isValid(int i, int j, int[] record){
for(int k = 0; k <= i; k++){
if(j==record[k]||Math.abs(i-k)==Math.abs(record[k]-j)){ //共列或者共斜线，就不满足
return false;
}
}
return true;
}
二、暴力递归
1、暴力递归技巧
暴力递归就是尝试
1、把问题转化为规模缩小的同类问题的子问题
2、有明确的不需要的继续进行递归的条件（Base case）
3、有当得到了子问题后的决策过程（类似于树型dp中自己要做处理的一部分）
4、不记录每一个子问题的解
【汉罗塔问题】
分析：假设左为from，中为to，右为other，设函数为P(i, from, to, other)
左 中 右
from to other
假设i位置圆盘要从from移动到to
1）对于 n~i-1 位置的圆盘来说， 它们要先从from移动到other的位置，P(i-1, from, other, to)
2) 对于 i 位置的圆盘来说，它要从from移动到to的位置，P(i, from, to, other)
3) 对于 n~i-1 位置的圆盘来说，它们要从from再移动到to的位置，P(i-1, other, to, from)
public static void hanoi(int n){
if(n>0){
// 注意，汉罗塔的顺序是从n -> 1， 1在最底层
func(n, "左", "中", "右")
}
}
public static void func(i, String from, String to, String other){
if(i==1) {
System.out.println("Moving 1 from"+ start + "to" + end);
}
func(i-1, from, other, to);
System.out.println("Moving" + i + "from" + start + "to" + end);
func(i-1, other, to, from);
}
【打印字符串的子序列】
打印一个字符串的子序列，包括空字符
如"abcd"，打印"a" "ab" "abc" "abcd" "b" "bc" "bcd" "c" "cd" "d" ""
分析：
1）走到 i 位置，两条路，选和不选
2）res为之前选择的路形成的列表
3）i走到 str.length的位置，打印res (base case)
public static void function(String str){
char[] chs = str.toCharArray();
process(chs, 0, new ArrayList<Character>);
}
public static void process(char[] str, i, List<Charater> res){
if(i==str.length){
printList(res);
}
// 选择str[i]的路
List<Charater> reskeep = copyList(res);
resKeep.add(str[i]);
process(resKeep, i+1, res);
// 没选择str[i]的路
List<Charater> resNokeep = copyList(res);
process(resNokeep, i+1, res);
}
public static List<Charater> copyList(ist<Charater> res){
ArrayList<Charater> copyL = new ArrayList<>();
for(Charater c: res){
copyL.add(c);
}
return copyL;
}
public static void printList(List<Character> res){
String str = "";
for(Character c : res){
str += c;
}
System.out.println(str);
}
【打印一个字符串的全部排列】
public static ArrayList<String> permutation(String str){
if(str==null || str.length<1) return new ArrayList<String>();
char[] chs = str.toCharArray();
return process(0, chs, new ArrayList<String>());
}
public static ArrayList<String> process(int i, char[] str, ArrayList<String>() res){
if(i==str.length){
res.add(String.valueOf(str));
}
for(int j=i; j<str.length; j++){ //j从i出发，往后所有的j都可以来到j位置
swap(str, i, j); //交换i，j
process(i+1, str, res); // 对i+1的位置周而复始
swap(str, i ,j); //再交换回来
}
return res;
}
【打印一个字符串的全部排列，要求不重复打印】
涉及一个概念：
分支限界：提前杀死不可能的路
public static ArrayList<String> permutation(String str){
if(str==null || str.length<1) return new ArrayList<String>();
char[] chs = str.toCharArray();
return process(0, chs, new ArrayList<String>());
}
public static ArrayList<String> process(int i, char[] str, ArrayList<String>() res){
if(i==str.length){
res.add(String.valueOf(str));
}
boolean[] visit = new boolean[26];
for(int j=i; j<str.length; j++){ //j从i出发，往后所有的j都可以来到j位置
if(!visit[j]-'a'){
visit[j] = true;
swap(str, i, j); //交换i，j
process(i+1, str, res); // 对i+1的位置周而复始
swap(str, i ,j); //再交换回来
}
}
return res;
}
【返回获胜者分数】
给定一个整型数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家只能拿走最左或者最右的纸牌，玩家A和玩家B都聪明绝顶，请返回获胜者最后的分数
举例：arr[1, 2, 100, 4]
分析：
1）先手拿的人拿的最大的分数为，选择最左或者最后的牌得到的分数与后手拿的分数的总和，选择分数最大的那一个
2）后手拿的人的最大分数为，选择最左或者最后的牌得到的分数与后手拿的分数的总和，但后手只能拿到较小的
假设先手函数为 f(arr, L, R), 后手函数为s(arr, L, R)
则有
先手情况：int f(arr, L, R) , 在arr的L~R范围上返回最大分数 base case: if(L==R) return arr[L]; 先拿左侧：int left = arr[L] + s(arr, L+1, R); s为后手函数 先拿右侧：int right = arr[R] + s(arr, L, R+1); 最后选择 max(left, right) 后手情况：int s(arr, L, R) base case: if(L==R) return 0; //只有一个数，必然被先手的人拿走 不止一个数： 变为先手，如果别人拿走L，变成f(arr, L+1, R)， 如果别人拿走R，变成f(arr, L, R-1)， 但是该过程由对方决定，因此后手方只能拿到最不利的情况 最后选择 min(left, right)
【逆序栈】
给一个栈，逆序这个栈，不能申请额外的数据结构，只能使用递归函数
分析：
1） 先准备一个函数，能够返回栈底的值，并把上面的值押回去
2） 再准备一个函数，栈空的时候返回栈
public static int popLast(Stack<Integer> stack){
int result = stack.pop();
if(!stack.isEmpty()){
int last = popLast(stack);
stack.push(result);
return last;
} else {
return result;
}
}
例：第一轮，弹出1，压回3，2
3 last =1 push 3 return 1
2 last =1 push 2 return 1
1
public static void reverse(Stack<Integer> stack){
if(stack.isEmpty()){
return;
} else {
int result = popLast(stack);
reverse(stack);
stack.push(result);
}
}
例：第一轮，弹出1，然后往下走，直到第三轮，弹出3，往栈里压
【字符串转化】
规定1和A对应，2和B对应，....，26和Z对应
那么一个数字字符串，比如"111"，就可以转化为"AAA"、"AK"、"KA"，给定一个只有数字字符组成的字符串，返回有多少种转化结果
分析：
将问题分割成假设0~i-1已经决定好了，i往后可以自由转化，问最终有多少种结果
情况一：i为0字符的时候，后面没法转化，如110111，0前面的11决定为K或者AA，则0与01都没法转换，返回0
情况二：i为数字1~9，存在两种决定：
决定1：i直接转换为对应的英文字符
决定2：若i不是最后一位，i能与后续的数字组合起来转换，但i与i+1的组合不能超过26，超过26则无法转换
base case: i走超过数组长度时，证明可以完成转换，返回1
public static int transfer(String str){
char[] chs = str.toCharArray();
return process(0, chs);
}
public static int process(int i, char[] str){
if(i==str.length){
return 1;
}
if(str[i]=="0"){
return 0;
}
int res = process(i+1, str);
if(i+1<arr.length && ((int)str[i]*10+(int)str[i+1])<=26){
res += process(i+2 chs);
}
return res;
}
【背包问题】
给定两个长度都为N的数组，weights和values，weights[i]和values[i] 分别代表i号物品的重量和价值。给一个正数bag，表示一个载重为bag的袋子，其装的物品的总重量不能超过bag，请问能装下最多的价值是多少？
分析：
可能性：假设0~i-1的货物选择已经确定，i...自由选择，两种决定
1、判断是否超过剩余的承重，若超过，则不能选择；
2、若未超过承重，则可以选择要不要把i加入到袋子中
返回两种可能性的最大值即可
base case：
1、i的大小超出数组长度
2、bag剩余重量为0，没有办法再装更多
public static int maxValue(int[] weights, int[] values, int bag){
return process(0, weights, values, bag);
}
public static int process(int i, int[] weights, int[] values, int bag){
if(i==weights.length || bag==0){
return 0;
}
int res = 0;
if(weights[i]<=bag){
res += Math.max(values[i]+process(i+1, weights, values, bag-weights[i]),
process(i+1, weights, values, bag));
} else {
res += process(i+1, weights, values, bag);
}
return res;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
12
0- 0
已为社区贡献1条内容
所有评论(0)