专业做网站的团队推荐,wordpress oa插件下载,集团公司网站怎么做,建立网站的基本过程1. 柠檬水找零 这一个题目是一个比较简单的模拟算法#xff0c;只需要根据手里的钱进行找零即可#xff0c;对于贪心的这一点#xff0c;主要是在20元钱找零的情况下#xff0c;此时会出现两种情况#xff1a;10 5 的组合 和 5 5 5 的组合#xff0c;根据找零的特点只需要根据手里的钱进行找零即可对于贪心的这一点主要是在20元钱找零的情况下此时会出现两种情况10 5 的组合 和 5 5 5 的组合根据找零的特点5元钱可以对10元和20元找零而10元钱只能对20找零5元钱的作用相对较大所以根据贪心的思想我们是对于20元找零优先0 5 的组合直接上思路
C 算法代码 注意由于本题最大的面值是20元所以只需要统计5元和10元的数量即可。
class Solution {
public:bool lemonadeChange(vectorint bills) {int five 0, ten 0;for (auto x : bills){if (x 5) five; // 5 元直接收下else if (x 10) // 10 元找零 5 元{if (five 0) return false;else five--; ten;}else // 20 元分情况讨论{// 优先处理组合:10 5if (ten ! 0 five ! 0) // 贪⼼{ten--; five--;}// 其次处理组合:5 5 5else if (five 3){five - 3;}else return false;}}return true;}
};
2. 将数组和减半的最少操作次数 我们来看看这个题目将数组和减半的最少操作此时根据贪心的策略只要我们每次都选择最大值将最大值依次减半就可以控制到操作次数最少直接看思路 C 算法代码
class Solution {
public:int halveArray(vectorint nums){priority_queuedouble heap; // 创建⼀个⼤根堆double sum 0.0;for (int x : nums) // 把元素都丢进堆中并求出累加和{heap.push(x);sum x;}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;}
};
3. 最大数 这个题目依然是采用贪心来解决将所有的数字当成字符串处理那么两个数字之间的拼接操作以及比较操作就会很方便此时我们只需要找出每次两个值组合的最大的排序方式重新定义⼀个新的排序规则然后排序即可即可解决问题。 C 算法代码
细节问题有可能数组中所有的元素都是0此时结果会有很多0因此我们需要单独去除前导0。
class Solution
{
public:string largestNumber(vectorint nums){// 优化把所有的数转化成字符串vectorstring strs;for (int x : nums) strs.push_back(to_string(x));// 排序 - lambda表达式sort(strs.begin(), strs.end(), [](const string s1, const string s2){return s1 s2 s2 s1;});// 提取结果string ret;for (auto s : strs) ret s;if (ret[0] 0) return 0;return ret;}
};
4. 摆动序列 何为一个摆动序列我们可以类比一个折线图题目上要求我们求出最长的摆动序列那么根据贪心的思想我们希望到达峰值或者峰低的点尽量大或者小以此来达到最长的要求直接上思路 C 算法代码
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;}
};
