【贪心算法】整数替换，俄罗斯套娃信封问题，可被三整除的最大和，距离相等的条形码，重构字符串

1. 整数替换（LC 397）

整数替换

题目描述

解题思路

模拟：递归+记忆化搜索

利用备忘录记录每个数到1的最小操作次数

• 如果是偶数，返回n/2的值+1
• 如果是奇数，返回n+1或n-1的最小值+！

贪心：找规律

知识补充：

1. 偶数的二进制表示最后一位是0
2. 奇数的二进制表示最后一位是1
3. 计算机中的/2操作在二进制中就是整体左移

分类讨论：

• n为偶数：只能/2，也就是左移
• n为奇数：可以对n%4得到后两位的值
  • 如果后两位是01，-1操作更快到达1
  • 如果后两位是11，+1操作更快到达1
  • 如果n==3，-1再/2更快到达1

代码解析

• 递归

classSolution{HashMap<Long,Integer>hash=newHashMap<>();publicintintegerReplacement(intn){hash.put((long)1,0);returndfs(n);}intdfs(longn){if(n==1)return0;if(n%2==0){if(!hash.containsKey(n))hash.put(n,dfs(n/2)+1);}else{if(!hash.containsKey(n))hash.put(n,Math.min(dfs(n-1),dfs(n+1))+1);}returnhash.get(n);}}

• 贪心

publicintintegerReplacement(longn){intret=0;while(n!=1){if(n==3){ret+=2;break;}if(n%2==0)n/=2;else{if(n%4==1)n-=1;elseif(n%4==3)n+=1;}ret++;}returnret;}

2. 俄罗斯套娃信封问题（LC 354）

俄罗斯套娃信封问题

题目描述

解题思路

参考最长递增子序列 把乱序数组按照“套娃信封”的顺序排列，统计最长的套娃序列

动态规划

• 状态表示：以当前的信封为结尾的最长套娃序列
• 状态转移方程：从0遍历到当前位置，如果过可以接上，dp[i] = dp[j]+1；取最大值
• 初始化：可以直接初始化为1
• 返回值：整个dp表中的最大值

贪心+二分

1. 先对数组的左端点排序，在左端点严格递增的情况下，只需要在右端点总找到最长递增子序列即可。
2. 如果左端点相同，右端点就是乱序的，会干扰最长递增子序列的选择，因此要重写排序方法：左端点不同时，从小到大排序；左端点相同时，从大到小排序。
   • 举个例子：[2,6] [2,5] [2,4] [2,3] 如果按照上面的逻辑，对于左端点相同的数组，不可能找到递增子序列。

代码解析

• 动态规划（超时）

publicintmaxEnvelopes(int[][]en){intn=en.length;Arrays.sort(en,(a,b)->a[0]-b[0]);int[]dp=newint[n];Arrays.fill(dp,1);intret=1;for(inti=1;i<n;i++){for(intj=0;j<i;j++){if(en[j][0]<en[i][0]&&en[j][1]<en[i][1])dp[i]=Math.max(dp[i],dp[j]+1);}ret=Math.max(ret,dp[i]);}returnret;}

• 贪心

publicintmaxEnvelopes(int[][]en){intn=en.length;if(n==1)return1;Arrays.sort(en,(a,b)->{if(a[0]==b[0])returnb[1]-a[1];returna[0]-b[0];});ArrayList<Integer>ret=newArrayList<>();ret.add(en[0][1]);for(inti=1;i<n;i++){if(en[i][1]>ret.getLast())ret.add(en[i][1]);else{intleft=0;intright=ret.size()-1;while(left<right){intmid=left+(right-left)/2;if(ret.get(mid)<en[i][1])left=mid+1;elseright=mid;}ret.set(left,en[i][1]);}}returnret.size();}

3. 可被三整除的最大和（LC 1262）

可被三整除的最大和

题目描述

解题思路

先计算所有数的总和，根据累加和，减去一部分数，直到可以被3整除。

• sum%3==1 :有两种情况
  • 找到最小的x1，x1%3==1，删除x1
  • 找到最小的y1，y2。y1%3==2,y2%3==2，删除y1,y2
• sum%3==2 :有两种情况
  • 找到最小的y1，y1%3==1，删除y1
  • 找到最小的y1，y2。x1%3==2,x2%3==2，删除x1,x2

根据上面的分析过程，统计和的同时，要找到x1,x2,y1,y2，分别是最小值与次小值

代码解析

publicintmaxSumDivThree(int[]nums){intret=0;intn=nums.length;intx1=0x3f3f3f3f;intx2=0x3f3f3f3f;inty1=0x3f3f3f3f;inty2=0x3f3f3f3f;for(inti=0;i<n;i++){ret+=nums[i];if(nums[i]%3==1){if(nums[i]<x1){x2=x1;x1=nums[i];}elseif(nums[i]<x2)x2=nums[i];}if(nums[i]%3==2){if(nums[i]<y1){y2=y1;y1=nums[i];}elseif(nums[i]<y2)y2=nums[i];}}if(ret%3==0)returnret;elseif(ret%3==1)returnret-Math.min(x1,y1+y2);elsereturnret-Math.min(y1,x1+x2);}

4. 距离相等的条形码（LC 1054）

距离相等的条形码

题目描述

解题思路

1. 利用哈希表记录每个数字出现的次数
2. 先处理出现次数最多的数，每次摆放都与上一个空隔开一个位置.
3. 最后排其他数字

代码解析

publicint[]rearrangeBarcodes(int[]barcodes){intn=barcodes.length;int[]ret=newint[n];intmaxcnt=0;intmaxnum=0;HashMap<Integer,Integer>hash=newHashMap<>();for(intx:barcodes){hash.put(x,hash.getOrDefault(x,0)+1);if(hash.get(x)>maxcnt){maxnum=x;maxcnt=hash.get(x);}}inti=0;while(hash.get(maxnum)>0){ret[i]=maxnum;hash.put(maxnum,hash.get(maxnum)-1);i+=2;}for(Map.Entry<Integer,Integer>entry:hash.entrySet()){intcnt=entry.getValue();while(cnt-->0){if(i>=n)i=1;ret[i]=entry.getKey();i+=2;}}returnret;}

5. 重构字符串（LC 767）

重构字符串

题目描述

解题思路

遇上一题的思路完全相同，重排之前，要判断maxchar>(n+1)/2，如果成立，说明一定有相同的字符相邻

代码解析

publicStringreorganizeString(Strings){int[]hash=newint[26];intn=s.length();char[]ss=s.toCharArray();charmaxchar='0';intmaxcnt=0;for(inti=0;i<n;i++){hash[ss[i]-'a']++;if(hash[ss[i]-'a']>maxcnt){maxchar=ss[i];maxcnt=hash[ss[i]-'a'];}}if(maxcnt>(n+1)/2)return"";char[]ret=newchar[n];inti=0;while(hash[maxchar-'a']>0){ret[i]=maxchar;hash[maxchar-'a']--;i+=2;}for(intj=0;j<26;j++){while(hash[j]>0){if(i>=n)i=1;ret[i]=(char)(j+'a');hash[j]--;i+=2;}}returnnewString(ret);}