做网站套路,甘肃网站建设公司,公众号平台网页版登录入口,wordpress完美搬家作者 | 王磊来源 | Java中文社群#xff08;ID#xff1a;javacn666#xff09;转载请联系授权#xff08;微信ID#xff1a;GG_Stone#xff09;这几年商家为了刺激消费是变着花样的推出各种各样的活动#xff0c;以某多多为首的运营式电商更是让我们看到了营销的无限“… 作者 | 王磊来源 | Java中文社群IDjavacn666转载请联系授权微信IDGG_Stone这几年商家为了刺激消费是变着花样的推出各种各样的活动以某多多为首的运营式电商更是让我们看到了营销的无限“潜力”。这不最近刚赶上双 11小区便利店的老王头也推出了一项「空酒瓶子换酒」的促销活动它的规则是这样的。本文已收录至 Github《小白学算法》系列https://github.com/vipstone/algorithm活动规则客户购买 X 瓶酒就可以用 Y 个空酒瓶来兑换一瓶新酒。提示X 和 Y 的取值如下1 X 1002 Y 100Y 值不固定随机抽取。如果喝掉了酒瓶中的酒那么酒瓶就会变成空的。请你计算最多能喝到多少瓶酒。示例 1输入X 9, Y 3输出13解释你可以用 3 个空酒瓶兑换 1 瓶酒。所以最多能喝到 9 3 1 13 瓶酒。示例 2输入X 15, Y 4输出19解释你可以用 4 个空酒瓶兑换 1 瓶酒。所以最多能喝到 15 3 1 19 瓶酒。示例 3输入X 5, Y 5输出6示例 4输入X 2, Y 3输出2解题思路这道题难点有两个第一用多少个空瓶换一瓶酒是不固定的随机的第二兑换的酒喝完之后还能继续参与兑换活动。因此要在满足这两个的前提条件下计算自己最多能喝到几瓶。可能有些朋友看到了本篇标题之后就知道了解题思路没错我们本文就是要用「贪心算法」来计算最终答案。同时这道题也符合贪心算法的解题思路那就是有酒瓶就兑换、能兑换多少就兑换多少。贪心算法贪心算法Greedy Algorithm又称贪婪算法是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说问题能够分解成子问题来解决子问题的最优解能递推到最终问题的最优解。贪心算法的实现框架从问题的初始解出发while能朝给定总目标前进一步{ 利用可行的决策求出一个可行解元素}由所有解元素组合成问题的一个可行解。注意因为用贪心算法只能通过解局部最优解的策略来达到全局最优解因此一定要注意判断问题是否适合采用贪心算法策略找到的解是否一定是问题的最优解。接下来我们就用代码来演示一下贪心算法的具体实现。代码实现 1贪心首先我们先把全局问题转换成局部问题当空瓶子能换一瓶酒的时候我们就换一瓶酒实现代码如下// 贪心1用 和 - 实现
class Solution {public int numWaterBottles(int numBottles, int numExchange) {// 最大酒瓶数int total numBottles;// 有酒瓶就兑换while (numBottles numExchange) {// 执行一轮兑换numBottles - numExchange;total;// 兑换一次多一个酒瓶numBottles;}return total;}
}
代码解析实现思路先把所有酒喝掉 int total numBottles有足够的空瓶就去换一瓶酒执行一次 while 循环在循环中空瓶的数量 1能喝到酒的数量 1执行下一次循环判断。我们将以上代码提交至 LeetCode执行结果如下代码实现 2贪心改进以上的贪心算法是一瓶酒一瓶酒进行循环兑换的那我们可否每次将所有的空瓶子全部兑换完可兑换的最大值然后将兑换的酒再喝完再进行下一次兑换答案是肯定的我们只需要使用取模和取余操作就可以实现了具体代码如下// 贪心 2用 / 和 % 实现
class Solution {public int numWaterBottles(int numBottles, int numExchange) {// 总酒瓶数int total numBottles;// 有酒瓶就兑换while (numBottles numExchange) {// 最多可兑换的新酒int n numBottles / numExchange;// 累计酒瓶total n;// 剩余酒瓶(剩余未兑换 已兑换喝掉的)numBottles numBottles % numExchange n;}return total;}
}
我们将以上代码提交至 LeetCode执行结果如下总结贪心算法初看感觉很“难”但具体实现起来却发现很简单。其实「算法」也是一样的初看这个词感觉很难很高大上其实它就是解决某个问题的一种思想、一种固定的“套路”而已也并无神秘可言。人常说路虽远行则将至事虽然难做者必成。“难”和“易”从来都是相对的其实从“难”到“易”就是一个逐渐开悟、逐渐成长的过程。愿你每天成长一点最后留一个我的私人微信GG_Stone相互交流、共同进步。参考 鸣谢https://leetcode-cn.com/problems/water-bottles/https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.htmlhttps://zh.wikipedia.org/zh-hans/贪心算法
往期推荐
嗯查询滑动窗口最大值的这4种方法不错....小白学算法买卖股票的最佳时机23张图万字详解「链表」从小白到大佬关注我每天陪你进步一点点
