微商手机网站制作公司哪家好,bing搜索国内版,做网站多少人,重庆app制作开发商✨感谢您阅读本篇文章#xff0c;文章内容是个人学习笔记的整理#xff0c;如果哪里有误的话还请您指正噢✨ ✨ 个人主页#xff1a;余辉zmh–CSDN博客 ✨ 文章所属专栏#xff1a;贪心算法篇–CSDN博客 文章目录 一.贪心算法1.什么是贪心算法2.贪心算法的特点 二.例题1.柠… ✨感谢您阅读本篇文章文章内容是个人学习笔记的整理如果哪里有误的话还请您指正噢✨ ✨ 个人主页余辉zmh–CSDN博客 ✨ 文章所属专栏贪心算法篇–CSDN博客 文章目录 一.贪心算法1.什么是贪心算法2.贪心算法的特点 二.例题1.柠檬水找零2.将数组和减半的最小操作次数3.最大数4.摆动序列 一.贪心算法
1.什么是贪心算法
贪心算法Greedy Algorithm)是一种在每一步选择中都采取在当前状态下的最优决策的算法策略。他并不从整体最优上加以考虑而是做出在当前看来是最好的选择。
1.把解决问题的过程分为若干步骤。
2.解决每一步时都选取当前看起来最优的选择。
3.“希望”得到全局最优解。注意是“希望”可不一定就是最优解
简单形容就是贪婪鼠目寸光因此叫做贪心算法。
下面介绍几个典型的示例 2.贪心算法的特点
贪心策略的提出 贪心策略的提出是没有标准和模板的可能每一道题的贪心策略都是不同的因此在学习贪心算法的时候重点要掌握每一道题的策略把这道题的策略当成经验。 贪心策略的正确性 前面提到一个词“希望”得到最优解因为有可能“贪心策略是一个错误的方法正确的贪心策略是需要严格的数学证明。
二.例题
1.柠檬水找零
题目 算法原理
根据题意可以明白顾客付钱有三种情况如果是5美元那就直接收下如果是10美元并且当前手里5美元的数量大于等于1收下然后找零5美元如果没有5美元则返回false如果是20美元有两种找零方式第一种105第二种555这里就用到了贪心的思想优先使用第一种方式找零。如果第一次20美元使用第二种找零方式恰好手里有三张5美元一张10美元如果第一次就使用三张5美元等之后再次遇到10美元就只剩一张10美元不能找零。
这里用到的是交换论证法如果20美元使用第二种找零方式手里的10美元一直到最后也没有使用因此10美元可以替换20美元找零时的两张5美元如果第一次20美元使用第二种找零方式555第二次使用第一种方式找零105第二次的10可以和第一次的两张5交换交换后无影响。
代码实现
bool lemonadeChange(vectorint bills){//设置两个变量一个用来表示5元的个数一用来表示10元的个数int five 0, ten 0;for(auto x : bills){//如果给的是5元直接收下if(x5){five;}//如果给的是10元先判度是否有5元找零有就找零收下没有就返回if(x10){if(five0){return false;}else{five--;ten;}}//如果给的是20元有三种情况if(x20){//贪心思想优先考虑105找零if(tenfive){five--;ten--;}//第一种不能找零再考虑第二种找零方式555else if(five3){five - 3;}//如果两种情况都不能找零返回else{return false;}}}return true;
}2.将数组和减半的最小操作次数
题目 算法原理
因此本道题的贪心策略使用最少的操作次数完成数组和的减半因此每次选择一个数减半时都选择最大的那个数减半这里就是贪心的思想每次都选择最大的数减半。既然要快速获取数组中的最大数就可以借助大根堆这个数据结构每次都选择堆顶的元素减半减半后从新放回堆中调整然后循环进行知道数组和减到一半返回最小操作数。
代码实现
int halveArray(vectorint nums){//建立一个大根堆priority_queuedouble heap;//遍历数组求和并存放到堆中double sum 0.0;for(int x : nums){heap.push(x);sum x;}//先获取数组和的一半每次减去堆顶元素的一半直到减为小于等于0sum / 2.0;int count0;while(sum0){//获取堆顶元素的一半,并删去double t heap.top() / 2.0;heap.pop();count;sum - t;heap.push(t);}return count;
}3.最大数
题目 算法原理
根据题意要求可以自定义排序规则因为要返回的是组合后最大的数所以按照自定义的排序规则从大到小的排序比如现在有两个数a和b有两种组合方式ab和ba如果组合后abba则a在前b在后如果abba则ab如果abba则b在前a在后比如示例一a10b2组合后ab102ba210所以b(2)在前a(10)在后根据自定义排序规则将整个数组中的元素都排序后然后从前往后组合就是要找的最大数。
这里有一个细节点如何快速的将两个数组合比较可以先将每一个数都转化成字符串的形式组合时直接的将两个字符串相加拼接即可这样就能快速的组合最后排完序后还可以直接从前往后将所有字符串拼接就是要返回的结果。
至于为什么上面的这个自定义排序规则是正确的可以看下面的证明过程 代码实现
string largestNumber(vectorint nums){//先将每个数字转换成字符串存放到字典数组中vectorstring dictionary;for(auto x : nums){dictionary.push_back(to_string(x));}//使用Lambda表达式自定义排序规则sort(dictionary.begin(), dictionary.end(), [](const string s1, const string s2){return s1 s2 s2 s1; });string ret;for(auto s : dictionary){ret s;}if(ret[0]0){return 0;}return ret;
}4.摆动序列
题目 算法原理 代码实现
//全局变量表示左侧的峰值
int left 0;
int wiggleMaxLength(vectorint nums){//寻找波峰和波谷int ret 0;for (int i 0; i nums.size(); i){//如果是最后一个位置直接1if(inums.size()-1){ret;break;}//先计算当前位置右侧的峰值int right nums[i 1] - nums[i];//如果右侧峰值等于0跳过if(right0){continue;}//如果左右两侧峰值相乘小于0表示当前位置是波峰或者波谷if(left*right0){ret;}//将当前位置的右侧峰值赋值给左侧表示下一个位置的左侧峰值left right;}return ret;
}以上就是关于贪心算法以及一些练习题的讲解如果哪里有错的话可以在评论区指正也欢迎大家一起讨论学习如果对你的学习有帮助的话点点赞关注支持一下吧
