贪心算法

在对问题求解时，总是做出在当前看来是最好的选择.
从局部最优解 ==> 全局最优解

第一题: 分发饼干

LeetCode 455 ： 分发饼干
描述：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

解题思路:

局部最优->全局最优
局部最优：让尺寸小的饼干满足胃口小的孩子
全局最优：优先满足胃口小的孩子

1. 先将2个组数排序
2. 让child为g数组下最小孩子胃口的下标
3. 让cookies为s数组下饼干尺寸最小的小标
4. 遍历 如果g[child] <= s[cookies] 那么就能满足

代码实现:

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 先进行排序
        Arrays.sort(g);
        Arrays.sort(s);
        // 让胃口最小的孩子 吃 最小尺寸的饼干
        int child = 0;
        int cookies = 0;
        int count = 0;
        while(child < g.length && cookies < s.length){
            // 这里的饼干回复度 >= 孩子饥饿度 才能满足
            if(g[child] <= s[cookies]){
                count++;
                child++;
            }
            cookies++;
        }
        return count;
    }
}

第二题: 无重叠区间

LeetCode 435 : 无重叠区间
描述:
给定一个区间的集合intervals ，其中 intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

解题思路:

局部最优 -> 全局最优
局部最优: 优先选右边界最小的区间,避免交叉
全局最优: 保留最多的不相交区间

1. 排序区间,根据右边界的大小排序
2. 从左向右遍历,如果i区间的右边界 <``i+1区间的左边界,则需要移除i+1区间

代码实现:

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 贪心思路 ： 每次都保留区间结尾最小的且不相交的区间
        // 排序 根据每组最后一个数排序
        Arrays.sort(intervals,(o1,o2)->o1[1]-o2[1]);
        int count = 0;
        // 让 pre 指向第一个区间的右边界 如果下一个区间的左边界 小于 这个pre 就是需要移除的
        int pre = intervals[0][1];
        // 因为第一组肯定是不需要移除的 所以让i == 1
        for (int i = 1; i < intervals.length; i++){
            //  下一组左边界 < pre 移除
            if (intervals[i][0] < pre){
                count++;
            }else{
                // 不需要移除 就让pre 指向下一组的右边界
                pre = intervals[i][1];
            }
        }
        return count;
    }
}

第三题: 买股票的最佳时机 Ⅱ

LeetCode 122: 买卖股票的最佳时机 II
描述:
给定一个数组 prices ，其中 prices[i]表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

解题思路:

局部最优 -> 全局最优
局部最优: 只要明天卖能赚钱就卖
全局最优: 总是能获得利润

1. 遍历数组,只要第二天能赚钱,就卖掉,然后把利润加起来

代码实现:

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        // 这里假设 如果当天买，明天卖了能赚钱，就今天买了，明天卖。
        for(int i = 0; i < prices.length - 1; i ++){
            if(prices[i] < prices[i + 1]){
                profit += prices[i+1] - prices[i];
            }
        }
        return profit;
    }
}

第四题: 跳跃游戏

LeetCode 55: 跳跃游戏
描述:
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

解题思路:

局部最优 -> 全局最优
局部最优: 每次跨越都跨最远的距离
全局最优: 跳跃的总长度最远

1. 用mostLength记录可以跳跃到的下标
2. 遍历数组.从0下标开始,下标下的值表示最远可以跳的距离,
3. 当下标i下的值nums[i]+i > mostLength 就更新mostLength
4. 这里的 nums[i]+i 表示.能到达的下标.
5. 每次都比较如果mostLength >= nums.length-1 就返回true;
6. 遍历完到达不了最后的位置,就返回false;

代码实现

class Solution {
    public boolean canJump(int[] nums) {
        // 贪心思路 每次都跳跃最大的距离
        // mostLength 记录 跳跃的最远距离的下标
        int mostLength = 0;
        for(int i = 0;i < nums.length;i++){
            // 如果 下标是小于等于mostLength，就代表可以跳跃
            if(i <=mostLength){
                // 更新最大跳跃距离
                // 最大距离为 历史最大距离 或者 当前数据跳跃距离＋下标
                // nums[i] + i 表示最远可以达到的下标
                mostLength = Math.max(mostLength,nums[i]+i);
                // 如果最大距离可到的下标 为 数组最后一个数的下标则返回true
                if(mostLength >= nums.length -1){
                    return true;
                }
            }
        }
        // 遍历完不能到达最后就是false
        return false;
    }
}

第五题: 跳跃游戏 Ⅱ

LeetCode 45: 跳跃游戏 II
描述:
给你一个非负整数数组 nums，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

解题思路:

局部最优 -> 全局最优
局部最优: 每次跳跃都移动最大距离
全局最优: 那么所用的次数就最少

1. mostLength记录最远可达的下标
2. flg记录是否遍历到了最远的下标
3. 遍历数组. 如果 i = flg 表示跳跃到了最远记录记录下 次数,并更新flg等于最远下标
4. 每次都要让mostLength和nums[i]+i比较,确保mostLength 永远指向最远的下标.
5. 由于每次跳跃都会跳到最后一个位置,按照此方法,一定会跳过到最后一个位置或者超出最后一个位置,所以不需要遍历最后一个下标.以免多计算一次.

代码实现:

class Solution {
    public int jump(int[] nums) {
        // 贪心: 每次跳最远 -> 步数就最少
        int mostLength = 0;// 指向能跳跃到的最远下标
        int count = 0;// 记录跳跃次数
        int flg = 0;// 标记是否经过最远距离下标
        for (int i = 0; i < nums.length-1; i++){
            // 始终让mostLength指向最远能跳到的下标
            mostLength = Math.max(mostLength,nums[i]+i);
            // 如果i=flg 表示跳跃了一次
            if(i == flg){
                // 更新flg能到的位置
                flg = mostLength;
                // 记录次数
                count++;
            }
        }
        return count;
    }
}

第六题: 数组拆分 Ⅰ

LeetCode 561: 数组拆分 I
描述:
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi)总和最大。
返回该 最大总和 。

解题思路:

局部最优 -> 全局最优
局部最优: 优先让最大的和第二大的数分组
全局最优: 总是拿到最大可保留的值

1. 先让数组排序
2. 题目分组总是两两分组,让right下标指向数组最后一个元素.
3. 每次让right-=2,其中nums[right-1]就是第二大的数,
4. 让sum记录下每次遍历到的第二大的值

代码实现:

class Solution {
    public int arrayPairSum(int[] nums) {
        // 贪心: 总是让第二大和最大的值分到一组.
        // 排序
        Arrays.sort(nums);
        // right 指向数组最后一个元素
        int right = nums.length - 1;
        // sum 记录总和
        int sum = 0;
        while(right >= 1){
            sum += nums[right - 1];// 始终加第二大的数
            right -= 2;
        }
        return sum;        
    }
}

第七题: 雪糕的最大数量

LeetCode 1833: 雪糕的最大数量
描述:
夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
商店中新到n支雪糕，用长度为 n的数组costs 表示雪糕的定价，其中 costs[i]表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
注意：Tony 可以按任意顺序购买雪糕。

解题思路:

局部最优 -> 全局最优
局部最优: 每次都去买最小价格的雪糕
全局最优: 购买的雪糕数量最多

1. 先排序,让价格便宜的在前面
2. 只要coins小于数组i下标下的元素,表示没法购买了
3. 遍历数组,只要可以购买就count++,让coins = coins - cost[i]

代码实现:

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        // 贪心思想: 每次都买最小的
        // 先排序
        Arrays.sort(costs);
        // 如果第一个价格都大于conis 那么就一个买不了
        if(costs[0] > coins) return 0;
        int count = 0;
        // 遍历数组
        for(int i = 0; i < costs.length; i++){
            // 只要costs[i] <= coins 就代表可以买,否则就买不起了就跳出循环
            if(costs[i] <= coins){
                coins -= costs[i];
                count++;
            }else{
                break;
            }
        }
        return count;
    }
}

第八题: 数组中最大数对和的最小值

LeetCode 1877: 数组中最大数对和的最小值
描述:
一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。

• 比方说，如果我们有数对(1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8。

给你一个长度为 偶数n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

• nums 中每个元素 恰好 在 一个 数对中，
• 且最大数对和 的值 最小 。

请你在最优数对划分的方案下，返回最小的 最大数对和 。

解题思路:

局部最优 -> 全局最优
局部最优: 总是让最大的和最小的组队
全局最优: 最大数对和最小

1. 先排序
2. 定义两个指针left和right指向0下标和nums.length-1下标
3. 每次让2个元素相加并记录最大的和

代码实现:

class Solution {
    public int minPairSum(int[] nums) {
        // 贪心思想: 每次让最大和最小的组队
        // 最大数对和就最小
        // 先排序
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length-1;
        int maxTotal = nums[left] + nums[right];
        // 遍历 让 最大和最小最队,并记录每队的和,返回最大和
        while(left < right){
            maxTotal = Math.max(maxTotal,nums[left]+nums[right]);
            left++;
            right--;
        }
        return maxTotal;
    }
}