贪心算法学习

2021/7/21 22:42:37

本文主要是介绍贪心算法学习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 贪心算法概述
    • 无后效性(仅供参考)
    • 案例一:分配问题(力扣455题:简单)
    • 案例二:摆动序列(LeetCode 376:中等)
    • 案例三:区间问题(力扣435:中等)
    • 案例四:买股票的最佳时机(力扣121题:简单)
    • 后记

贪心算法概述

贪心算法(又称贪婪算法)在对问题求解时,总是做出在当前看来是最好的选择,也就是说,不从整体最优上加以考虑,它所做出的仅是在某种意义上的局部最优解,从而最后得到全局最优。

贪心算法没有固定的算法框架,算法设计的关键是贪心策略,必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。

贪心策略适用的前提是:局部最优策略能导致产生全局最优解

无后效性(仅供参考)

百度百科的解释:

  • 无后效性原则:指的是这样一种性质,某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响,也就是说,未来与过去无关

只看概念有点晦涩难懂,举个栗子吧(仅供理解):

  • 假设你骑电动车去上学,所以有的路随便走,OK,中午去上学对于下午去上学没有任何影响,这就是无后效性,未来与过去无关。
  • 假设你骑电动车去上学,中午走过的路下午不能走,OK,下午去上学走的路要收到中午上学走的路线的影响,这就不满足无后效性,未来与过去有关。

案例一:分配问题(力扣455题:简单)

题目描述

  • 有一群孩子和一堆饼干,每个孩子有一个饥饿度,每个饼干都有一个大小。每个孩子只能吃一个饼干,且只有饼干的大小不小于(大于或者等于)孩子的饥饿度时,这个孩子才能吃饱,求解最多有多少孩子可以吃饱。

示例:

  • 输入两个数组,分别代表孩子的饥饿度和饼干的大小,输出最多有多少孩子可以吃饱的数量。
Input: [1,2], [1,2,3]
Output: 2

分析

  • 贪心策略,我们首先考虑饥饿度最小的孩子,这个孩子最容易吃饱,我们给他最小的饼干,如果不能满足,就使用次大的饼干,这就是通过局部最优解,然后找到全局最优解
  • 我们先给数组进行排序,然后在使用饼干数组中的元素和孩子数组中的元素对比,如果匹配成功就进行下一个孩子的投喂(这个时候两个数组的指针都要后移),如果匹配失败就要使用饼干数组下一个元素对孩子进行投喂(这时候饼干数组后移,孩子数组不动),直到匹配成功;

代码实现

public class Test01 {
    public static void main(String[] args) {
        int[] children=new int[]{1,2};
        int[] cookies=new int[]{1,2,3};
        int num=distribution(children,cookies);
        System.out.println(num);

        }
    public static int distribution(int[] children,int[] cookies ){
        //使用工具类对数组进行排序
        Arrays.sort(children);
        Arrays.sort(cookies);
        //定义两个索引【指针】
        int indexCh=0;
        int indexCo=0;
        //注意:饼干数组一定会后移的,孩子数组如果投喂成功才会后移
        while(indexCh<children.length&&indexCo<cookies.length){
            if(indexCo>=indexCh){
                indexCh++;
                indexCo++;
            }else {
                indexCo++;
            }
        }
        //最终返回的是投喂成功孩子的个数,索引每次都是投喂成功后先加一的,刚好是实际的个数
        return indexCh;
    }
}

案例二:摆动序列(LeetCode 376:中等)

题目描述:

  • 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列,少于两个元素的序列也是摆动序列。
  • 例如:
    • [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

分析

  • 首先看一下摆动数列的特点:要么比两边大(峰),要么比两边小(谷),而且峰谷交替
  • 比如nums=[1, 7, 4, 9, 11, 15, 5]
    • 我们将第0个元素作为起始端点(峰、谷)lastIndex = 0
    • 第一个元素是7,大于上一个端点nums[lastIndex],所以此时是寻找下一个峰,第二个元素为4,所以第一个元素即为峰,更新lastIndex = 1
    • 第二个元素是4,小于上一个端点nums[lastIndex],所以此时是寻找下一个谷,第三个元素为9,所以第二个元素即为谷,更新lastIndex = 2
    • 第三个元素是9,大于上一个端点nums[lastIndex],所以此时是寻找下一个峰,但是第四个元素比第三个元素大,第五个元素比第四个元素大,所以(贪心策略)下一个峰应该为第五个元素,更新lastIndex = 5这种情况除非一直或者一直减
    • 第六个元素是5,小于上一个端点nums[lastIndex],所以此时是寻找下一个谷,最后的元素为5,所以最后的元素即为谷,更新lastIndex = 6
    • 退出!!!!

代码实现

  • 力扣上面的一种解法,感觉相当的经典,再此分享一下:
public static int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        //因为初始不知道是峰还是谷,所以都设为1
        int up = 1;
        int down = 1;
        //从索引为1的位置开始遍历
        for (int i = 1; i < n; i++) {
            //峰,所以前面为谷,使用谷加1
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            }
            //谷,所以前面为峰,使用峰加1
            if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }

案例三:区间问题(力扣435:中等)

题目描述

  • 给定多个区间,计算让这些区间互不重叠所需要移除区间的最少个数,起止相连不算重叠。

示例

  • 输入是一个数组,数组由多个长度固定为2的数组组成(二维数组),表示区间的开始和结尾,输出一个整数,表示需要移除的区间数量。
Input:[[1,2],[2,4],[1,3]]
Output:1
  • 在示例中,可以移除区间[1,3],使得剩余的区间[[1,2],[2,4]]互不重叠。

分析

  • 在选择要保留区间时,区间的结尾十分重要:贪心策略,选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。因此,采用贪心算法,优先保留结尾小且不相交的区间。
  • 实现方法:先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选择的区间不重叠的区间
  • 注意:我们使用结尾进行排序,我们要尽可能选择结尾小的区间,这样才能留下更多的区间,我们先用一个变量保存当前已选定区间的结尾,只要下个区间开头不小于我们保存的区间的结尾,我们就用这个区间的结尾去替换变量的值,用于下一次的比较。

代码实现

public static int region(int[][] arr) {
       //保留区间的个数
       int num=1;
       /*Array.sort(array);来进行排序,如果我们数组中是放的基本数据类型,就可以直接比较大小排序,
       如果我们放的是对象的话,这样排序就意义不大,需要我们自己进行相应的修改,得到我们想要的比较结果。

       对二维数组按照区间的结尾大小排序,对于二维数组,我们可以重写这个比较器
       使用二维数组中的一维数组的第二个元素来比较,也就是把二维数组中的一维数组看成一个元素
       */
       Arrays.sort(arr, new Comparator<int[]>() {
           public int compare(int[] o1, int[] o2) {
               return o1[1]-o2[1];
           }
       });
       //保存第一个保留区间的结尾
       int temp=arr[0][1];
       for(int i=1;i<arr.length;i++){
           /*我们使用结尾进行排序,我们要尽可能选择结尾小的区间,这样才能留下更多的区间,
            我们先用一个`变量`保存当前`已选定区间的结尾`,只要下个区间`开头`不小于我们保存的区间的`结尾`,
            我们就用这个区间的结尾去替换变量的值,用于下一次的比较*/
           if(temp<=arr[i][0]){
               num++;
               temp=arr[i][1];
           }
       }
       return arr.length-num;
   }

案例四:买股票的最佳时机(力扣121题:简单)

题目描述

  • 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格,设计一个算法来计算你所能获取的最大利润,你最多可以完成 k 笔交易(可以多次交易)。
  • 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例

  • 示例 1:
输入: p=[2,4,1]
输出: 2
解释: 在第1天(股票价格 = 2)的时候买入,在第2天(股票价格 = 4)的时候卖出,这笔交易所能获得利润 4-2 = 2 。
  • 示例 2:
输入: p=[3,2,6,5,1,3]
输出: 6
解释: 
在第2天(股票价格 = 2)的时候买入,在第3天(股票价格 = 6)的时候卖出,这笔交易所能获得利润6-2 =4 
在第5天(股票价格 = 1)的时候买入,在第6天 (股票价格=3) 的时候卖出, 这笔交易所能获得利润 = 3-1 =2 。

分析

  • 贪心策略1:只要今天买明天卖能赚钱就买
  • 贪心策略2:只要今天买明天卖能赚钱就买,但是,如果第三天的价格高于第二天就持续持有,不卖。

代码实现

public static int maxProfit(int[] arr) {
        //开始利润为0
        int profit=0;
        //循环遍历数组
        for(int i=1;i<arr.length;i++){
            //如果后一天的价格比前一天的高,就在前一天买入
            if(arr[i]-arr[i-1]>=0){
               profit+=arr[i]-arr[i-1];
               //买入就有卖出,所以卖出当天不能买入,指针再加1
               i++;
            }
        }
      return profit;
    }

后记

有些问题贪心算法只能找到局部最优解,并无法找到全局最优解,好比那个股票问题,假如价格是[1,2,3,4,5]

  • 如果使用贪心策略1:只要赚钱就买卖,只能赚取2,并不是全局最优解
  • 如果使用贪心策略2:只要今天买明天卖能赚钱就买,但是,如果第三天的价格高于第二天就持续持有,不卖,能赚到4。


这篇关于贪心算法学习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程