算法沉淀——贪婪算法七（leetcode真题剖析）

  
01.整数替换

标题链接：https://leetcode.cn/problems/integer-replacement/
给定一个正整数 n ，你可以做如下操作：

• 假如 n 是偶数，则用 n / 2替换 n 。
  
• 假如 n 是奇数，则可以用 n + 1或n - 1替换 n 。
  

返回 n 变为 1 所需的 最小替换次数 。
示例 1：

1. 输入：n = 8
2. 输出：3
3. 解释：8 -> 4 -> 2 -> 1

复制代码

示例 2：

1. 输入：n = 7
2. 输出：4
3. 解释：7 -> 8 -> 4 -> 2 -> 1
4. 或 7 -> 6 -> 3 -> 2 -> 1

复制代码

示例 3：

1. 输入：n = 4
2. 输出：2

复制代码

提示：

• 1 <= n <= 2^31 - 1
  

思路
这里我们要求得最小次数，要进行具体的分析讨论，起首偶数只有一种环境，以是不必讨论，假如奇数则分为一下三种环境：

1. 1、n>1且n%3==1的时候，二进制位后是……01，最优的方式应该选择-1，这样就可以把末尾的1去掉
2. 2、n>3且n%3==3的时候，二进制位后是……11，最优的方式应是选择+1，这样后续均为连续0，能够更快趋近1
3. 3、n==3时，变成1最优操作数为2

复制代码

代码

1. class Solution {
2. public:
3.     int integerReplacement(int n) {
4.         int ret=0;
5.         while(n>1){
6.             if(n%2==0){
7.                 ret++;
8.                 n/=2;
9.             }
10.             else
11.             {
12.                 if(n==3){
13.                     ret+=2;
14.                     n=1;
15.                 }
16.                 else if(n%4==1){
17.                     ret+=2;
18.                     n/=2;
19.                 }else{
20.                     ret+=2;
21.                     n=n/2+1;
22.                 }
23.             }
24.         }
25.         return ret;
26.     }
27. };

复制代码

02.俄罗斯套娃信封问题

标题链接：https://leetcode.cn/problems/russian-doll-envelopes/
给你一个二维整数数组 envelopes ，其中 envelopes = [wi, hi] ，表现第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时间，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请盘算 最多能有多少个 信封能构成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封内里）。
注意：不允许旋转信封。
示例 1：

1. 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
2. 输出：3
3. 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

复制代码

示例 2：

1. 输入：envelopes = [[1,1],[1,1],[1,1]]
2. 输出：1

复制代码

提示：

• 1 <= envelopes.length <= 105
  
• envelopes.length == 2
  
• 1 <= wi, hi <= 105
  

思路
重写排序+贪婪+二分的思想：
我们先按照左端点不同时升序排序，左端点雷同时按右端点降序排序，如许我们只需要考虑右端点，再使用贪婪+二分就可以很好的解决这个问题
代码

1. class Solution {
2. public:
3.     int maxEnvelopes(vector<vector<int>>& envelopes) {
4.         sort(envelopes.begin(),envelopes.end(),[&](const vector<int>& v1,const vector<int>& v2){
5.             return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]>v2[1];
6.         });
8.         vector<int> ret;
9.         ret.push_back(envelopes[0][1]);
11.         for(int i=1;i<envelopes.size();i++){
12.             int b=envelopes[i][1];
13.             if(b>ret.back()) ret.push_back(b);
14.             else{
15.                 int left=0,right=ret.size()-1;
16.                 while(left<right){
17.                     int mid=(left+right)/2;
18.                     if(ret[mid]>=b) right=mid;
19.                     else left=mid+1;
20.                 }
21.                 ret[left]=b;
22.             }
23.         }
24.         return ret.size();
25.     }
26. };

复制代码

03.可被三整除的最大和

标题链接：https://leetcode.cn/problems/greatest-sum-divisible-by-three/
给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
示例 1：

1. 输入：nums = [3,6,5,1,8]
2. 输出：18
3. 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

复制代码

示例 2：

1. 输入：nums = [4]
2. 输出：0
3. 解释：4 不能被 3 整除，所以无法选出数字，返回 0。

复制代码

示例 3：

1. 输入：nums = [1,2,3,4,4]
2. 输出：12
3. 解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

复制代码

提示：

• 1 <= nums.length <= 4 * 10^4
  
• 1 <= nums <= 10^4
  

思路
起首我们先将所有的值累加起来，那么就会有下面三种环境

1. 1、刚好是3的倍数，那么直接返回即可。
2. 2、是3的倍数多1，那么我们找出除3的数中余1的最小的一个数，用总和减去与除3的数中余2的最小的两个数，找出最大值即为所需
3. 3、是3的倍数多2，那么我们找出除3的数中余2的最小的一个数，用总和减去与除3的数中余1的最小的两个数，找出最大值即为所需

复制代码

代码

1. class Solution {
2. public:
3.     int maxSumDivThree(vector<int>& nums) {
4.         const int INF=0x3f3f3f3f;
5.         int sum=0,x1=INF,x2=INF,y1=INF,y2=INF;
6.         for(int& x:nums){
7.             sum+=x;
8.             if(x%3==1){
9.                 if(x<x1) x2=x1,x1=x;
10.                 else if(x<x2) x2=x;
11.             }else if(x%3==2){
12.                 if(x<y1) y2=y1,y1=x;
13.                 else if(x<y2) y2=x;
14.             }
15.         }
17.         if(sum%3==0) return sum;
18.         else if(sum%3==1) return max(sum - x1,sum-y1-y2);
19.         else return max(sum-y1,sum-x1-x2);
20.     }
21. };

复制代码

04.距离相等的条形码

标题链接：https://leetcode.cn/problems/distant-barcodes/
在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes。
请你重新排列这些条形码，使其中恣意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
示例 1：

1. 输入：barcodes = [1,1,1,2,2,2]
2. 输出：[2,1,2,1,2,1]

复制代码

示例 2：

1. 输入：barcodes = [1,1,1,1,2,2,3,3]
2. 输出：[1,3,1,3,2,1,2,1]

复制代码

提示：

• 1 <= barcodes.length <= 10000
  
• 1 <= barcodes <= 10000
  

思路
起首标题要求保证存在答案，我们只需将出现次数最多的谁人数两两相隔放置，剩下的数接着两两相隔放置即可，关于剩下的数为什么也可以直接两两放置，这是因为我们可以通过鸽巢定理推出只有出现最多的数才会影响到相隔，而我们解决了出现次数最大的数，以是剩下的数只要继续按照两两相隔的次序继续放置即可。
代码

1. class Solution {
2. public:
3.     vector<int> rearrangeBarcodes(vector<int>& barcodes) {
4.         unordered_map<int,int> hash;
5.         int maxval=0,maxCount=0;
6.         for(int& x:barcodes){
7.             if(maxCount<++hash[x]){
8.                 maxCount=hash[x];
9.                 maxval=x;
10.             }
11.         }
13.         int n=barcodes.size(),index=0;
14.         vector<int> ret(n);
15.         for(int i=0;i<maxCount;i++){
16.             ret[index]=maxval;
17.             index+=2;
18.         }
20.         hash.erase(maxval);
21.         for(auto& [x,y]:hash){
22.             for(int i=0;i<y;i++){
23.                 if(index>=n) index=1;
24.                 ret[index]=x;
25.                 index+=2;
26.             }
27.         }
28.         return ret;
29.     }
30. };

复制代码

05.重构字符串

标题链接：https://leetcode.cn/problems/reorganize-string/
给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。
返回 s 的恣意可能的重新排列。若不可行，返回空字符串 "" 。
示例 1:

1. 输入: s = "aab"
2. 输出: "aba"

复制代码

示例 2:

1. 输入: s = "aaab"
2. 输出: ""

复制代码

提示:

• 1 <= s.length <= 500
  
• s 只包含小写字母
  

思路
这一题和上一题思路基本一致，但需要注意的是，这一题并没有说肯定有解，以是这里我们需要给出不符合的判定，其余代码雷同上一题。
代码

1. class Solution {
2. public:
3.     string reorganizeString(string s) {
4.         int hash[26]={0};
5.         char maxChar=' ';
6.         int maxCount=0;
7.         for(char& ch:s){
8.             if(maxCount<++hash[ch-'a']){
9.                 maxChar=ch;
10.                 maxCount=hash[ch-'a'];
11.             }
12.         }
14.         int n=s.size();
15.         if(maxCount>(n+1)/2) return "";
17.         string ret(n,' ');
18.         int index=0;
19.         for(int i=0;i<maxCount;i++){
20.             ret[index]=maxChar;
21.             index+=2;
22.         }
24.         hash[maxChar-'a']=0;
25.         for(int i=0;i<26;i++){
26.             for(int j=0;j<hash[i];j++){
27.                 if(index>=n) index=1;
28.                 ret[index]='a'+i;
29.                 index+=2;
30.             }
31.         }
32.         return ret;
33.     }
34. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告