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 <= 1000s[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 == n1 <= n <= 5001 <= 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 <= 5001 <= 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;
}
};（4）算法分析
时间复杂度：O(n)
空间复杂度：O(n)
算法优点：时间复杂度优，且简单易想。
缺点：空间复杂度一般
3、问题与总结
问题：以上题目都可用C++的API更简单地解题，学习这些API用了较长时间。
总结：总体耗时较短，且对C++STL库的使用更加熟练
4、完成情况证明
Comments NOTHING