贪心系列专题篇四

目录

整数替换

解法一

解法二

俄罗斯套娃信封问题

堆箱子

可被三整除的最大和

距离相等的条形码

重构字符串

---

声明：接下来主要使用贪心法来解决问题！！！

整数替换

题目

思路

下面将使用两种方法来解决这道题，第一种方法是递归+记忆化搜索；第二种方法是贪心。

解法一

使用递归+记忆化搜素来解决，因为递归当对数进行两种操作时，会用到相同的值，因此记录下每个数的最小替换次数将会更佳。

代码

class Solution {
public:
    int integerReplacement(int n) {
        return dfs(n);
    }
 
    int dfs(long long n){
        if(n==1)
            return 0;
        if(n%2==0)
            return 1+dfs(n/2);
        else
            return 1+min(dfs(n+1),dfs(n-1));
    }
};//只递归版
 
 
 
class Solution {
    unordered_map<int,int> hash;
public:
    int integerReplacement(int n) {
        return dfs(n);
    }
 
    int dfs(long long 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];
        }
    }
};//递归+记忆化搜素

解法二

依题意，对于偶数，只执行除2操作，对奇数有+1和-1操作，那么如何能区分出+1和-1哪个操作更优那？

将奇数分成3类进行讨论：分别是3，大于3且模4等于1，大于3且模4等于3.

贪心策略

对于3，最少操作次数确定为2；

对于大于3且模4等于1，易知进行-1操作优于+1操作；

对于大于3且模4等于3，易知进行+1操作优于-1操作；

代码

class Solution {
public:
    int integerReplacement(long long n) {
        int ret=0;
        while(n>1){
            if(n%2==0){
                n/=2;
                ret++;
            }
            else{
                if(n==3){
                    ret+=2;
                    n=1;
                }
                else if(n%4==1){
                    n-=1;
                    ret++;
                }
                else if(n%4==3){
                    n+=1;
                    ret++;
                }
            }
        }
        return ret;
    }
};

俄罗斯套娃信封问题

题目

思路

首先我们先对集合按区间左端点进行排序，因为如果不排序的话，比较两个区间左端点的大小是需要不断遍历集合的。

通过分析这道题，我们会发现就是要找出一个最长的俄罗斯套娃序列即可，与《最长递增子序列》几乎是如出一辙，可以使用动态规划和定义排序+贪心+二分来解决，但是使用动态规划的时间复杂度是O(N^2)，对于本道题是会超时的，下面将使用定义排序+贪心+二分来解决，时间复杂度是O(N^logN)的，贪心+二分是怎样的，如下：
我们知道，对于一个递增子序列，如果递增子序列某个位置的数在原始数组中该数后面的数比它小，那么可以以这个较小的数替换它，显而易见是可以的，不过这样找出来的结果虽然不是对应的最长递增子序列所对应的数，但是长度是一致的。

更新规则如下：从前往后扫描数组，当找到的数大于已记录的数，就把这个数放到长度更长的对应位置；如果找到的数大于某个位置的数，就往后找到合适的位置；当找到的数小于等于某个位置的数，就覆盖这个位置的数。

优化：扫描整个数组是必不可少的，可优化的地方就是找对应合适的位置，可使用二分查找代替再次遍历整个数组。

但是为什么要定义排序那？因为按常规排序时，得到的序列是如下图第一行所示，

因为已经排好序，因此我们只需要考虑每个二元组的第二个元素即可，和《最长递归子序列》一样；但是如果像下图第二行，就不行了，如果两个二元组的第一个元素相等，只考虑每个二元组的第二个元素，找出的结果可能不符合，因为题目要求外层的信封的宽度和高度都大于里层的信封的高度和宽度，解决办法，将二元组的第一个元素按升序进行排序，如果两个二元组的第一个元素相等，则将这类二元组的第二个元素按降序排序即可，如下面第二张图：

代码

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n=envelopes.size();
        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> v;
        v.push_back(envelopes[0][1]);
        for(int i=1;i<n;i++){
            if(envelopes[i][1]>v.back())
                v.push_back(envelopes[i][1]);
            else{
                int left=0,right=v.size()-1;
                while(left<right){
                    int mid=(left+right)>>1;
                    if(v[mid]<envelopes[i][1])
                        left=mid+1;
                    else
                        right=mid;
                }
                v[left]=envelopes[i][1];
            }
        }
        return v.size();
    }
};

堆箱子

题目

思路

首先我们先对集合按区间左端点进行排序，因为如果不排序的话，比较两个区间左端点的大小是需要不断遍历集合的。

通过分析这道题，我们会发现就是要找出一个最长的升序序列即可，与《最长递增子序列》几乎是如出一辙，可以使用动态规划和定义排序+贪心+二分来解决，使用动态规划的时间复杂度是O(N^2)。

代码

class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        int n=box.size();
        sort(box.begin(),box.end());
        vector<int> dp(n);
        for(int i=0;i<n;i++){
            dp[i]=box[i][2];
            for(int j=0;j<i;j++){
                if(box[i][0]>box[j][0] && box[i][1]>box[j][1] && box[i][2]>box[j][2])
                    dp[i]=max(dp[i],dp[j]+box[i][2]);
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};

可被三整除的最大和

题目

思路

贪心策略

如果我们通过拼凑若干个数来找到可被三整除的最大和是较为困难的，此时我们不妨尝试“正难则反”，先求出所有数的和，看是否能被三整除，如果能被三整除的话，所有数的和肯定是最大的值；如果不能被三整除的话，就删除某些数，如果总和模3余1，要么删除1个模3等于1的数，要么删除两个数的和模3等于2的数中最小的和次最小的数；如果总和模3余2，要么删除1个模等于2的数，要么删除两个数的和模3等于1的数中最小的和次最小的数。

寻找数组中最小和次最小的数，要么对数组排序的方式找，时间复杂度是O(N^logN），要么遍历整个数组，使用两个变量来记录数组中最小和次最小的数，时间复杂度是O(N），更优。

代码

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);
    }
};

距离相等的条形码

题目

思路

首先统计出现次数最多的数出现的次数，因为题目保证存在答案，因此这个次数的值肯定小于等于(数组大小n+1)/2的。

贪心策略

我们先把出现次数最多的数进行摆放，把出现次数最多的数摆放在奇数位置处，然后再摆放剩下的其余的数，只需要摆放两遍即可，先把所有的奇数位置处摆放完，再摆放偶数处的位置，这样能保证相邻位置的两个数是不相同的。

代码

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();
        vector<int> ret(n);
        int index=0;
        for(int i=0;i<maxCount;i++){
            ret[index]=maxVal;
            index+=2;
        }
        hash.erase(maxVal);
        for(auto& [a,b]:hash){
            for(int i=0;i<b;i++){
                if(index>=n) index=1;
                ret[index]=a;
                index+=2;
            }
        }
        return ret;
    }
};

重构字符串

题目

思路

这一道题和上一道题几乎是一模一样的，不同之处是这道题不一定能成功重排字符。

首先统计出现次数最多的字符出现的次数，这个次数的值可能小于等于(数组大小n+1)/2，也可能大于(数组大小n+1)/2，此时返回空串。

贪心策略

我们先把出现次数最多的字符进行摆放，把出现次数最多的字符摆放在奇数位置处，然后再摆放剩下的其余的字符，只需要摆放两遍即可，先把所有的奇数位置处摆放完，再摆放偶数处的位置，这样能保证相邻位置的两个字符是不相同的。

代码

class Solution {
public:
    string reorganizeString(string s) {
        int n=s.size();
        int hash[26];
        char ch;
        int maxCount=0;
        for(char c:s){
            if(maxCount<++hash[c-'a']){
                maxCount=hash[c-'a'];
                ch=c;
            }
        }
        if(maxCount>(n+1)/2) return "";
        else{
            string str(n,' ');
            int index=0;
            for(int i=0;i<maxCount;i++){
                str[index]=ch;
                index+=2;
            }
            hash[ch-'a']=0;
            for(int i=0;i<26;i++){
                for(int j=0;j<hash[i];j++){
                    if(index>=n) index=1;
                    str[index]=i+'a';
                    index+=2;
                }
            }
            return str;
        }
    }
};
 
 
 
 
 
 
 
 
 
 
 
 
// class Solution {
// public:
//     string reorganizeString(string s) {
//         int n=s.size();
//         unordered_map<char,int> hash;
//         char ch;
//         int maxCount=0;
//         for(char c:s){
//             if(maxCount<++hash[c]){
//                 maxCount=hash[c];
//                 ch=c;
//             }
//         }
//         string str;
//         if(maxCount>(n+1)/2) return str;
//         else{
//             str.resize(n);
//             int index=0;
//             for(int i=0;i<maxCount;i++){
//                 str[index]=ch;
//                 index+=2;
//             }
//             hash.erase(ch);
//             for(auto& [t,k]:hash){
//                 for(int i=0;i<k;i++){
//                     if(index>=n) index=1;
//                     str[index]=t;
//                     index+=2;
//                 }
//             }
//             return str;
//         }
//     }
// };