LeetCode刷题|算法归类|贪心算法介绍及各算法题合辑（持续补充）
贪心算法
一、介绍
-
贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而
希望能够导致结果是最好或者最优的算法 -
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
二、案例
-
假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有
的地区都可以接收到信号 -
思路分析:
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假
设总的有 n 个广播台，则广播台的组合总共有
2ⁿ -1 个,假设每秒可以计算 10 个子集， 如图:
使用贪婪算法，效率高:
- 目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择
策略上，因为需要覆盖全部地区的最小集合: - 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关
系） - 将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
- 重复第 1 步直到覆盖了全部的地区
分析的图解:
比如，在第一轮时，遍历所有的电台，求出每个广播台能够覆盖的地区（之前尚未被覆盖的地区）的个数，第一轮的时候分别是3,3,3,2,2。因为k2没有超过k1，所以选择k1，这时我们需要将待覆盖地区集合allAreas集合中k1已经覆盖到的地区去掉，即allAreas变成了{广州，深圳，成都，杭州，大连}，第二轮遍历开始，这时对比allAreas集合，每个广播台能够覆盖的地区（尚未被覆盖的地区）的个数分别为0,2,2,1,2,选择k2，再在allAreas集合中去掉k2新覆盖的两个地区，一直循环，直至allAreas为null
3、代码实现
package com.atguigu.greedy;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
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>();
//定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
//还没覆盖的地区即图解中的allAreas，最初是全部，即均需要被覆盖，随着有地区被覆盖，allAreas逐渐变小
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
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]
}
}
输出：
得到的选择结果是[K1, K2, K3, K5]
三、LeetCode例题
1、#370摆动序列
1）题目
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wiggle-subsequence
2）代码实现
class Solution {
//贪心算法，所以第一个数字就开始算进摆动子序列，且下一个不等于nums[0]的值就能决定先升还是先降
public int wiggleMaxLength(int[] nums) {
if (nums.length<2){
return nums.length;
}
int precha=nums[1]-nums[0];//求前两个数的差值
int count=precha==0?1:2;//如果前两个数相等，则cout从1开始计，如果不相等，则count从2开始计
for(int i=2;i<nums.length;i++){
int diff=nums[i]-nums[i-1];
if(precha>=0&&diff<0||precha<=0&&diff>0){
//如果升降序交替了，则count++，注意这里只能precha==0，diff不能=0，因为即使precha==0，前面也只算了一个
count++;
precha=diff;//更新前一个差值
}
}
return count;
}
}
复杂度分析
- 时间复杂度： O(n) 。我们需要遍历数组一次。
- 空间复杂度： O(1)。不需要使用额外的空间。
2、#1007 行相等的最少多米诺旋转
1）题目
在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）
我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。
返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
如果无法做到，返回 -1.
示例 1：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pLYZOJWu-1595142587487)(E:/User/markdown笔记/博客笔记/LeetCode/%231007行相等的最少多米诺旋转/img/1.png)]
输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
输出：2
解释：
图一表示：在我们旋转之前， A 和 B 给出的多米诺牌。
如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
示例 2：
输入：A = [3,5,1,2,3], B = [3,6,3,3,4]
输出：-1
解释：
在这种情况下，不可能旋转多米诺牌使一行的值相等。
提示：
1 <= A[i], B[i] <= 6
2 <= A.length == B.length <= 20000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-domino-rotations-for-equal-row
2）代码实现
class Solution {
public int check(int target, int[] A, int[] B, int n) {
int min_a = 0, min_b = 0;//记录要反转的次数
for (int i = 0; i < n; i++) {
if (A[i] != target && B[i] != target) return -1;
//如果没有一个等于target，那就失败，直接返回-1
//经过上面的if判断过滤，则后面每一对中至少有一个==target，只要找出每个数组中不等于target的，即需要翻转的
else if (A[i] != target) min_a++;//这里判断其实是A[i]!=target&&B[i]==target
else if (B[i] != target) min_b++;//这里判断其实是B[i]!=target&&A[i]==target
}
return Math.min(min_a, min_b);//能成功使得一行相同，返回翻转次数最小的
}
//如果想要任何一行的数字都相同，则这个数字必须出现在每一对里，
//要么在A里要么在B里，既然必须出现在每一对，那么我们就可以任取一对，我们就取第一对
//即这个一列相同的数字要么是A[0]，要么是B[0]，或者不存在相同数字的一行
public int minDominoRotations(int[] A, int[] B) {
int n = A.length;
int min = check(A[0], B, A, n);//这里切记B为第一个，A为第二个
if (min!= -1 || A[0] == B[0]) return min;
//如果这对数相等，则也不用求B[0]时的情况，直接返回，无论成不成功
//如果target是A[0]时，且不等于-1，也直接返回，且不必比较和target是b[0]时，哪个更小，因为肯定相等
else return check(B[0], B, A, n);
//如果不满足上面if的要求，直接返回target是B[0]时的返回值，不论成功与否
}
}
3、#392判断子序列
1）题目
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1:
s = “abc”, t = “ahbgdc”
返回 true.
示例 2:
s = “axc”, t = “ahbgdc”
返回 false.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-subsequence
2）代码实现
从s中依次取出一个字符，到t中去查找，记录出现的位置；
s中取出下一个字符，从上次出现位置的下一个开始查找，
直到s中的字符全部扫描完成
class Solution {
public boolean isSubsequence(String s, String t) {
if(s==null) return true;
if(t==null) return false;
//将两个字符串都转为字符数组
char[] chars01 = s.toCharArray();
char[] chars02 = t.toCharArray();
int index=-1;
//从t查找的索引初始值为0,search函数返回更新index值
//因为后面需要+1，所以这里index取-1
//每次从上次查询返回索引值的下一个位置开始
for(int i=0;i<chars01.length;i++){
char target=chars01[i];
if(index==-2){
return false;
}else{
index=search(chars02,index+1,target);
}
}
if(index==-2){//这里加if是为了特殊情况，s="a",t="b",search方法之后返回-2，上一个else中index=-2之后，for循环直接结束了，没来得及判断if(index==-2)
return false;
}else {
return true;
}
}
//因为是无序数组，所以采用线性查找算法 index是查找的起点
public int search(char[] arr,int index,char target){
for(int i=index;i<arr.length;i++){
if(arr[i]==target){
return i;
}
}
return -2;//如果循环结束还没有返回索引值，说明没有返回-1
}
}
可以继续改进：
没来得及判断if(index==-2)
return false;
}else {
return true;
}
}
//因为是无序数组，所以采用线性查找算法 index是查找的起点
public int search(char[] arr,int index,char target){
for(int i=index;i<arr.length;i++){
if(arr[i]==target){
return i;
}
}
return -2;//如果循环结束还没有返回索引值，说明没有返回-1
}
}
可以继续改进：
遍历扫描chars02的时候，不必遍历到最后。如当我们搜索chars01=“abcde”中的c时，就可以只搜寻到chars02的倒数第三个数，只要我们在每次search之后并返回值不是-2的时候记录此时chars01已被搜寻到的字符串个数k，并将k传入到search方法中，然后search方法中for循环的中值条件就可以改为i<arr.length-（chars.length-k）
持续补充对应算法题，欢迎关注
上一篇： 算法-程序设计课week6-作业-D - 数据中心
下一篇： Spark-Shuffle