贪心算法整理

目录

455.分发饼干

思路：

策略归纳：

55、跳跃问题

621. 任务调度器

135. 分发糖果

 435. 无重叠区间

45. 跳跃游戏 II

 总结：

每次根据问题的当前状态，选择一个局部最优策略，并且不断迭代，最后产生一个全局最优解。

 每次从当前问题出发，而不考虑之前或之后的状态，做出一个最有利于当前问题的决策，迭代更新问题，不断重复同样的 *** 作直到问题得到解决。

不同大小的饼干分发给胃口不同的孩子，目标是满足尽可能多的孩子。

从孩子方面：

胃口小的应该优先满足，因为最容易满足，被成功分配的概率高

从饼干方面：

        物尽其用，当一个孩子能被多个饼干满足时，应该用最小的一个。

当全局最优解涉及多个变量时，分别考虑每个变量对全局最优解的影响，最后将所有情况进行汇总考虑。

上面涉及两个变量孩子和饼干，归纳起来就是先满足胃口最小的孩子，然后饼干选可以满足的最小一块。

也就是对孩子和饼干分别排序，

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

思路：

从贪心的思路（局部最优）走

思考，当前位置是3，那我是跳1，跳2还是跳3

（1） 如果每次都选择最远距离，而如果最远距离3可以跳跃的最大长度是0，那么就进入了死胡同。

（2）如果每次选择最近距离1，那么如果最近距离1可以跳跃的最大长度是0，那么也进入了死胡同。

（3）从上面可以看出不管选择最远距离还是最近距离还是中间的距离都会有可能陷入它的在最大长度为0的死路，那么是不是需要考虑跳的那个距离呢？

（4）考虑跳到那个位置的下标数，它那个数代表我能跳到下一个步骤的距离，如果那个距离大，那么就认为我为下一个步骤提供了最好的一步

伪代码：

1、如果数组的长度为1，返回true

2、 for遍历数组，如果当前位置加上数组的位置超过数组直接返回true

      否则判断数组的[当前位置+位置里的从0开始的数]进行循环

下面的代码以覆盖范围为主角， 刚开始覆盖范围为0，在覆盖范围内计算自己能达到的最远距离，然后更新覆盖范围，每往前走一步，如果覆盖范围超过了数组的范围，那么就成功

  public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
        int coverRange = 0;
        //在覆盖范围内更新最大的覆盖范围
        for (int i = 0; i <= coverRange; i++) {
            coverRange = Math.max(coverRange, i + nums[i]);
            if (coverRange >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。

其中每个字母表示一种不同种类的任务。

任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。

在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

思路：

我觉得这个题的解法和贪心没有关系，如果硬套的话

局部优先，考虑次数最多的任务

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] count = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            count[tasks[i]-'A']++;
        }//统计词频
        Arrays.sort(count);//词频排序，升序排序，count[25]是频率最高的
        int maxCount = 0;
        //统计有多少个频率最高的字母
        for (int i = 25; i >= 0; i--) {
            if(count[i] != count[25]){
                break;
            }
            maxCount++;
        }
        //公式算出的值可能会比数组的长度小，取两者中最大的那个
        return Math.max((count[25] - 1) * (n + 1) + maxCount , tasks.length);
    }
}

n 个孩子站成一排。

给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。

相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

例如

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

提示：

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
通过次数133,507提交次数273,320

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left_ans = new int[n];
        int[] right_ans = new int[n];
        Arrays.fill(left_ans, 1);
        Arrays.fill(right_ans, 1);
        int ans = 0;
        // 考虑左相邻条件
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left_ans[i] = left_ans[i - 1] + 1;
            }
        }
        // 考虑右相邻条件
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right_ans[i] = right_ans[i + 1] + 1;
            }
        }
        // 合并两个条件结果
        for (int i = 0; i < n; i++) {
            ans += Math.max(left_ans[i], right_ans[i]);
        }
        return ans;
    }
}

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。

返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

 局部最优推出全局最优，那就是贪心。

下面排序代码使用了泛型

java中Arrays.sort()的几种用法_barry_gfw的博客-CSDN博客_arrays.sort

class SolutionL15_5 {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == a[0]) return a[1] - b[1];
            return a[0] - b[0];
        });
        System.out.println(intervals);
        for(int i=0;i

public static  int jump(int[] nums) {
            if (nums == null || nums.length == 0 || nums.length == 1) {
                return 0;
            }
            //记录跳跃的次数
            int count=0;
            //当前的覆盖最大区域
            int curDistance = 0;
            //最大的覆盖区域
            int maxDistance = 0;
            for (int i = 0; i < nums.length; i++) {
                //在可覆盖区域内更新最大的覆盖区域
                maxDistance = Math.max(maxDistance,i+nums[i]);
                //说明当前一步，再跳一步就到达了末尾
                if (maxDistance>=nums.length-1){
                    count++;
                    break;
                }
                //走到当前覆盖的最大区域时，更新下一步可达的最大区域
                if (i==curDistance){
                    curDistance = maxDistance;
                    count++;
                }
            }
            return count;
        }