【每日多题之贪心】

文章目录

• • • 1、分割平衡字符串
    • • 1.1、题目描述
      • 1.2、题目分析
      • 1.3、代码实现
    • 2、最少 *** 作数使数组递增
    • • 2.1、题目描述
      • 2.2、题目分析
      • 2.3、代码实现
    • 3、卡车上的最大单元数
    • • 3.1、题目描述
      • 3.2、题目分析
      • 3.3、代码实现
      • 3.4、总结
    • 4、打折购买糖果的最小开销
    • • 4.1、题目描述
      • 4.2、题目分析
      • 4.3、代码实现

道阻且长，行则将至。

1、分割平衡字符串 1.1、题目描述

1221. 分割平衡字符串

    在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。
示例：
输入：s = “RLRRLLRLRL”
输出：4
解释：s 可以分割为 “RL”、“RRLL”、“RL”、“RL” ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。

1.2、题目分析

    （1）明确题目中说明的 s s s一定是平衡字符串
    （2）计数问题，遍历容器，遇到字符 L L L，和计数器加一，否则就减一，当和计数器为0的时候说明前面走过的字符串是一个平衡字符串，则答案计数器加一。

1.3、代码实现

class Solution {
public:
    int balancedStringSplit(string s) {
        int cnt = 0;
        int sum = 0;
        int i;
        for(i = 0; i < s.size(); ++i){
            sum += (s[i] == 'L' ? 1 : -1);
            if(sum == 0){
                ++cnt;
            }
        }
        
        return cnt;
    }
};

2、最少 *** 作数使数组递增 2.1、题目描述

1827. 最少 *** 作数使数组递增

给你一个整数数组 nums（下标从 0 开始）。每一次 *** 作中，你可以选择数组中一个元素，并将它增加 1 。
    比方说，如果nums = [1,2,3] ，你可以选择增加 nums[1] 得到
     nums = [1,3,3] 。
请你返回使 nums严格递增 的 最少 *** 作次数。
我们称数组 nums是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 1 的数组是严格递增的一种特殊情况。
示例：
输入：nums = [1,1,1]
输出：3
解释：你可以进行如下 *** 作：
1)增加 nums[2] ，数组变为 [1,1,2] 。
2)增加 nums[1] ，数组变为 [1,2,2] 。
3)增加 nums[2] ，数组变为 [1,2,3] 。

2.2、题目分析

    （1）一般简单题进行模拟都可以做出来；
    （2）维护一个变量pre记录已经完成递增任务的元素，维护一个答案变量ans。从第二个数开始遍历数组，当nums[i]小于pre时，就要更新当前的nums[i]为使递增的最小数(pre+1) （这里的更新只是思想上更新，并不是真的进行更新），并记录变化量(pre+1) - nums[i]，还要记得更新pre的值；当num[i大于pre的时候不需要进行 *** 作，只要更新pre就好了。

2.3、代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int pre = nums[0];
        int i;
        int ans = 0;
        for(i = 1; i < nums.size(); ++i){
            if(nums[i] <= pre){
                ans += (pre+1) - nums[i];
                pre += 1;
            }
            else{
                pre = nums[i];
            }
        }
        
        return ans;
    }
};

3、卡车上的最大单元数 3.1、题目描述

1710. 卡车上的最大单元数

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，
其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
    numberOfBoxesi 是类型 i 的箱子的数量。
    numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
返回卡车可以装载 单元 的 最大 总数。
示例：
输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
-1 个第一类的箱子，里面含 3 个单元。
-2 个第二类的箱子，每个里面含 2 个单元。
-3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8

3.2、题目分析

    （1）贪心的思想，每次都选取当前truckSize下包含最多单元的箱子；
    （2）首先对二维数组按照进行第二个元素进行排序，然后遍历二维数组，利用贪心思想解决。

3.3、代码实现

class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxes, int truckSize) {
        sort(boxes.begin(), boxes.end(), [](const vector<int> v1, const vector<int> v2){
            return v1[1] > v2[1];
        });
        int ans = 0;
        int i, n = boxes.size();
        int currNum = 0;
        for(auto &box : boxes){
            if(box[0] <= truckSize){
                ans += box[0] * box[1];
                truckSize -= box[0];
            }
            else{
                ans += truckSize * box[1];
                break;
            }
        }
        
        return ans;
    }
};

3.4、总结

    （1）与其说是总结，不如说是对本题知识点的回顾吧；
    （2）贪心思想：选取当前最优解得到的结果就是全局最优解，本题中就是每次都选取当前truckSize下可以包含的最大单元的那个箱子；
    （3）排序 *** 作，利用的是快排，时间复杂度是O（nlogn)，并且是自定义排序，是sort()函数的一个重载版本，第三个参数是一个 谓词 ，利用的是 lambda表达式 来实现的；
    （4）谓词 是一个可调用的表达式，其返回结果是一个能被用做条件的值，具体用法可见《C++ Primer中文版（第五版）》约344页；
    （5）、lambda表达式 表示一个可调用的代码单元，其 捕获列表 可以为空但不能省略，参数列表 可以省略，函数体 不可以省略，具体用法可见《C++ Primer中文版（第五版）》约345页.

4、打折购买糖果的最小开销 4.1、题目描述

2144. 打折购买糖果的最小开销

一家商店正在打折销售糖果。每购买 两个 糖果，商店会 免费 送一个糖果。
免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的 较小值 。
    比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。
给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有 糖果的 最小 总开销。
示例：
输入：cost = [1,2,3]
输出：5
解释：我们购买价格为 2 和 3 的糖果，然后免费获得价格为 1 的糖果。
总开销为 2 + 3 = 5 。这是开销最小的 唯一 方案。
注意，我们不能购买价格为 1 和 3 的糖果，并免费获得价格为 2 的糖果。
这是因为免费糖果的价格必须小于等于购买的 2 个糖果价格的较小值。

4.2、题目分析

    （1）为了减小开销，一定是要尽可能的获得更多 免费 的糖果，那么就是每买两颗，送一颗。

4.3、代码实现

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        sort(cost.begin(), cost.end(), greater());
        int i, n = cost.size();
        int ans = 0;
        for(i = 0; i < n; ++i){
            ans += cost[i];
            if(i+1 < n){
                ans += cost[i+1];
            }
            else{
                break;
            }
            i += 2;
        }
        
        return ans;
    }
};