淮安网站优化,vi设计公司山猫,flashfxp上传多个网站,水滴信用企业查询官网目录 柠檬水找零
题解#xff1a;
代码#xff1a;
将数组和减半的最少操作次数#xff08;大根堆#xff09;
题解#xff1a;
代码#xff1a;
最大数#xff08;注意 sort 中 cmp 的写法#xff09;
题解#xff1a;
代码#xff1a;
摆动序列#xff0…目录 柠檬水找零
题解
代码
将数组和减半的最少操作次数大根堆
题解
代码
最大数注意 sort 中 cmp 的写法
题解
代码
摆动序列如何判断波峰、波谷、平台
题解
代码 贪心策略 解决问题的策略局部最优- 全局最优 1、把解决问题的过程分为若干步 2、解决每一步的时候都选择当前看起来“最优的”解法 3、希望得到全局最优解。 柠檬水找零
860. 柠檬水找零 - 力扣LeetCodehttps://leetcode.cn/problems/lemonade-change/description/ 题解 假设当前顾客付了 5 美元则无需找零摊主手中 5 美元的张数1 假设当前顾客付了 10 美元那么摊主需要返还 5 美元 如果摊主手中有 5 美元则摊主手中 10 美元的张数 1且返还顾客 5 美元即摊主手中 5 美元的张数 -1 如果摊主手中没有 5 美元说明摊主此时无法找零直接返回 false 假设当前顾客付了 20 美元那么摊主需要返还 15 美元 如果摊主手中有 10 美元 和 5 美元则摊主手中 10 美元和 5 美元的张数都 -1如果摊主手中有 3 张 5 美元则摊主手中 5 美元的张数 -3 在可以找零的这两种情况中就可以体现贪心策略。可以发现在找零的过程中5 美元经常使用所以不能让 5 美元的张数太快消耗完可能会影响后面找零所以在返还 15 美元的情况下应该优先返还 1张 10 美元和 1张 5 美元其次选择返还 3张 5 美元。 代码
class Solution {
public:bool lemonadeChange(vectorint bills) {int ten0,five0;for(auto x:bills){if(x5) five;else if(x10){if(five0){five--; ten;}else return false;//无法找零}else//x20{if(ten0 five0)//找105{ten--; five--;}else if(five3) five-3;//没有10找555else return false;//无法找零}}return true;}
};
将数组和减半的最少操作次数大根堆
2208. 将数组和减半的最少操作次数 - 力扣LeetCodehttps://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/ 题解 数组减半的最少操作数其实就是找到数组中的最大值并将其减半为了方便找到数组的最大值可以使用大根堆找到堆顶元素将其减半后再次放回大根堆中直到数组和减半就可以得出最少操作数。 代码
class Solution {
public:int halveArray(vectorint nums) {priority_queuedouble p;double sum0.0;for(auto x:nums){p.push(x);sumx;}sum/2.0;int count0;while(sum0){double tmpp.top();p.pop();tmp/2.0;sum-tmp; p.push(tmp);count;}return count;}
};
最大数注意 sort 中 cmp 的写法
179. 最大数 - 力扣LeetCodehttps://leetcode.cn/problems/largest-number/description/ 题解 以示例一为例数字 10 和数字 2 拼在一起会得到数字 102 和数字 210由于 210 102所以返回 210 以示例二为例我们可以对数组排序 数字 3 和 数字 30 拼在一起得到数字 330 和 数字 303由于 330 303所以 数字 3 和 数字 30 排序后为 [ 3 , 30 ] 数字 30 和 数字 34 拼在一起得到数字 3430 和数字 3034所以排序结果为 [ 34, 30 ]数字 34 再和 数字 3 拼在一起得到343 和 334所以最终排序结果为 [ 34 , 3 , 30 ] 用这个规则排序后得到的数组为 [ 9 , 5 , 34 , 3 , 30 ]最终拼到的最大数为 9534330。 可以看出排序的规则就是把两个数 a 和 b 拼在一起拼接后的数为 ab 和 ba 若 ab baa 就排在 b 前面若 ab bab 就排在 a 前面。 为了方便拼接和比较大小可以把数字都转换为字符串比较拼接后字符串的字典序 字典序 ab ba a 排在前面;字典序 ab ba b 排在前面。 代码
class Solution {
public:string largestNumber(vectorint nums) {vectorstring str;for(auto x:nums){str.push_back(to_string(x));}sort(str.begin(),str.end(),[](const string s1,const string s2){ return s1s2s2s1; });string ret;for(auto x:str)retx;if(ret[0]0) return 0;else return ret;}
};
摆动序列如何判断波峰、波谷、平台
376. 摆动序列 - 力扣LeetCodehttps://leetcode.cn/problems/wiggle-subsequence/description/ 题解
以示例二为例将数字的升降趋势画出图 可以看出图中存在波峰极大值波谷极小值波峰和波峰左、右边的数的差值恰好一正一负 波谷和波谷左、右边的数的差值恰好一正一负 满足摆动序列的条件即数组中所有的极大值和极小值构成的子数组就是题目所说的摆动序列我们只需要得到摆动序列的长度即可。 判断一个数和这个数左边的数的差值为 left和右边的数的差值为 right判断 left * right 是否小于 0 就可以知道这个数是不是极大/小值。 同时数组最左端和最右端的数也可以视为极大值或极小值也应该被计入摆动序列中但最左端的数左边没有数字了最右端的数右边没有数字了没办法用 left * right 的积是否小于 0 来判断是否为极大/小值。 针对最左端的数我们将 left 初始化为 0left * right 为 0摆动序列的长度 1就可以解决最左端的问题针对最右端的数在整个数组判断完 left * right 之后得到的摆动序列的长度 1 即可。 但是 left * right 0 还有以下特殊情况也就是出现了平台 1、数组中连续的几个数的数值相等即 right 0但这几个数总体是呈现上升或下降趋势的并没有极大/小值 2、数组中连续的几个数的数值相等即 right 0但这几个数中总体上是存在极大/小值的把这几个数值相同的点视为一个点的话 当 right 0 时说明存在平台我们可以跳过平台 不要计算 left * right避免与最左端的情况的判断混淆跳过平台后left 是平台左边的差值right 是平台右边的差值 left * right 0 则摆动序列的长度 1该平台中存在极大/小值选择平台中的任意一点计入摆动序列即可。 代码
class Solution {
public:int wiggleMaxLength(vectorint nums) {int left0,ret0,nnums.size();for(int i0;in-1;i){int rightnums[i1]-nums[i];if(right0) continue;//平台else if(left*right0) ret;//存在波峰或波谷leftright;}return ret1;//数组的最左/右端也算是波峰/波谷}
};
