LeetCode刷题|算法归类|贪心算法介绍及各算法题合辑(持续补充)

贪心算法

一、介绍

  1. 贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取***或者最优(即最有利)的选择,从而
    希望能够导致结果是***或者最优的算法

  2. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果

二、案例

  1. 假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台,让所有
    的地区都可以接收到信号
    LeetCode刷题|算法归类|贪心算法介绍及各算法题合辑(持续补充)

  2. 思路分析:
    如何找出覆盖所有地区的广播台的集合呢,使用穷举法实现,列出每个可能的广播台的集合,这被称为幂集。假
    设总的有 n 个广播台,则广播台的组合总共有
    2ⁿ -1 个,假设每秒可以计算 10 个子集, 如图:
    LeetCode刷题|算法归类|贪心算法介绍及各算法题合辑(持续补充)

使用贪婪算法,效率高:

  1. 目前并没有算法可以快速计算得到准备的值, 使用贪婪算法,则可以得到非常接近的解,并且效率高。选择
    策略上,因为需要覆盖全部地区的最小集合:
  2. 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区,但没有关
    系)
  3. 将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
  4. 重复第 1 步直到覆盖了全部的地区
    分析的图解:
    LeetCode刷题|算法归类|贪心算法介绍及各算法题合辑(持续补充)

比如,在第一轮时,遍历所有的电台,求出每个广播台能够覆盖的地区(之前尚未被覆盖的地区)的个数,第一轮的时候分别是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)

持续补充对应算法题,欢迎关注

猜你喜欢