贪心算法
约 2887 字大约 10 分钟
介绍
贪心算法（Greedy Algorithm）是一种在解决问题时所采用的逐步构建解决方案的策略。它在每一步选择中都采取当前状态下最优或最有利的选择，而不管这个选择在全局范围内是否最优。简单来说，贪心算法总是做出看起来最好的选择，期望通过一系列的局部最优选择最终得到全局最优解。
贪心算法的特点
- 局部最优：贪心算法在每一步都选择当前状态下最优的操作。
- 全局最优：通过局部最优的选择，贪心算法期望最终能得到全局最优解。但贪心算法并不总是能保证得到全局最优解。
- 不回溯：一旦作出某个选择，贪心算法不会回头更改以前的选择。它不会像动态规划或回溯算法那样存储之前的状态。
应用场景
- 最优子结构性质：一个问题具有最优子结构，如果问题的最优解包含其子问题的最优解。贪心算法可以通过解决子问题来构建全局最优解。
- 贪心选择性质：每一步的局部最优选择可以构成问题的全局最优解。
常见的贪心算法例子
- 活动选择问题：选择最多的活动在一个时间段内参加，要求选出的活动互不冲突。
- 最小生成树问题：Kruskal和Prim算法都利用贪心思想构造图的最小生成树。
- Huffman编码：基于字符出现的频率，构建最优的前缀编码。
- 找零问题：在商店找零时，使用最少数量的硬币来找出指定金额。
贪心算法的局限性：贪心算法不是万能的，只有当问题满足贪心选择性质和最优子结构性质时，才能确保贪心算法得到的解是全局最优的。在某些情况下，贪心算法得到的解可能不是最优的，因为它只考虑了局部的最优解，没有考虑全局的情况。
15. 贪心算法
- 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
- 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
- 比如上题的算法选出的是K1, K2, K3, K5，符合覆盖了全部的地区
- 但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果K2 的使用成本低于K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的.
假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号
广播台 覆盖地区
K1 "北京", "上海", "天津"
K2 "广州", "北京", "深圳"
K3 "成都", "上海", "杭州"
K4 "上海", "天津"
K5 "杭州", "大连"
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集
假设总的有n个广播台，则广播台的组合总共有2ⁿ -1 个
使用贪婪算法，效率高:
目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:
1.遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
2.将这个电台加入到一个集合中(比如ArrayList), 把该电台覆盖的地区在下次比较时去掉。
3.重复第1步直到覆盖了全部的地区
public class GreedyAlgorithm {
public static void main(String[] args) {
//创建广播电台,放入到Map
HashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
//将各个电台放入到broadcasts
HashSet<String> hashSet1 = new HashSet<String>();
hashSet1.add("北京");
hashSet1.add("上海");
hashSet1.add("天津");
HashSet<String> hashSet2 = new HashSet<String>();
hashSet2.add("广州");
hashSet2.add("北京");
hashSet2.add("深圳");
HashSet<String> hashSet3 = new HashSet<String>();
hashSet3.add("成都");
hashSet3.add("上海");
hashSet3.add("杭州");
HashSet<String> hashSet4 = new HashSet<String>();
hashSet4.add("上海");
hashSet4.add("天津");
HashSet<String> hashSet5 = new HashSet<String>();
hashSet5.add("杭州");
hashSet5.add("大连");
//加入到map
broadcasts.put("K1", hashSet1);
broadcasts.put("K2", hashSet2);
broadcasts.put("K3", hashSet3);
broadcasts.put("K4", hashSet4);
broadcasts.put("K5", hashSet5);
//allAreas 存放所有的地区
HashSet<String> allAreas = new HashSet<String>();
allAreas.add("北京");
allAreas.add("上海");
allAreas.add("天津");
allAreas.add("广州");
allAreas.add("深圳");
allAreas.add("成都");
allAreas.add("杭州");
allAreas.add("大连");
//创建ArrayList, 存放选择的电台集合
ArrayList<String> selects = new ArrayList<String>();
//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
HashSet<String> tempSet = new HashSet<String>();
//定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
//如果maxKey 不为null , 则会加入到 selects
String maxKey = null;
while(allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
//每进行一次while,需要
maxKey = null;
//遍历 broadcasts, 取出对应key
for(String key : broadcasts.keySet()) {
//每进行一次for
tempSet.clear();
//当前这个key能够覆盖的地区
HashSet<String> areas = broadcasts.get(key);
tempSet.addAll(areas);
//求出tempSet 和 allAreas 集合的交集, 得到该电台所能覆盖到未覆盖的地区
tempSet.retainAll(allAreas);
//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多
//就需要重置maxKey
// tempSet.size() >broadcasts.get(maxKey).size() 体现出贪心算法的特点,每次都选择最优的
if(tempSet.size() > 0 &&
(maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){
maxKey = key;
}
}
//maxKey != null, 就应该将maxKey 加入selects
if(maxKey != null) {
selects.add(maxKey);
//将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉
allAreas.removeAll(broadcasts.get(maxKey));
}
}
System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]
}
}
121买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
时间复杂度：O(n)，只需要遍历一次。
空间复杂度：O(1)，只使用了常数个变量。
用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
55跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：输入：nums = [2,3,1,1,4]输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。
空间复杂度：O(1)，不需要额外的空间开销。
public class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int rightmost = 0;
for (int i = 0; i < n; ++i) {
if (i <= rightmost) {//如果 i <= rightmost：说明位置 i 是可以从起点经过某些跳跃到达的。
//换句话说，rightmost 已经覆盖到了位置 i，所以可以在这个位置 i 继续考虑从这里往后跳跃，进一步更新 rightmost。
rightmost = Math.max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
}
45跳跃游戏II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
时间复杂度：O(n)，其中 n 是数组长度。
空间复杂度：O(1)。
class Solution {
public int jump(int[] nums) {
int length = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < length - 1; i++) {
//记录从0-end的最大位置
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {//更新end的位置
end = maxPosition;
steps++;
}
}
return steps;
}
}
763划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
由于同一个字母只会出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。
在得到每个字母最后一次出现的下标位置之后，可以使用贪心的方法将字符串划分为尽可能多的片段，具体做法如下：
- 从左到右遍历字符串，遍历的同时维护当前片段的开始下标
start和结束下标end，初始时start = end = 0。 - 对于每个访问到的字符
c，得到当前字符的最后一次出现的下标位置end_c，则当前片段的结束下标一定不会小于end_c，因此令end = max(end, end_c)。 - 当访问到下标
end时，当前片段访问结束，当前片段的下标范围是[start, end]，长度为end - start + 1，将当前片段的长度添加到返回值，然后令start = end + 1，继续寻找下一个片段。 - 重复上述过程，直到遍历完字符串。
class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
int length = s.length();
//记录每个字母最后一次出现的索引
for (int i = 0; i < length; i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> partition = new ArrayList<Integer>();
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
end = Math.max(end, last[s.charAt(i) - 'a']);
if (i == end) {
partition.add(end - start + 1);
start = end + 1;
}
}
return partition;
}
}