左神算法笔记之贪心算法和暴力递归

admin管理员组

文章数量:1530022

贪心算法

一、安排会议

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目），你来安排宣讲的日程，要求会议室进行的宣讲次数最多，返回这个最多的宣讲次数。

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));
}

本文标签： 递归神算贪心算法暴力