c++贪心系列
各位小伙伴们新年好呀，这是年后的第一篇文章，那么还是一样，我们继续学习这个贪心算法。
第一题
题目链接
2418. 按身高排序 - 力扣（LeetCode）
题目解析
代码原理
方法一
1.先创建一个下标数组，将两个数组所对应的数据的下标创建成一个数组
2.对下标数组进行排序，依靠升高的数据对下标数组进行排序
3.通过重新排序后的下标数组进行重新尾插names数组的数据
方法二
1.使用哈希表存映射关系
2.对身高数组进行排序
3.根据排序后的结果，往哈希表里找名字
代码编写
方法一
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n = names.size();
vector<int> index(n);
for(int i = 0; i < n; i++)
{
index[i] = i;
}//先创建一个下标数组
sort(index.begin(), index.end(), [&](const int i, const int j)
{
return heights[i] > heights[j];
});//排序
vector<string> ret;
for(auto cur: index)
{
ret.push_back(names[cur]);
}//重新尾插
return ret;
}
};
方法二
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n = names.size();
unordered_map<int, string> hash(n);
for(int i = 0; i < n; i++)
{
hash[heights[i]] = names[i];
}
sort(heights.begin(), heights.end(), greater<int>());
vector<string> ret;
for(int i = 0; i < n; i++)
{
ret.push_back(hash[heights[i]]);
}
return ret;
}
};
本题总结
如何想到
出现两组数据，且是可以一一对应的关系
方法&思路
1.哈希表，类型是unorder_map<数据类型一， 数据类型二>，然后重新插入另一个数组的数据
2.将两个数组所对应的数据的下标创建成一个数组，先根据一个数组的数据大小进行排序，再重新插入另一个数组的数据
第二题
在讲解这题之前，如果小伙伴们感兴趣可以先去了解一下田忌赛马这个故事，当然，博主也给大家准备了一个类似田忌赛马故事的小视频
日常分享
题目链接
870. 优势洗牌 - 力扣（LeetCode）
题目解析
根据视频中的田忌赛马原理，先用一组数据中的最小值与另一组的最小值进行比较，若比不过则拖走对面的最大值
代码原理
原理大家都已经清楚了，就是田忌赛马，但是如何把它转化成代码呢？利用指针即可当第一组中的最小值小于第二组的最小值时，直接将其从右边插入到结果的数组中，反之，则从左边插入
其次这里也用到了上一题我们总结过的下标数组，先将第一组的数据进行排序，并取它们的下标作为数组，之后再根据下标数组对第二个数组进行排序
代码编写
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
//将第一数组进行排序
sort(nums1.begin(), nums1.end());
//创建下标数组
int n = nums1.size();
vector<int> index(n);
for(int i = 0; i < n; i++)
{
index[i] = i;
}
//对第二个数组进行排序
sort(index.begin(), index.end(), [&](const int& i, const int& j){
return nums2[i] < nums2[j];
//nums2[i] > nums2[j] 这是降序
});
//小圣贤庄比武
vector<int> ret(n);
int left = 0, right = n - 1;
for(auto cur: nums1)
{
if(cur > nums2[index[left]]) ret[index[left++]] = cur;
else ret[index[right--]] = cur;
}
return ret;
}
};
本题总结
方法总结
题型特征
类似田忌赛马
方法&思路
思路：田忌赛马的思路、下标数组、根据下标数组进行排序
方法：利用指针即可当第一组中的最小值小于第二组的最小值时，直接将其从右边插入到结果的数组中，反之，则从左边插入
第三题
题目链接
409. 最长回文串 - 力扣（LeetCode）
题目解析
回文数组：以某一个字母为对称轴，对称轴两边的字母要保持一模一样
上图中的回文数组的长度要从第一个d开始算起
注意：只有一个字母时也是回文数组
代码原理
1. 如果字符的个数偶数个，那么全部都可以⽤来构造回⽂串；
2. 如果字符的个数奇数个，减去⼀个之后，剩下的字符能够全部⽤来构造回⽂串；
3. 最后再判断⼀下，如果有字符出现奇数个，就把它单独拿出来放在中间。
那么如何统计字符个数，我们使用哈希表即可（如何写，见代码编写部分）
代码编写
class Solution {
public:
int longestPalindrome(string s) {
int hash[2010];
//计数
for(auto cur: s)
{
hash[cur]++;
}
//统计结果
int ret = 0;
for(auto cur: hash)
{
ret += cur / 2 * 2;//这里只统计了偶数部分
}
return ret < s.size()? ret + 1: ret;
}
};
本题总结
思路&方法
哈希表计数：hash[cur]++
cur/2*2的思路
第四题
题目链接
942. 增减字符串匹配 - 力扣（LeetCode）
题目解析
代码原理
遇到‘I’则prem[i]这个位置的数此时是最小的
遇到‘D’则prem[i]这个位置的数此时是最大的
代码编写
class Solution {
public:
vector<int> diStringMatch(string s) {
int n = s.size();
vector<int> ret;
int left = 0, right = n;
for(auto cur: s)
{
if(cur == 'I') ret.push_back(left++);
else ret.push_back(right--);
}
ret.push_back(left);//把最后一个数放进去
return ret;
}
};
第五题
题目链接
455. 分发饼干 - 力扣（LeetCode）
题目解析
代码原理
优先满足胃口小的小朋友
代码编写
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int ret = 0, m = g.size(), n = s.size();
for(int i = 0, j = 0; i < m && j < n; i++, j++)
{
while(j < n && s[j] < g[i])
{
j++;
}
if(j < n) ret++;
}
return ret;
}
};
第六题
题目链接
553. 最优除法 - 力扣（LeetCode）
题目解析
代码原理
a * c * d / b
代码编写
class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
if(n == 1)
{
return to_string(nums[0]);
}
if(n == 2)
{
return to_string(nums[0]) + "/" + to_string(nums[1]);
}
string ret;
ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
for(int i = 2; i < n; i++)
{
ret += "/" + to_string(nums[i]);
}
ret += ")";
return ret;
}
};
本题总结
方法&思路
思路：a * c * d / b
方法：to_string(元素)//用于转换数据类型
第七题
题目链接
45. 跳跃游戏 II - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int left = 0, right = 0, ret = 0, max_position = 0;
while(left <= right)
{
if(max_position >= n - 1) return ret;
for(int i = left; i <= right; i++)
{
max_position = max(max_position, nums[i] + i);
}
left = right + 1;
right = max_position;
ret++;
}
return -1;
}
};
思路总结：
先模拟走一遍，拿到最大长度后，先更新left和right，再判断是否能够到达最后一个位置，若能达到则返回次数，反之则返回-1。其中更新left和right时先更新left,再更新right，并且right要为往后的最大长度。
变式题
题目链接
55. 跳跃游戏 - 力扣（LeetCode）
代码编写
class Solution {
public:
bool canJump(vector<int>& nums) {
int ret = 0, left = 0, right = 0, maxPos = 0;
int n = nums.size();
while(left <= right)
{
if(right >= n - 1) return true;
for(int i = left; i <= right; i++)
{
maxPos = max(maxPos, nums[i] + i);
}
left = right + 1;
right = maxPos;
}
return false;
}
};
第九题
题目链接
题目解析
代码原理
规律怎么来？
代码编写
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
for(int i = 0; i < n; i++)
{
int ret = 0, step = 0, index = 0;
for(; step < n; step++)
{
index = (i + step) % n;
ret += gas[index] - cost[index];
if(ret < 0) break;
}
if(ret >= 0) return i;
i += index;
}
return -1;
}
};
本题总结
如何提取规律
结合题意，借用仅有的例子，列举一些符合题意和不合题意的例子，从中总结一些规律
本篇文章的内容就先到这里，我们下期文章再见！！！
