c++算法贪心系列
本篇文章，同各人一起学习贪心算法！！！https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMWYzNzA1MzZiNzMwNDQ4NGE3ZmM2M2UxYTRmY2U4NzguZ2lm
第一题
标题链接
2208. 将数组和减半的最少操纵次数 - 力扣（LeetCode）
标题分析
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNzE4ZmMwMGJhNmRhNDRkNThiOTQ4NzA3N2I4NDJmOTAucG5n
本题重点：终极的数组和要小于原数组和的一半，且求这一操纵的最少操纵数
代码原理
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYTM2N2UzY2MzMjdhNGVhMjliMjk4NDZiZGFkZmI4YTMucG5n
代码编写
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）
标题分析
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjVjNTJmODY4YWMxNGUxZDhjMDEwNDQxYzAyYWRlOGEucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMWUwNmNmNmIyYTY5NDA0Mzg1NzI5MDExMDM5NmY2ODYucG5n
代码原理
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjVkZGNjMjhmZDIxNDE1YTgzZmJhNzc2Yjk5NWZkOWMucG5n
代码编写
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') return "0";
return ret;
}
};
贪心战略
先看数字的最高位，与其他数字的最高位举行比力，大的在前小的在后
留意：齐备都以每个数的最高位为比力对象
第三题
标题链接
376. 摆动序列 - 力扣（LeetCode）
标题分析
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYjc5OGRiNGQwM2NkNDRhMmEyNjA5NzA1MmNkNWM2MDkucG5n
信任各人对这道题已经不再陌生，由于我们上一次做这题的时间是用动态规划的方法去做的题，固然这次博主仍旧为给各人简单分析一下这题
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYTU4YTM2MWZlZjc1NGY3MThiYzM2MjY3ZjNlNDI2NDIucG5n
留意：这里的加号表现递增，减号表现递减！！！大要可以参考高中时学过的单调性
代码原理
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMWUzODgzMjNhNmU4NDRmZmI0MWY5MmZjOTdjZjFlNTkucG5n
将一个波分成两段分析，因此就有了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 - nums;
if(right == 0) continue;
if(right * left <= 0) ret++;
left = right;
}
return ret + 1;
}
};
贪心战略
画图 + 状态走向
那么本篇文章的内容就先到这里，我们下期文章再见！！！！
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZGZjYTYyNTBhYmIxNGRkNDlmN2FmZTYyNjFjOWIzY2QuZ2lm
记得一键三联哦！！！
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZjE1M2VjYzIyNmZmNDEzMGFiYjhmMjA5NmQxM2FjYWMuZ2lm
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]