贪心算法题目总结

1. 整数替换

看到这道题目，我们首先能想到的方法就应该是递归解法，我们来画个图

此时我们出现了重复的子问题，就可以使用递归，只要我们遇到偶数，直接将n除以2递归下去，如果是奇数，选出加1和减1中最小步数的那个继续递归下去即可，直接看代码：

class Solution {
public:
    int integerReplacement(int n) {
        if(n == 1)
            return 0;
        if(n & 1 == 1) // 奇数
            return min(integerReplacement(n+1),integerReplacement(n-1)) + 1;
        else
            return integerReplacement(n / 2) + 1;
    }
};

然后我们去运行代码，很遗憾，此时代码没有通过，这是因为的递归过程中出现了大量的重复子问题的，这些重复的子问题其实我们已经计算过了，没必要再计算一次，所以我们可以利用记忆化搜索的备忘录来解决这个问题，此时我们递归的时候，如果此时备忘录立马存在这个值，我们就可以直接返回，如果没有这个值，我们再去递归。

class Solution {
    unordered_map<int,int> hash;
public:
    int integerReplacement(int n) {
        // 先判断是否再在备忘录中
        if(hash.count(n)) 
        {
            return hash[n];
        } 
        if(n == 1)
        {
            hash[1] = 0;
            return 0;
        }  
        if(n & 1 == 1) // 奇数
        {
            hash[n] = min(integerReplacement(n+1),integerReplacement(n-1)) + 1;
            return hash[n];
        }
        else
        {
            hash[n] = integerReplacement(n / 2) + 1;
            return hash[n];
        }  
    }
};

但是此时我们发现程序没有通过，通过这个测试案例我们可以知道，当n是2147483647的时候，此时是奇数，会去递归2147483647+1，此时就超过了int的范围。

此时我们需要自己来定义一个dfs函数来解决这个问题。

class Solution {
    unordered_map<int,int> hash;
public:
    int integerReplacement(int n) 
    {
        return dfs(n);
    }
    int dfs(long long int n){
        // 先判断是否再在备忘录中
        if(hash.count(n)) 
        {
            return hash[n];
        } 
        if(n == 1)
        {
            hash[1] = 0;
            return 0;
        }  
        if(n & 1 == 1) // 奇数
        {
            hash[n] = min(dfs(n+1),dfs(n-1)) + 1;
            return hash[n];
        }
        else
        {
            hash[n] = dfs(n / 2) + 1;
            return hash[n];
        }  
    }
};

此时我们的代码就能通过，我们再来写另一种解法。

直接上手代码：

class Solution {
public:
    int integerReplacement(int n) {
        return dfs(n);
    }
    int dfs(long long int n)
    {
        if(n == 1)
            return 0;
        if(n % 2 == 0) // 偶数
        {
            return dfs(n/2) + 1;
        } 
        else
        {
            if(n == 3)
            {
                return dfs(n-1) + 1;
            }
            else if(n % 4 == 1)
            {
                return dfs(n - 1) + 1;
            }
            else if(n % 4 == 3)
            {
                return dfs(n + 1) + 1;
            }
        }
        // 这里有返回值是因为要让所有的路径都有返回值
        return 0;
    }
};

其实我们这里也可以不使用递归来解决这个题目。

class Solution {
public:
    int integerReplacement(int n) {
        int ret = 0;
        while(n > 1)
        {
            if(n % 2 == 0) // 偶数
            {
                n /= 2;
                ret++;
            }
            else // 奇数
            {
                if(n == 3)
                {
                    n = 1;
                    ret += 2;
                }
                else if(n % 4 == 1)
                {
                    n -= 1;
                    n /= 2;
                    ret += 2;
                }
                else if(n % 4 == 3)
                {
                    n /= 2; // 这里需要先除2,防止n+1溢出
                    n += 1;
                    ret += 2;
                }
 
            }
        }
    return ret;
    }
};

2. 俄罗斯套娃信封问题

首先我们看到这个题目，就和我们之前的最长递增子序列是一样的，我们需要对左端点进行排序，然后看是否满足俄罗斯套娃的条件，既然是找最长的套娃个数，此时我们可以使用动态规划来解决这个问题，我们可以假设dp[i]位置表示i位置之前的此时最长的套娃个数，当我们到i的位置的时候，我们需要看看0到i-1位置的最长的套娃个数，如果有一个条件满足俄罗斯套娃的条件，那么最长的套娃个数就可以+1，此时就可以使用动态规划来解决这个问题。

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // 动态规划
        sort(envelopes.begin(), envelopes.end());
        int n = envelopes.size();
        vector<int> dp(n, 1);
        int ret = 1;
 
        for(int i = 1; i < n; i++)
        {   
            for(int j = 0; j < i; j++)
            {
                if(envelopes[i][0] > envelopes[j][0] &&
                    envelopes[i][1] > envelopes[j][1])
                    {
                        dp[i] = max(dp[i], dp[j]) + 1;
                    }
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

但是此时我们的代码会超时，所以此时我们就需要来使用另一种策略

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

3. 可被三整除的最大和

正难则反： 我们可以先把所有的数累加在⼀起，然后根据累加和的结果，贪心的删除⼀些数。

那么我们该如何寻找到最小的和次小的值呢？当然我们可以进行一下sort排序取出最小的和次小的值，但是我们知道sort的底层使用的是快速排序，时间复杂度是O(N*logN)，所以此时并不是最优的选择，我们可以使用O(N)的时间复杂度来解决这个问题：

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int x1 = 0x3f3f3f3f3f;
        int x2 = 0x3f3f3f3f3f;
        int y1 = 0x3f3f3f3f3f;
        int y2 = 0x3f3f3f3f3f;
        int sum = 0;
        // 求出总和,最小和次小的值
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            if(nums[i] % 3 == 1) // 判断当值余数是否为1
            {
                if(nums[i] <= x1)
                    x2 = x1, x1 = nums[i];
                else if(nums[i] > x1 && nums[i] < x2)
                    x2 = nums[i];
            }
            else if(nums[i] % 3 == 2) // 判断当值余数是否为2
            {
                if(nums[i] <= y1)
                    y2 = y1, y1 = nums[i];
                else if(nums[i] > y1 && nums[i] < y2)
                    y2 = nums[i];
            }
        }
        // 分类讨论
        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);
    }
};

4. 距离相等的条形码

这道题目比较简单，我们只需要每次处理一批相同的数字，往 n 个空里面摆放； 每次摆放的时候，隔一个格子摆放一个数，但是我们需要优先处理出现次数最多的那个数，其余的数处理的顺序就没什么要求了。

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> hash; // 统计每个数出现的次数
        int maxVal = 0; // 最大的值
        int maxCount = 0; // 最大值的项数
        for(auto& e : barcodes)
        {
            if(maxCount < ++hash[e])
            {
                maxCount = hash[e];
                maxVal = e;
            }
        }
        vector<int> v(barcodes.size(), 0);
        // 先处理出现次数最多的数
        int index = 0;
        for(int i = 0; i < maxCount; i++)
        {
            v[index] = maxVal;
            index += 2;
        }
        // 处理剩下的数,不用管顺序,直接防即可
        hash.erase(maxVal);
        for(auto& [x, y] : hash)
        {   
            for(int i = 0; i < y; i++)
            {
                // 超过最大位置,需要重新从头开始摆放
                if(index >= barcodes.size()) 
                    index = 1;
                v[index] = x;
                index += 2;
            }
        }
        return v;
    }
};

5. 重构字符串

我们读完题目会发现这道题目和上一道题目是类似的，只不过上一道题目是重排数字，而这道题目是重排字符串，思路基本上都是一致的，但是上一个题目明确告诉了我们所有数字都是可以重排列的，但是我们这个题目不一定，因此我们需要先判断一下，如果出现最多的字符的个数大于(n + 1) / 2 就无法重排，其他情况下就可以直接重排列，那我们直接上代码啦！

class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> hash;
        char maxVal = ' ';
        int maxCount = 0;
        for(auto& x : s)
        {
            if(maxCount < ++hash[x])
            {
                maxCount = hash[x];
                maxVal = x;
            }
        }
 
        if(maxCount > ((s.size() + 1) / 2))
            return "";
        // 先处理出现次数最多的那个字符
        string ret;
        ret.resize(s.size());
        int index = 0;
        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 >= ret.size()) index = 1;
                ret[index] = x;
                index += 2;
            }
        }
        return ret;
 
    }
};