【贪心算法】贪心算法六

贪心算法六

• 1.坏了的计算器
• 2.合并区间
• 3.无重叠区间
• 4.用最少数量的箭引爆气球

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.坏了的计算器

题目链接： 991. 坏了的计算器

题目分析：

算法原理：

解法一：正向推导

以3转化成10为例，我们正向推导有两个操作x2，-1。

此时拿到3要么x2，要么-1，此时我们有一个小贪心的想法，为了更快到达，所以选择x2，得到6，这里也有两种选择要么x2，要么-1，如果延续刚才的贪心我们会x2，得到12，此时12比10大了，我们只能执行-1操作，得到11，再执行依次-1操作得到10，这里我们共进行了4次操作

但是我们发现如果再6的时候，不去x2，而去-1，得到5，然后在去x2，就得到10，总共才3次操作，反而比刚才的小贪心更优。

所以说在面临一个数的时候，是x2 还是 -1操作，判断标准其实是依赖后面的数来判断前面是x2还是-1好。所以说如果正向推导有点难，我们可以尝试另一个思路。

解法二：正难则反

我们这道题明显可能反着来做，x2和-1 操作 可以变成/2和+1 操作。所以说我们能正向从3推导到10，那肯定能逆向推导回去。

假设我们要从end转化成begin（10 -> 3）

正着难推导，难道逆着就好推导吗？确实是的，原因就在于这里/2操作，别忘了我们这道题是没有小数的，没有小数，那谁才能执行/2操作？那肯定是偶数，偶数/2能除尽，奇数/2除不尽。

所以面对奇数的时候只能执行+1操作，面对偶数我们在分情况讨论是/2还是+1。

1. end <= begin

奇数依旧+1，当end <= begin的时候，偶数此时就没有必要执行/2操作。因为此时end都比begin小了难道你要/2之后在加1吗？那不如直接加1好了。所以end <= begin，奇数+1，偶数+1，而且这个+1操作也不用一次一次算，我们仅需 begin - end就得到要执行几次+1了。

2. end > begin

奇数依旧+1，偶数要么/2，要么+1，此时这里我们有一个小贪心，因为end大于begin，我们想最少操作次数到达begin所以我们看似选择/2是更优的。

那这个贪心的想法对不对呢?

我们证明一下先除更优。

假设x是个偶数，并且大于begin。
如果不执行/2操作，而执行+1操作，那会得到一个奇数，但是奇数只能加1，然后又变成偶数了，又执行+1操作，又变成奇数，奇数只能+1，又变成偶数了。假设x一共加了k个1。这个k也是个偶数，如果k是奇数接下来还要+1总归要把它先加成一个偶数才行。

x + k 是大于 begin，必然会执行一次 / 2操作，你想把大的数变成小的数不执行除法操作怎么才能变小呢？所以无论加上多少1最终都会执行一次/2操作，变成(x+k)/2，次数这种操作执行的次数就是 k + 1次

但是如果拿x这个数变成(x+k)/2，先执行/2操作变成 x/2，然后仅需在x/2的基础上加上k/2，就得到(x+k)/2，这种执行操作次数是 1 + k/2次，是比上面执行次数小的。

所以说当 end > begin ，面对偶数我们也不需要分类讨论，仅需执行/2操作。奇数+1，偶数/2，一直到end <= begin的时候，执行begin - end就可以得到整个操作次数。

class Solution { public: int brokenCalc(int startValue, int target) {  // 正难则反 + 贪心 int ret = 0; while(target > startValue) {  if(target % 2) target++; else target /= 2; ++ret; } return ret + startValue - target; }};

2.合并区间

题目链接： 56. 合并区间

题目分析：

给一个二维矩阵，每一行表示一个区间，里面有两个元素第一个表示左端点，第二个表示右端点，请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

有重叠的部分合并相当于就是求并集。注意示例2这个特殊的情况[1,4]和[4,5]也需要合并，也就是仅有一个点重叠也是可以合并。

算法原理：

关于贪心里面的区间问题的解法，我们都是固定的解法。

1. 排序
2. 根据排序后的结果，总结出一些规律，进而得出解决这个问题的策略

关于第2点也可以先提出一个解决问题的策略，进而总结出一些规律。

关于第1点排序，是分为两大类的，其中第一类是按照左