c++算法贪心系列
本篇文章，同大家一起学习贪心算法！！！
第一题
题目链接
2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）
题目解析
本题重点：最终的数组和要小于原数组和的一半，且求这一操作的最少操作数
代码原理
代码编写
class Solution {
public:
int halveArray(vector<int>& nums) {
double sum = 0.0;
priority_queue<double> heap;//将数据存放进大根堆中的优势：最大的数会在堆顶
for(auto cur: nums)
{
heap.push(cur);
sum += cur;
}
sum /= 2.0;
int count = 0;
while(sum > 0)
{
double t = heap.top() / 2.0;
heap.pop();
sum -= t;
count++;
heap.push(t);
}
return count;
}
};
贪心策略
选择数组中最大的元素
第二题
题目链接
179. 最大数 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> str;
for(auto cur: nums)
{
str.push_back(to_string(cur));
}
sort(str.begin(), str.end(), [](const string& a, const string& b)
{
return a + b > b + a;
});
string ret;
for(auto& s: str)
{
ret += s;
}
if(ret[0] == '0') return "0";
return ret;
}
};
贪心策略
先看数字的最高位，与其他数字的最高位进行比较，大的在前小的在后
注意：一切都以每个数的最高位为比较对象
第三题
题目链接
376. 摆动序列 - 力扣（LeetCode）
题目解析
相信大家对这道题已经不再陌生，因为我们上一次做这题的时候是用动态规划的方法去做的题，当然这次博主依旧为给大家简单解析一下这题
注意：这里的加号表示递增，减号表示递减！！！大体可以参考高中时学过的单调性
代码原理
将一个波分成两段分析，因此就有了left和right，left的状态（是上升还是下降）由后面的i+1的元素决定，right的状态则需要i + 1元素和i元素决定。
由于起点无法判断它的状态因此要长度减1,也因此最后的子序列长度要加1
代码编写
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(n < 2) return n;
int ret = 0, left = 0;
for(int i = 0; i < n - 1; i++)
{
int right = nums[i + 1] - nums[i];
if(right == 0) continue;
if(right * left <= 0) ret++;
left = right;
}
return ret + 1;
}
};
贪心策略
画图 + 状态走向
那么本篇文章的内容就先到这里，我们下期文章再见！！！！
记得一键三联哦！！！
