【贪心算法】贪心算法七

贪心算法七

• 1.整数替换
• 2.俄罗斯套娃信封问题
• 3.可被三整除的最大和
• 4.距离相等的条形码
• 5.重构字符串

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

1.整数替换

题目链接：397. 整数替换

题目描述：

算法原理：

解法一：模拟（递归 + 记忆化搜索）

假设n = 18，我们要干的事情是把18变成1最小的步数。因为18是一个偶数只能除2变成9，拿到9这个数字，要干的其实也是一件相同的事情，要把9变成1最小的步数。

此时这里就出现了重复的子问题，大问题是18变成1的最小步数，18/2=9后就从了9变成1的最小步数的相同问题。因此我们可以把重复子问题拿到设计出函数头
int dfs(int n) 给一个整数n返回n变成1的最小步数。函数体 其实就是题目给的，如果n是偶数/2，如果n是奇数要么+1，要么-1我们求得是最小步数所以是 min(dfs(n-1)，dfs(n+1))，递归出口 当 n == 1是之间返回0就行了。

在递归过程中发现大量重复，就可以用记忆化搜索，建一个数组，但是这道题的数据范围是1 <= n <= 2^31 - 1，我们要开这么大的空间肯定不行，因此搞一个hash<int,int> 第一个参数对应数字n，第二个参数对应这个数变成1的最小步数。

classSolution{  unordered_map<int,int> hash;public:intintegerReplacement(int n){ returndfs(n);}// 递归intdfs(longlong n)// 细节问题 数据范围1 <= n <= 2^31 - 1 加1会越界{ if(n ==1){ return0;}if(n %2==0)// 如果是偶数 { return1+dfs(n /2);}else{ return1+min(dfs(n -1),dfs(n +1));}}// 记忆化搜索intdfs(longlong n){ if(hash.count(n)){ return hash[n];}if(n ==1){  hash[1]=0;return hash[1];}if(n %2==0){  hash[n]=1+dfs(n /2);return hash[n];}else{  hash[n]=1+min(dfs(n -1),dfs(n +1));return hash[n];}}};

解法二：贪心

补充知识：二进制

1. 偶数：二进制表示中最后一位是 0
2. 奇数：二进制表示中最后一位是 1
3. /2 操作：二进制表示中统一右移一位

我们这里研究的都是整数。
前两个可以自己举例看看。我们看最后一个

接下来想我们的贪心策略：

如果n是偶数没法贪，只能执行/2操作

是奇数就可以贪，要么执行+1，要么执行-1操作。
在模拟解法我们就是试试+1操作和-1操作看谁最小，但是如果在没有试之前就已经知道是+1好还是-1好，直接让奇数沿着较好的选择走，就可以舍去一个选择，那我们的时间复杂度会变得更优。

所以我们的贪心就是判断是+1好还是-1好。

如何判断？分情况讨论：

奇数的二进制最后一位是0，所以我们可以把奇数分为两大类

第一类：前面二进制位是 …，最后两个二进制位是 01

第二类：前面二进制位是 …，最后两个二进制位是 11

其中第一类我们默认 n > 1，也就是说 … 有1，如果没有1的话就是00…01了，直接返回即可。第二类默认 n > 3。

如果是 …01，接下来要么执行+1操作，要么执行-1操作。 +1操作会变成 …10，-1操作会变成 …00，那到底那个操作好呢? +1和-1操作都会变成偶数，偶数只能执行/2操作。假设…01是 …10001，执行+1操作会变成10010在执行/2操作会变成1001，执行-1操作会变成10000在执行/2操作会变成1000。这个时候就可以看出那个操作好了，肯定是-1操作好，因为1000我们可以一直/2操作尽快得到1，1001还需要在+1和-1操作在/2操作。

所以是奇数二进制最后两位是01，就执行-1操作，然后/2操作，会比较快得到1。

如果是 …11，接下来也是要么执行+1操作，要么执行-1操作，分析过程和上面一样。

但是n > 3这里有一个意外，当 n = 3的时候，我们需要特殊讨论，n = 3，二进制位前面都是0，后面虽然也是11。但是这里我们执行-1操作得到…10，然后在执行/2操作，直接就变成1了。这个和选择是不一样的。如果执行+1操作就会多一步/2操作。

我们这个贪心不用证明，分类讨论过程本身就是对这个贪心的证明。

那如何写代码呢？

如何判断二进制最后两位是01还是11呢？
拿n%4就可以了，因为n是奇数%4只能得到1和3，如果是1就是01情况，如果是3就是11情况。

classSolution{  unordered_map<int,int> hash;public:intintegerReplacement(int n){ int ret =0;while(n >1){ if(n %2==0){  n /=2;++ret;}else{ if(n ==3){  ret +=2; n =1;}elseif(n %4==1){  n