贪心算法的设计与分析

内容纲要

1、专题名称

贪心算法的设计与分析

2、实践内容

2.1 实践内容 1

（1）题目要求

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 10^4^
0 <= nums[i] <= 10^5^

（2）算法设计

这题贪心算法的核心是尽可能多到达远的地方，因此可以遍历一次数组，计算经过每格后可到达的最远的地方，并判断目前所在的格子是否为可到达的最远地方，若是最远地方，判断是否为最终格

若为是，则返回true

若为否，则返回false

（3）代码实现

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxfar = 0;
        bool yes = true;
        for(int i = 0 ; i < nums.size() ; i++ )
        {
            maxfar = max(maxfar,(nums[i]+i));
            if(maxfar == i && i != nums.size()-1)
            {
                yes = false;
                break;
            }
        }
        return yes;
    }
};

（4）算法分析

时间复杂度：O(n)

空间复杂度：O(1)

算法优点：实现简单。

缺点：稍微难想一点。

2.2 实践内容 2

（1）题目要求

平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：

每个子字符串都是平衡字符串。

返回可以通过分割得到的平衡字符串的 最大数量 。

示例 1：

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 2：

输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：

输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR" 。

提示：

2 <= s.length <= 1000
s[i] = 'L' 或 'R'
s 是一个平衡字符串

（2）算法设计

此题可以遍历一次字符数组，将问题转化为判断遍历完某个字符后的L和R是否相等，若相等，则可以组成一个平衡字符串，累加记录即可。

（3）代码实现

class Solution {
public:
    int balancedStringSplit(string s) {
        int sum = 0,left = 0,right = 0;
        for(int i = 0 ; i < s.size() ; i++ )
        {
            if(s[i] == 'R')
            right ++;
            else
            left ++;
            if(left == right)
            sum ++;
        }
        return sum;
    }
};

（4）算法分析

时间复杂度：O(n)

空间复杂度：O(1)

算法优点：空间复杂度低，时间复杂度低。

缺点：稍微难想一点。

2.3 实践内容 3

（1）题目要求

有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一ID 。

给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。

返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。

每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中任何一个。可以保证给定输入 至少有一个 有效的解。

示例 1：
```
输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释：
第一组是 [5]，大小为 1，groupSizes[5] = 1。
第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。 
其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
```
示例 2：
```
输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]
```
提示：
- groupSizes.length == n
- 1 <= n <= 500
- 1 <= groupSizes[i] <= n

（2）算法设计

使用哈希表记录每个大小的值里的i个人，遍历传入数组，当某个大小值里的人数等于该值时，打包到输出数组，以此遍历。

（3）代码实现

class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        unordered_map<int,vector<int>> groups;
        int n = groupSizes.size();
        for(int i = 0 ; i < n ; i++ )
        {
            int size = groupSizes[i];
            groups[size].push_back(i);
        }
        vector<vector<int>> groupList;
        for (auto &[size, people] : groups) {
            int groupCount = people.size() / size;
            for (int i = 0; i < groupCount; i++) {
                vector<int> group;
                int start = i * size;
                for (int j = 0; j < size; j++) {
                    group.push_back(people[start + j]);
                }
                groupList.push_back(group);
            }
        }
        return groupList;
    }
};

（4）算法分析

时间复杂度：O(n)

空间复杂度：O(n)

算法优点：稍微易想。

缺点：要对C++的哈希表有一定的理解。

2.4 实践内容 4

（1）题目要求

给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和严格大于未包含在该子序列中的各元素之和。

如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。

与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。

注意，题目数据保证满足所有约束条件的解决方案是唯一的。同时，返回的答案应当按 非递增顺序 排列。

示例 1：

输入：nums = [4,3,10,9,8]
输出：[10,9] 
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。

示例 2：

输入：nums = [4,4,7,6,7]
输出：[7,7,6] 
解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。

示例 3：

输入：nums = [6]
输出：[6]

提示：

1 <= nums.length <= 500
1 <= nums[i] <= 100

（2）算法设计

对数组进行递减排序，并对数组进行累加求总和sum，从最大的元素开始，累加求和sums直到符合sums > sum，输出遍历过的数组成的数组。

（3）代码实现

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        int sums = accumulate(nums.begin(),nums.end(),0),sum = 0;
        vector<int> res;
        sort(nums.begin(),nums.end(),greater<int>());
        for(int i = 0 ; i < nums.size() ; i++ )
        {
            sum += nums[i];
            res.push_back(nums[i]);
            if(sum > sums/2)
            break;
        }
        return res;
    }
};