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

01.整数替换

题目链接：https://leetcode.cn/problems/integer-replacement/

给定一个正整数 n ，你可以做如下操作：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路

这里我们要求得最小次数，要进行具体的分析讨论，首先偶数只有一种情况，所以不必讨论，若是奇数则分为一下三种情况：

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

代码

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

02.俄罗斯套娃信封问题

题目链接：https://leetcode.cn/problems/russian-doll-envelopes/

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

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

示例 2：

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

提示：

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

思路

重写排序+贪心+二分的思想：

我们先按照左端点不同时升序排序，左端点相同时按右端点降序排序，这样我们只需要考虑右端点，再使用贪心+二分就可以很好的解决这个问题

代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end(),[&](const vector<int>& v1,const vector<int>& v2){
            return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]>v2[1];
        });

        vector<int> ret;
        ret.push_back(envelopes[0][1]);

        for(int i=1;i<envelopes.size();i++){
            int b=envelopes[i][1];
            if(b>ret.back()) ret.push_back(b);
            else{
                int left=0,right=ret.size()-1;
                while(left<right){
                    int mid=(left+right)/2;
                    if(ret[mid]>=b) right=mid;
                    else left=mid+1;
                }
                ret[left]=b;
            }
        }
        return ret.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

03.可被三整除的最大和

题目链接：https://leetcode.cn/problems/greatest-sum-divisible-by-three/

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

思路

首先我们先将所有的值累加起来，那么就会有下面三种情况

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

代码

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        const int INF=0x3f3f3f3f;
        int sum=0,x1=INF,x2=INF,y1=INF,y2=INF;
        for(int& x:nums){
            sum+=x;
            if(x%3==1){
                if(x<x1) x2=x1,x1=x;
                else if(x<x2) x2=x;
            }else if(x%3==2){
                if(x<y1) y2=y1,y1=x;
                else if(x<y2) y2=x;
            }
        }

        if(sum%3==0) return sum;
        else if(sum%3==1) return max(sum - x1,sum-y1-y2);
        else return max(sum-y1,sum-x1-x2);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

04.距离相等的条形码

题目链接：https://leetcode.cn/problems/distant-barcodes/

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

示例 1：

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

示例 2：

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

提示：

• 1 <= barcodes.length <= 10000
• 1 <= barcodes[i] <= 10000

思路

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

代码

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int> hash;
        int maxval=0,maxCount=0;
        for(int& x:barcodes){
            if(maxCount<++hash[x]){
                maxCount=hash[x];
                maxval=x;
            }
        }

        int n=barcodes.size(),index=0;
        vector<int> ret(n);
        for(int i=0;i<maxCount;i++){
            ret[index]=maxval;
            index+=2;
        }

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

05.重构字符串

题目链接：https://leetcode.cn/problems/reorganize-string/

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

示例 1:

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

示例 2:

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

提示:

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

思路

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

代码

class Solution {
public:
    string reorganizeString(string s) {
        int hash[26]={0};
        char maxChar=' ';
        int maxCount=0;
        for(char& ch:s){
            if(maxCount<++hash[ch-'a']){
                maxChar=ch;
                maxCount=hash[ch-'a'];
            }
        }

        int n=s.size();
        if(maxCount>(n+1)/2) return "";

        string ret(n,' ');
        int index=0;
        for(int i=0;i<maxCount;i++){
            ret[index]=maxChar;
            index+=2;
        }

        hash[maxChar-'a']=0;
        for(int i=0;i<26;i++){
            for(int j=0;j<hash[i];j++){
                if(index>=n) index=1;
                ret[index]='a'+i;
                index+=2;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34