share poine 户做网站,在线字体设计,建设网络平台 英语,如何创建博客网站本篇文章#xff0c;同大家一起学习贪心算法#xff01;#xff01;#xff01; 第一题
题目链接
2208. 将数组和减半的最少操作次数 - 力扣#xff08;LeetCode#xff09;
题目解析 本题重点#xff1a;最终的数组和要小于原数组和的一半#xff0c;且求这一操作的…本篇文章同大家一起学习贪心算法 第一题
题目链接
2208. 将数组和减半的最少操作次数 - 力扣LeetCode
题目解析 本题重点最终的数组和要小于原数组和的一半且求这一操作的最少操作数
代码原理 代码编写
class Solution {
public: int halveArray(vectorint nums) { double sum 0.0; priority_queuedouble 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(vectorint nums) { vectorstring 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和rightleft的状态是上升还是下降由后面的i1的元素决定right的状态则需要i 1元素和i元素决定。
由于起点无法判断它的状态因此要长度减1,也因此最后的子序列长度要加1
代码编写
class Solution {
public: int wiggleMaxLength(vectorint 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; }
};
贪心策略
画图 状态走向
那么本篇文章的内容就先到这里我们下期文章再见 记得一键三联哦
