• 【算法训练营】 - ⑨ 贪心算法


    贪心算法

    1. 最自然智慧的算法
    2. 用一种局部最功利的标准,总是做出在当前看来是最好的选择
    3. 难点在于证明局部最功利的标准可以得到全局最优解
    4. 对于贪心算法的学习主要以增加阅历和经验为主

    贪心算法求解的标准过程

    1. 分析业务
    2. 根据业务逻辑找到不同的贪心策略
    3. 对于能举出反例的策略直接跳过,不能举出反例的策略要证明有效性。这往往是特别困难的,要求数学能力很高且不具有统一的技巧性

    贪心算法的在笔试时的解题套路

    1. 实现一个不依靠贪心策略的解法X,可以用最暴力的尝试
    2. 脑补出贪心策略A、贪心策略B、贪心策略C…
    3. 用解法X和对数器,去验证每一个贪心策略,用实验的方式得知哪个贪心策略正确
    4. 不要去纠结贪心策略的证明

    贪心策略在实现中,经常使用的技巧 - 堆 & 排序

    1. 根据某标准建立比较器来进行排序
    2. 根据某标准建立比较器来组成堆

    题目

    安排会议

    package class14;
    
    import java.util.Arrays;
    import java.util.Comparator;
    
    public class Code03_BestArrange {
    
    	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 bestArrange1(Program[] programs) {
    		if (programs == null || programs.length == 0) {
    			return 0;
    		}
    		return process(programs, 0, 0);
    	}
    
    	// 还剩下的会议都放在programs里
    	// done之前已经安排了多少会议的数量
    	// timeLine目前来到的时间点是什么
    	
    	// 目前来到timeLine的时间点,已经安排了done多的会议,剩下的会议programs可以自由安排
    	// 返回能安排的最多会议数量
    	public static int process(Program[] programs, int 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;
    	}
    
    	public static Program[] copyButExcept(Program[] programs, int i) {
    		Program[] ans = new Program[programs.length - 1];
    		int index = 0;
    		for (int k = 0; k < programs.length; k++) {
    			if (k != i) {
    				ans[index++] = programs[k];
    			}
    		}
    		return ans;
    	}
    
    	// 会议的开始时间和结束时间,都是数值,不会 < 0
    	public static int bestArrange2(Program[] programs) {
    		Arrays.sort(programs, new ProgramComparator());
    		int timeLine = 0;
    		int result = 0;
    		// 依次遍历每一个会议,结束时间早的会议先遍历
    		for (int i = 0; i < programs.length; i++) {
    			if (timeLine <= programs[i].start) {
    				result++;
    				timeLine = programs[i].end;
    			}
    		}
    		return result;
    	}
    
    	public static class ProgramComparator implements Comparator<Program> {
    
    		@Override
    		public int compare(Program o1, Program o2) {
    			return o1.end - o2.end;
    		}
    
    	}
    
    	// for test
    	public static Program[] generatePrograms(int programSize, int timeMax) {
    		Program[] ans = new Program[(int) (Math.random() * (programSize + 1))];
    		for (int i = 0; i < ans.length; i++) {
    			int r1 = (int) (Math.random() * (timeMax + 1));
    			int r2 = (int) (Math.random() * (timeMax + 1));
    			if (r1 == r2) {
    				ans[i] = new Program(r1, r1 + 1);
    			} else {
    				ans[i] = new Program(Math.min(r1, r2), Math.max(r1, r2));
    			}
    		}
    		return ans;
    	}
    
    	public static void main(String[] args) {
    		int programSize = 12;
    		int timeMax = 20;
    		int timeTimes = 1000000;
    		for (int i = 0; i < timeTimes; i++) {
    			Program[] programs = generatePrograms(programSize, timeMax);
    			if (bestArrange1(programs) != bestArrange2(programs)) {
    				System.out.println("Oops!");
    			}
    		}
    		System.out.println("finish!");
    	}
    
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112

    字典序最小的字符串拼接

    给定一个由字符串组成的数组strs,必须把所有的字符串拼接起来,返回所有可能的拼接结果中字典序最小的结果

    package class13;
    
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.TreeSet;
    
    public class Code05_LowestLexicography {
    
    	public static String lowestString1(String[] strs) {
    		if (strs == null || strs.length == 0) {
    			return "";
    		}
    		TreeSet<String> ans = process(strs);
    		return ans.size() == 0 ? "" : ans.first();
    	}
    
    	// strs中所有字符串全排列,返回所有可能的结果
    	public static TreeSet<String> process(String[] strs) {
    		TreeSet<String> ans = new TreeSet<>();
    		if (strs.length == 0) {
    			ans.add("");
    			return ans;
    		}
    		for (int i = 0; i < strs.length; i++) {
    			String first = strs[i];
    			String[] nexts = removeIndexString(strs, i);
    			TreeSet<String> next = process(nexts);
    			for (String cur : next) {
    				ans.add(first + cur);
    			}
    		}
    		return ans;
    	}
    
    	// {"abc", "cks", "bct"}
    	// 0 1 2
    	// removeIndexString(arr , 1) -> {"abc", "bct"}
    	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 class MyComparator implements Comparator<String> {
    		@Override
    		public int compare(String a, String b) {
    			return (a + b).compareTo(b + a);
    		}
    	}
    
    	public static String lowestString2(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;
    	}
    
    	// for test
    	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() * 5);
    			ans[i] = (Math.random() <= 0.5) ? (char) (65 + value) : (char) (97 + value);
    		}
    		return String.valueOf(ans);
    	}
    
    	// for test
    	public static String[] generateRandomStringArray(int arrLen, int strLen) {
    		String[] ans = new String[(int) (Math.random() * arrLen) + 1];
    		for (int i = 0; i < ans.length; i++) {
    			ans[i] = generateRandomString(strLen);
    		}
    		return ans;
    	}
    
    	// for test
    	public static String[] copyStringArray(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 arrLen = 6;
    		int strLen = 5;
    		int testTimes = 10000;
    		System.out.println("test begin");
    		for (int i = 0; i < testTimes; i++) {
    			String[] arr1 = generateRandomStringArray(arrLen, strLen);
    			String[] arr2 = copyStringArray(arr1);
    			if (!lowestString1(arr1).equals(lowestString2(arr2))) {
    				for (String str : arr1) {
    					System.out.print(str + ",");
    				}
    				System.out.println();
    				System.out.println("Oops!");
    			}
    		}
    		System.out.println("finish!");
    	}
    
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117

    分割金条

    一块金条切成两半,是需要花费和长度数值一样的铜板
    比如长度为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铜板
    输入一个数组,返回分割的最小代价

    package class14;
    
    import java.util.PriorityQueue;
    
    public class Code02_LessMoneySplitGold {
    
    	// 纯暴力!
    	public static int lessMoney1(int[] arr) {
    		if (arr == null || arr.length == 0) {
    			return 0;
    		}
    		return process(arr, 0);
    	}
    
    	// 等待合并的数都在arr里,pre之前的合并行为产生了多少总代价
    	// arr中只剩一个数字的时候,停止合并,返回最小的总代价
    	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++) {
    				ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), 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 int lessMoney2(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;
    	}
    
    	// for test
    	public static int[] generateRandomArray(int maxSize, int maxValue) {
    		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
    		for (int i = 0; i < arr.length; i++) {
    			arr[i] = (int) (Math.random() * (maxValue + 1));
    		}
    		return arr;
    	}
    
    	public static void main(String[] args) {
    		int testTime = 100000;
    		int maxSize = 6;
    		int maxValue = 1000;
    		for (int i = 0; i < testTime; i++) {
    			int[] arr = generateRandomArray(maxSize, maxValue);
    			if (lessMoney1(arr) != lessMoney2(arr)) {
    				System.out.println("Oops!");
    			}
    		}
    		System.out.println("finish!");
    	}
    
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    项目收益

    输入:
    正数数组costs正数数组profits正数k
    正数m含义:
    costs[i] 表示 i 号项目的花费
    profits[i] 表示 i 号项目在扣除花费之后还能挣到的钱(利润) k 表示你只能串行的最多做k个项目
    m表示你初始的资金
    说明:
    你每做完一个项目,马上获得的收益,可以支持你去做下一个项目。
    输出:
    你最后获得的最大钱数。

    package class14;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class Code04_IPO {
    
    	// 最多K个项目
    	// W是初始资金
    	// Profits[] Capital[] 一定等长
    	// 返回最终最大的资金
    	public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
    		PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
    		PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
    		for (int i = 0; i < Profits.length; i++) {
    			minCostQ.add(new Program(Profits[i], Capital[i]));
    		}
    		for (int i = 0; i < K; i++) {
    			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
    				maxProfitQ.add(minCostQ.poll());
    			}
    			if (maxProfitQ.isEmpty()) {
    				return W;
    			}
    			W += maxProfitQ.poll().p;
    		}
    		return W;
    	}
    
    	public static class Program {
    		public int p;
    		public int c;
    
    		public Program(int p, int c) {
    			this.p = p;
    			this.c = c;
    		}
    	}
    
    	public static class MinCostComparator implements Comparator<Program> {
    
    		@Override
    		public int compare(Program o1, Program o2) {
    			return o1.c - o2.c;
    		}
    
    	}
    
    	public static class MaxProfitComparator implements Comparator<Program> {
    
    		@Override
    		public int compare(Program o1, Program o2) {
    			return o2.p - o1.p;
    		}
    
    	}
    
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    点亮.位置要几盏灯?

    给定一个字符串str,只由’X’和’.'两种字符构成
    ‘X’表示墙,不能放灯,也不需要点亮;’.'表示居民点,可以放灯,需要点亮
    如果灯放在i位置,可以让i-1,i和i+1三个位置被点亮
    返回如果点亮str中所有需要点亮的位置,至少需要几盏灯

    package class14;
    
    import java.util.HashSet;
    
    public class Code01_Light {
    
    	public static int minLight1(String road) {
    		if (road == null || road.length() == 0) {
    			return 0;
    		}
    		return process(road.toCharArray(), 0, new HashSet<>());
    	}
    
    	// str[index....]位置,自由选择放灯还是不放灯
    	// str[0..index-1]位置呢?已经做完决定了,那些放了灯的位置,存在lights里
    	// 要求选出能照亮所有.的方案,并且在这些有效的方案中,返回最少需要几个灯
    	public static int process(char[] str, int index, HashSet<Integer> lights) {
    		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 lights.size();
    		} else { // str还没结束
    			// i X .
    			int no = process(str, index + 1, lights);
    			int yes = Integer.MAX_VALUE;
    			if (str[index] == '.') {
    				lights.add(index);
    				yes = process(str, index + 1, lights);
    				lights.remove(index);
    			}
    			return Math.min(no, yes);
    		}
    	}
    
    	public static int minLight2(String road) {
    		char[] str = road.toCharArray();
    		int i = 0;
    		int light = 0;
    		while (i < str.length) {
    			if (str[i] == 'X') {
    				i++;
    			} else {
    				light++;
    				if (i + 1 == str.length) {
    					break;
    				} else { // 有i位置 i+ 1 X .
    					if (str[i + 1] == 'X') {
    						i = i + 2;
    					} else {
    						i = i + 3;
    					}
    				}
    			}
    		}
    		return light;
    	}
    
    	// 更简洁的解法
    	// 两个X之间,数一下.的数量,然后除以3,向上取整
    	// 把灯数累加
    	public static int minLight3(String road) {
    		char[] str = road.toCharArray();
    		int cur = 0;
    		int light = 0;
    		for (char c : str) {
    			if (c == 'X') {
    				light += (cur + 2) / 3;
    				cur = 0;
    			} else {
    				cur++;
    			}
    		}
    		light += (cur + 2) / 3;
    		return light;
    	}
    
    	// for test
    	public static String randomString(int len) {
    		char[] res = new char[(int) (Math.random() * len) + 1];
    		for (int i = 0; i < res.length; i++) {
    			res[i] = Math.random() < 0.5 ? 'X' : '.';
    		}
    		return String.valueOf(res);
    	}
    
    	public static void main(String[] args) {
    		int len = 20;
    		int testTime = 100000;
    		for (int i = 0; i < testTime; i++) {
    			String test = randomString(len);
    			int ans1 = minLight1(test);
    			int ans2 = minLight2(test);
    			int ans3 = minLight3(test);
    			if (ans1 != ans2 || ans1 != ans3) {
    				System.out.println("oops!");
    			}
    		}
    		System.out.println("finish!");
    	}
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
  • 相关阅读:
    pthread 常用 API 创建 销毁 调度 互斥锁 自旋锁 读写锁 条件变量
    书店漫游记录
    Python面向对象丨面向过程和面向对象,你真的了解“对象”吗?
    关于OCR文字识别的坑(64位Python专属)
    【python海洋专题二十五】给南海年平均海流+scale
    linux-grep命令
    2023年安全生产监管人员证考试题库及安全生产监管人员试题解析
    堆、堆排序、堆应用
    SSM整合(五)
    Folly库实现阅读——FBString
  • 原文地址:https://blog.csdn.net/weixin_42274953/article/details/126178327