保险理财网站建设,网页游戏网站2345,旭泽建站,内江广告制作公司贪心算法一 1.柠檬水找零2.将数组和减半的最少操作次数3.最大数4.摆动序列 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#xff0c;我们一起努力吧!#x1f603;#x1f603; 1.柠檬水找零
题目… 贪心算法一 1.柠檬水找零2.将数组和减半的最少操作次数3.最大数4.摆动序列 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1.柠檬水找零
题目链接 860. 柠檬水找零
题目分析 这里有两点需要注意
顾客排队购买你的产品一开始你手头没有任何零钱你要拿着顾客的钱去找钱
顾客排队购买你的产品也就是说如果第一个顾客给你10或者20美元你就找不了返回false。
算法原理
这里我们只关注正确的贪心策略不用管它怎么来的。最后我们来证明一下。
贪心可不是上来就贪而是在分析问题的过程中发现可以贪我们才贪。
这道题就是一个找零问题顾客会给5美元10美元20美元。我们分情况给他找钱就可以了。 当顾客给5块钱我们直接收下就行了 当顾客给10块钱我们要找5块钱顺手把10块钱收下但是找5元前提是我们有5块钱可以找如果没有返回false 当顾客给20块钱关于20块钱找零其实我们有两种策略 第一种找一张10块钱在找一张5块钱 第二种找三张5块钱
此时就有分歧了我们要想哪一种最好这就体现了贪心。贪心就体现在这一步我们应该选择更优的策略来完成这个找零工作。
到底那个优秀其实是根据5块钱来的5块钱不仅完成20块钱找零工作还能完成10块钱找零工作。因此我们尽量保留5块钱。
所以看起来当前最优策略就是第一种策略。如果第一种策略不成立我们再选第二种策略如果第二种策略都不成立就返回false class Solution {
public:bool lemonadeChange(vectorint bills) {int five 0, ten 0;for(auto e : bills){if(e 5) five;else if(e 10){if(five 0) return false;five--; ten;}else{if(ten five) //贪心{ten--; five--;}else if(five 3){five - 3;}else return false;}}return true;}
};证明贪心策略是正确的
证明策略交换论证法
假设 贪心策略解决这道题的方法顺序是a、b、c、d、e、f 最优解解决这道题的方法顺序是e、b、c、d、a、f
此时如果在不破坏最优解的 “最优性质的” 前提下能够将最优解调整成贪心解。那我们就说贪心解就是最优解。 这就是我们的交换论证法交换论证法的核心就是找到不破坏最优性质的前提下把假设出来的最优解逐步的调整出贪心解。
如果顾客给我们5美元或者10美元贪心解和最优解是没有区别的。5块就收下10块就找5块。 唯一的区间就是20美元
贪心解策略是有限选择105但是最优解有可能和贪心解不一样选择的是555。如果一样肯定不考虑考虑的肯定是不一样的情况。
假设从左往右扫描第一次碰到20美元下不同的时候我们看看能不能把最优解调整成贪心解。 其实就盯着10美元就可以了。因为贪心解这里用到10最优解这里没有用到10。那么此时10美元就有两种情况了第一种情况10美元在后面找零过程没有用到也就是贪心解用来10但是最优解在后面的找零操作并没有用到1010块钱装到兜里了。那么此时我们就可以把最优解的两个5替换成兜里的10块钱。这个替换并不影响最优性质因为这个10在后面找零操作就没有用过。
最优解能解决问题替换完之后的10也能解决问题 第二种情况10美元在后面的换零操作有一次用过了。此时我们依旧可以把前两个5用后面的10交换。前面用10后面用两个5交换后依旧不影响最优性质。然后又和贪心解一模一样。 你会发现最优解用或者不用10都可以把它替换成和贪心解一样的形式。也就说从前往后扫描只要不相等就调整那最终一定能把最优解逐步调整成贪心解并且最优解是可以解决问题那贪心解也一定能解决问题。所以贪心解就和最优解是等价的。
2.将数组和减半的最少操作次数
题目链接 2208. 将数组和减半的最少操作次数
题目描述 算法原理
这道题把题意搞清楚之后想让我们用最少的操作次数把数组和至少减少到之前的一半那我们肯定会想到每次挑选的时候挑选当前数组里最大的数给它减半因为挑数组最大的数减半才有可能最快的把整个数组的和减少到之前的一半。
解法贪心
具体策略每次挑选当前数组中最大的那个数然后减半直到数组和减少到至少一半为止。
实现我们这个策略的核心就是循环这一步每次挑选当前数组中最大的那个数。如果每次都去遍历数组挑最大的那个数时间复杂度是非常恐怖的这里我们可以使用优先级队列这个数据结构建立一个大根堆。
解法贪心 大根堆
class Solution {
public:int halveArray(vectorint nums) {priority_queuedouble heap;double sum 0.0;for(auto e : nums) {heap.push(e);sum e;}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;}
};证明
证明策略交换论证法
这里在说明一点不管用什么方法证明一定得要结合题意和贪心策略来证明。
我们这里的题意是每次挑选一个数直到数组和减半 假设贪心解每次挑选数这里用横线上面的点表示每次挑选的数。同样最优解也是这样表示。贪心解挑选的数个数大于或者等于最优解的数个数。 我们只要能想到一个转化规则在不破坏最优解的 “最优性质的” 前提下能够将最优解调整成贪心解。就可以了。
那我们从左到右扫描贪心解和最优解。先找到第一次两者不一样的地方。假设贪心解挑的是x最优解挑的是y此时我们只要能把y变成x就可以了。 如何变紧扣题意和贪心策略在我们贪心解里面挑的数组中最大的数最优解如果没有挑最大那个数那么这里有一个不等式x y 对于x在最优解中它有两种情况第一种情况x没有用过。此时可以大胆将y替换成x因为x y你用一个小的数减半就能让整个数组和减半那选一个更大的数减半那更能让整个数组和减半。即使后面有y/2y/4等都可以用x替换y。 第二种情况x在后续最优解使用了那我们依旧可以将y与x交换。因为在最优解先用x减半和后用y减半并不影响最优解的最少操作次数。即使在y和x中间可能使用了y/2y/4但是把y交换到后面去了那就没有y/2y/4这些数那逻辑不就错了吗。其实可以把y和x交换完之后把y/2y/4y重新排一下序还是 yy/2y/4的使用。 此时我们在处理最后一个情况贪心解的次数可能是比最优解次数多的但是这种情况是绝对不可能的因为我们从前往后扫描的时候只要遇到不同都可以用这两种情况进行调整。所以说当最优解解决完情况后贪心解也一定减半了。所以最优解的操作次数和贪心解的操作次数是一样的。 到这里就证明完毕了。原因就是从前往后扫描两个解的时候只要有一个地方不一样就可以通过这两个策略进行调整所以最优解就可以在不失去最优性的前提下转化为贪心解。所以当最优解是最少操作次数解决这个问题的时候贪心解也是最少操作次数解决这个问题的时候。
3.最大数
题目链接 179. 最大数
题目分析 示例1[102] 它所形成的最大整数就是这个数组里面按照从左往右的顺序把数拼起来就可以了。比如这个数组不去休息顺序从左往右拼起来就是102如果调整一下顺序拼接就是210201显然大于102所以示例1所能拼成的最大整数就是210.
但是有可能输出结果可能非常大所以你需要返回一个字符串而不是整数。
算法原理
如果把这道题的题意搞清楚之后会发现这道题特别像是一道排序题。无非就是给一个数组按照它给的规则把数组排下序使其形成一个最大的数。
所以先回忆之前正常的排序看能否给我们这道题带来一些启发
正常的排序升序 [4108]
不管是之前学习过的冒泡快排归并等排序它们都是干一件事情就是确定这些元素的先后顺序。只要能搞清楚这些元素谁在前面、谁在中间、谁在后面我们就能完成这些元素的排序。
所以正常的排序本质确定元素的先后顺序谁在前谁在后。
其中确定元素的先后顺序是根据一定的排序规则来确定 本题的排序其实也是在确定元素的先后顺序所以我们仅需找一个排序规则就可以了。
排序规则其实例一[102]已经给我们了先把这两个数拼接成102和210然后我们会发现把2放在前面把10放在后面是优于102因此我们得到一个结果把2放前面10放后面。 我们可以把这两个数抽象出来a表示第一个数b表示第二个数。 此时我们会得到两种情况要么a在前b在后要么b在前a在后
如果发现a在前b在后这种拼接是优于把b在前a在后的拼接我们可以得到a可以放放在前面b放在后面。 如果发现b在前a在后这种拼接和把a在前b在后的拼接是一样的那就无所谓。 如果发现b在前a在后这种拼接是优于把a在前b在后的拼接我们可以得到b可以放放在前面a放在后面。 这就是我们这道题里面的排序规则。基于这样的排序规则会发现它们俩是非常一样的这里我们可以使用sort进行排序然后把这个比较规则传给sort。
我们这个专题不是贪心吗但是这里贪心体现在哪里呢
其实贪心就体现在了比较规则确定谁前谁后的策略就是贪心。
这一个排序规则为什么能排序呢?
之前排序规则之所以能排序最重要的就是传递性。a bb c ---- a c可以推出来 a 在 b 前面b 在 c 前面又因为 a c所以 a 在 c 前面。所以符合 a b c。 如果此时a bb c 推不出来 a c就不能排序。因为a b 可以推出 a 在 b 前面b c 可以推出 b 在 c 前面如果推不出来 a c 的意思是 c 可能大于 a如果 c a 那 a 就在 c 的后面此时根本就不可能。数组就不能排序。 上面传递性太明显了所以极有可能会忽略但是我们这道题不能忽略这一点。如果知道 ab babc cb 推出 a 在 b 的前面b 在 c 的前面如果在能知道ac ca a 在 c 的前面才能摆出 a b c
但是能不能推出这一点需要后面去证明。 这里写代码还有两个细节问题
第一个细节把数转化成字符串然后拼接成字符串比较字典序。
如果不这样搞还需要算两个数有多少位然后一个数乘于位数在加上另一个数才能得到一个拼接的数。
第二个细节这道题有可能传递 [00]这样的数组如果按照之前的策略那就会返回一个 “00” 字符串。但是我们要的是一个数我们要把字符串搞成 “0” 才行。我们可以判断一下最后的结果ret如果第一个字符是 “0” 说明后面应该全都是 “0”那我们最终返回 “0” 这个字符串就可以了。为什么后面应该全都是 “0”如果后面的是不是0的话0放在最后一个位置绝对不可能是最大数。
class Solution {
public:string largestNumber(vectorint nums) {// 优化: 把所有的数转化成字符串vectorstring strs;for(int x : nums) strs.push_back(to_string(x));// 排序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;}
};证明
这里我们只要证明我们这个策略是可以排序的就可以了。
如何证明一个东西可以排序呢这里要用到数学的知识。
证明方法数学知识全序关系
全序关系的用处假设有一个集合集合里有很多元素全序关系的作用就是从这个集合中任意挑选两个元素如果这两个元素在定义的比较规则下如果满足全序关系的话我们就说这个集合是可以排序的。
全序关系分为三个性质也就是说只要满足三个性质就有全序关系。
完全性
从集合中任意挑选两个元素 a、b它必定会存在两个关系的一个要么 a b要么 a b。如果挑选的两个元素压根没有大小关系根本不知道谁在前谁在后。所以完全性就是能够排序的最前提条件任意挑选两个元素能够比大小。 反对称性
还是任意挑选两个元素a、b如果知道 a b 且 a b那必须能够推出 a b如果得不到这个结果那么整个数组排序把a放在前面b放在后面是一种排序结果把b放在前面a放在后面还是一种排序结果。那么整个集合就不能排序因为整个集合要想排序那最终结果是唯一的才行。 传递性
任意挑三个元素a、b、c如果 a bb c那一定要推出a c 。这一点上面已经说过了如果不满足排序不出来最终结果。 我们要证明的是排序规则任意挑两个数a、b然后看 ab 和 ba 这个情况的大小然后确定a和b的前后顺序。
证明完全性
挑出a、b然后看a拼接bb拼接a是能够比大小的就可以了。
第一种证明
ab拼接后是一个数ba拼接后也是一个数。数和数之间是能够比大小的。要么ab ba要么 ba ab。 第二种证明
设a的位数为 x 位 b的位数为 y 位。 ab拼接的结果是可以表示出来的10^ya b ba10^xb a
既然这两个数能明确表示出来那一定能比大小。
证明反对称性
如果 ab ba 且 ab ba那我们要能得到 ab ba 这个结论。
将ab和ba用刚才的进行处理因为这里是一个一个的数设ab为mba为n此时我们能得到一个夹逼定理。m n m我们可以得到 m n。所以我们可以根据1、2得到3。 证明传递性
还是任取三个数a、b、c如果ab ba 且 bc cb 我们必须要推出来ac ca ac ca的意思是a在前c在后也就是说a在前b在后我们要能推出来a在前c在后才行。
我们证明方法和上面一样把不等式写成一个确切的数 这里特殊情况要考虑一下如果a、b、c其中任意一个可能等于0 假如a是0的话那x位数就是为0。小学我们就知道0不是一个个位数但是这道题里我们把0这个数当成一个个位数。如a是12b为0ab为120 如果能由1和2这两个式子能推出来第3个式子那么这个式子就成立 我们观察一下三个式子发现第三个式子是没有b的因此我们仅需通过1和2两个式子把b给消掉就可以了。我们可以把b的系数移过去就可以把b消掉但是移系数要注意系数不能为0但是刚才处理特殊情况的时候说过x绝对不可能等于0的那么10^x绝对不可能等于1所以我们可以大胆移第一个式子b的系数。同样第二个式子也是。 10^y - 1不可能为0两步同时消掉然后在移项就可以得到第三个式子
到此证毕我们这个排序规则既有完全性又有反对称性又有对称性因此具有全序关系。有全序关系就说明我们这里定义的排序规则是可以排序的。
4.摆动序列
题目链接376. 摆动序列
题目分析 摆动序列就是一上一下。注意仅有一个元素或者含两个不等元素的序列也视作摆动序列返回摆动序列 的 最长子序列的长度。
算法原理
这里我们就不写具体的数了而把数当成折线图的形式。目前先不考虑水平这样的形式先考虑相邻两个元素不同的形式最后在把水平的处理一下 如果图是这样的如何找它的最长摆动序列呢 我们肯定有这样的想法把左边和右边的点挑出来然后在把所有极大值点和极小值点也挑出来所形成的序列就是一个最长摆动序列。
这个策略确实是可以的我们的贪心策略最终也和这个策略长的一样。 接下来我们就来贪一下我们要找到的是最长摆动序列相当于就是在这个图中尽可能的挑一些点出来所形成的序列是摆动序列。
既然是尽可能挑多的点那第一个点就给选上接下来挑选第二个点的时候继续贪当前右边这么多点我选择那个点看起来是最优的此时就有分情况讨论的过程 第一种情况在上升的线上选一个点但是在上升的这条线上选都没有第三种情况好因为选了上升线上一个点接下来要去选下降的如果挑选这些较小上升的点那在挑选下降的点可供选择的空间就小了。比如画×的点就选不到了。 第二种情况选择右边的某个点如果选了这个点那摆动系列绝对不可能是最长的因为中间还有可以选择的一上一下的点。 同样选了这个点也会错失一个拐点那摆动序列也不会是最长的。 可能还会选这条下降线的点有可能是会最长的但是并不保险有可能这条线没有点所以不如选第三种情况这个点。 固定两个点之后考虑第三个点依旧和选择第二个点一样分情况讨论如果是下降选择不能在下降的点如果是上升选择不能在上升的点。直到所有点都选完就是最长摆动子序列。 你会发现我们贪心挑选出来的点就是把极大值和极小值还有两个端点的值跳出来。
贪心统计出所有的波峰以及波谷的个数 然后在把左右两个点加上就可以了。 那如何统计出最终的结果呢
首先如何确定一个点是波峰还是波谷
波峰当前这个点减左边的点如果是正右边的点减去当前的点如果是负就是波峰。
波谷当前这个点减去左边的点如果是负右边的点减去当前的点如果是正就是波谷。
也就是说当前这个点左右是相反的就可以确定要么是波峰要么是波谷。 还有一个问题如果相邻两个元素是相同的就麻烦了它会分成两大类 第一类相同的时候左右增减趋势是相同的 第二类相同的时候左右增减趋势是相反的 第一类是没有波峰波谷的第二类是有的。虽然是有相同的元素但是第一类总体要么上升、要么下降不需要统计波峰波谷。第二类要么下降后上升、要么上升后下降是需要统计波峰波谷的。
但是相同元素该统计那一个呢并且虽然属于不同类但是都是左边是是负数右边是0一个不需要统计一个需要统计还是很恶心的。 可以用一个变量left记录当前某个点左边的增减趋势然后上述情况的时候把这些相同的情况都可以忽略掉。仅需考虑最左边点的增减趋势和最右边点的增减趋势。 接下来模拟一下
left就是标记某个点左边的正负它有三种情况
left 0表示第一个点左边既可以上升也可以是下降的 left 0上升 left 0下降
然后确定某个点的时候仅需算一个它的右边right就行了right nums[i1] - nums[i] 当left*right 0 就是波峰或者波谷当right 0 说明遇到相同的元素然后是可以抛弃的 class Solution {
public:int wiggleMaxLength(vectorint nums) {int n nums.size();if(n 2) return n;int left 0, right 0, ret 0;for(int i 0; i n - 1 ; i){right nums[i 1] - nums[i];if(right 0) continue;if(left * right 0) ret;left right;}return ret 1;}
};证明
这道题证明有三种方法
反证法分类讨论交换论证法
这里我们证明方法是反证法
假设我们的操作是错的此时它的反命题就是一个正确的只要我们证明正确的命题是有矛盾的或者有错误的那原来的命题就是正确的。
我们的贪心解是选择左右端点和极值假设最后选择的点为n这里 n 6 假设贪心解是错的那必须会存在一个最优解在相同的情况下可以选择更多的点N 6。我们只要推出最优解是矛盾的或者错误的那我们贪心解就对了。 盯着每一个拐点先看最左边的拐点我们这是一个连续的区间左边元素比它小右边元素也比它小在它这个左右区间里一定会出现一个极大值要么该点是极大值点要么就是区间内的其他点。 在看下一个拐点左右两侧都是比它大的又因为是连续的所以在这个区间里面必定会存在一个极小值。
同理后面也可以得到极大值极小值。 因此可以推出在最优解里极值点个数是N-2舍去左右两端点但是这个N-2是不存在的。因为在贪心解里面我们是可以推出来极值点个数是n-24因为最优解N6所以它的极值点个数是N-2 4的但是极值点个数是不可能大于4的所以最优解压根就是不存在的因为贪心解得到极值点个数是4你这个最优解算出考虑极值点个数大于4这是不符合实际情况的。所以这个最优解是不存在的因此贪心解是正确的。
