LeetCode周赛288场题解合集

大家好，我是梁唐。

今天是周一，老规矩，我们一起来看昨天上午的LeetCode周赛。本文始发于公众号：Coder梁

这场比赛是由Airwallex 空中云汇举办的，没记错这是一家总部在澳洲的公司，国内的分部在上海。

这次的奖品还不错，前300名可以获得内推资格。

本场比赛的难度很大，大到我第四题没有做出来，依然能排进前300……

好了，废话不多说了，我们一起来看题吧。

按奇偶性交换后的最大数字

难度：2星

给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。

返回交换 任意 次之后 num 的 最大 可能值*。*

解法

这题本身难度不大，给的范围也很小，属于无论怎么弄都能过的题。

我比赛的时候没能想到最优解，用的是奇偶拆分的笨办法过的。

class Solution {
public:
    int largestInteger(int num) {
        vector<int> odd, even, is_odd;
        int cur = num;
        while (cur > 0) {
            int bit = cur % 10;
            cur /= 10;
            is_odd.push_back(bit % 2);
            if (bit % 2) {
                odd.push_back(bit);
            }else even.push_back(bit);
        }
        reverse(is_odd.begin(), is_odd.end());
        sort(odd.begin(), odd.end());
        sort(even.begin(), even.end());
    
        int ret = 0;
        for (int i = 0; i < is_odd.size(); i++) {
            if (is_odd[i]) {
                ret = ret * 10 + odd.back();
                odd.pop_back();
            }else {
                ret = ret * 10 + even.back();
                even.pop_back();
            }
        }
        return ret;
    }
};

赛后看到大佬的代码才发现，我们可以把它转化成字符串来进行操作。这样的话，我们就可以随意调换数字了。

本质上就是选择排序的思路，只不过我们加上了限制条件，除了s[j]要更大，还需要s[i]和s[j]奇偶性相同。

class Solution {
public:
    int largestInteger(int num) {
        auto s = to_string(num);
        int n = s.length();
        
        for (int i = 0; i < n; i++) 
            for (int j = i+1; j < n; j++) {
                if (s[i] % 2 == s[j] % 2 && s[i] < s[j]) {
                    swap(s[i], s[j]);
                }
            }
        
        return atoi(s.c_str());
    }
};

向表达式添加括号后的最小结果

难度：2.5星

给你一个下标从 0 开始的字符串 expression ，格式为 "+" ，其中 和 表示正整数。

请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到 最小 可能值。左括号 必须 添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。

返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到 最小 可能值*。*如果存在多个答案都能产生相同结果，返回任意一个答案。

生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。

解法

这题思路其实并不难，因为括号可以出现的位置是非常有限的。左括号只能出现在+左侧，而有括号只能出现在+右侧。并且题目中也说了，表达式的长度最大是10，所以我们要做的很简单，就是枚举一下括号可以出现的合法位置，然后计算一下对应表达式的值即可。

加上括号之后，最多分成三个部分，即括号左侧括号当中和括号右侧。比如1(2+3)4，这三个部分除了中间部分以外都有可能为空，为空的话我们只需要把它当成1相乘即可。

由于涉及到字符串操作，所以比赛的时候使用了Python，其实用C++也一样。

class Solution:
    def minimizeResult(self, expression: str) -> str:
        ele = expression.split('+')
        left, right = ele
        
        ret = 1e18
        
        def to_num(x):
            if len(x) == 0:
                return 1
            return int(x)
        
        exp = ''
        
        for i in range(len(left)):
            for j in range(1, len(right)+1):
                cur = to_num(left[:i]) * (to_num(left[i:]) + to_num(right[:j])) * to_num(right[j:])
                if cur < ret:
                    ret = cur
                    exp = '{}({}+{}){}'.format(left[:i], left[i:], right[:j], right[j:])
                    
        return exp

下面是C++的版本，由于没有切面，所以会显得稍微复杂一些：

class Solution {
    public:
    string minimizeResult(string exp) {
        int n = exp.length();
        int x = exp.find('+');
        string lef = exp.substr(0, x), rig = exp.substr(x+1, n-x);
        
        int tmp = INT_MAX;
        string ret = "";
        
        auto f = [&](string s) -> int {
            if (s.length() == 0) return 1;
            return atoi(s.c_str());
        };
        
        for (int i = 0; i < lef.length(); i++) {
            for (int j = 1; j <= rig.length(); j++) {
                int cur = f(lef.substr(0, i)) * (f(lef.substr(i)) + f(rig.substr(0, j))) * f(rig.substr(j));
                if (cur < tmp) {
                    tmp = cur;
                    ret = lef.substr(0, i) + "(" + lef.substr(i) + "+" + rig.substr(0, j) + ")" + rig.substr(j);
                }
            }
        }
        return ret;
    }
};

K 次增加后的最大乘积

难度：3.5星

给你一个非负整数数组 nums 和一个整数 k 。每次操作，你可以选择 nums 中 任一 元素并将它 增加 1 。

请你返回 至多 k 次操作后，能得到的 nums的 最大乘积 。由于答案可能很大，请你将答案对 109 + 7 取余后返回。

解法

题意不难，但是数据范围不小，尤其是k的范围有1e5，明显不能暴力求解，但一时也找不出什么明显的诀窍，我估计很多同学可能直接懵住了，不知道从何入手。

其实只要冷静下来，找几个例子看看，是能够发现一点端倪的。

首先可以发现，如果数组nums当中存在0，那么肯定要先想办法把0给增加。否则其他数字无论多大，最后的乘积都是0。把0处理完了之后，应该怎么做呢？本能上可能会有一点感觉，也许可以贪心，每次都拿最小的元素出来+1，但这道题贪心能成立吗？

我们假设当前数组当中已经没有0了，所有元素的乘积是P。假设我们选择递增的数是x，那么递增之后的乘积就是Px+1xP \frac{x+1} xPxx+1​。我们可以看下函数x+1x\frac {x+1} xxx+1​的图像：

不难发现这是一个单调递减函数，也就是说x越大，这个值越小。也就是说我们每次选择用来+1的数越小，对于最后乘积的贡献就越大。

基于简单的数学分析，很容易发现，贪心是可行的。既然贪心可行，那么我们只需要使用优先队列来维护一下nums当中的所有元素，每次取出最小的数来进行+1操作，最后再把它们乘到一起即可。

class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        long long mod = 1e9 + 7;
        int n = nums.size();
        // 传入greater，让小的元素排在前
        priority_queue<int, vector<int>, greater<int>> que(nums.begin(), nums.end());
        
        for (int i = 0; i < k; i++) {
            int cur = que.top();
            que.pop();
            cur++;
            que.push(cur);
        }
        
        long long tmp = 1;
        for (int i = 0; i < n; i++) {
            tmp *= (long long)que.top();
            que.pop();
            tmp = tmp % mod;
        }
        return tmp;
    }
};

花园的最大总美丽值

难度：五星

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花 不能 移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。

如果一个花园有 至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之 和 ：

• 完善 花园数目乘以 full.
• 剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。

请你返回 Alice 种最多 newFlowers 朵花以后，能得到的 最大 总美丽值。

解法

这道题非常麻烦，要考虑的情况也非常多。

虽然不完善的花园也能得分，但不完善的花园只会计分一次。要让能够获得的总分最大，我们要尽量保证不完善的花园中花朵的最小值尽量大，同时尽可能让完善的花园尽量多。

进一步，可以想到，如果花园A的花朵数大于花园B，那么花园A比B更应该完善。所以我们可以考虑优先选择花朵较多的花园进行完善。

但同样有一个问题，并不是完善的花园越多约优，比如样例2就是一个经典的反例。

所以只是简单地贪心，尽可能多地完善花园是行不通的。这样一来，我们就没办法直接计算出到底完善多少花园能够得到最优解，所以，这个变量是必须要通过枚举获取的。

进而可以想到，我们可以对花园按照花朵数量进行排序，并且对花朵的数量进行处理，将超过target的部分去掉。

在计算花园中花朵数的前缀和：sums[i] = flower[0] + flower[1] + ... + flower[i-1]

有了前缀和数组之后，我们可以快速计算任意一个下标区间对应的元素和。例如区间[i, j]的区间和等于sums[j+1] - sums[i]。假设我们要将区间[i, j]的花园中的花朵全部补齐到target朵，我们可以直接使用(j-i+1) * target - (sums[j+1] - sums[i])来进行计算，就不需要再通过循环累加了。

我们之前把超过target的部分抹掉，正是为了这里计算方便。

如果上面没看懂没有关系，可以先放一放，我们先来做推理。

我们要做的是枚举完整花坛的数量x，如果x == n那么所有花坛都是完整的，直接返回n * full。

如果x < n，显然我们要选择花朵最多的x个花坛将它们补充完整，需要补充的花朵数我们可以通过前缀和快速计算。

接下来，我们要在剩下的n - x个花坛当中种植m朵花使得花坛中花朵的最小值最大，m是补充x个花坛剩下的花朵数。

我们假设要补充j个花坛，这个最大值是T，那么它应该满足T * j - sum(花朵数)<= m。这个式子里有两个变量T和j，我们没办法直接计算。所以只能枚举。我们可以枚举j，这样除了T以外都是定值，我们可以直接计算。

j的取值范围是[0, m-x)，如果无脑枚举需要消耗O(n)O(n)O(n)的复杂度，再加上外层x的枚举，整体的复杂度会达到O(n2)O(n^2)O(n2)，显然会超时。

所以我们要想办法优化， 怎么优化呢？需要我们来观察一下式子：T * j - sum(花朵数)<= m

这个式子的右边m随着x的增大是减小的，因为x越大，说明消费的花朵越多，剩余的花朵也就越少。

既然m在减小，那么j整体趋势也是递减的。如果不理解也没有关系，我们可以参考一下下图。在下图当中，当i减小的时候，意味着我们用了更多的花朵去弥补完整的花坛，那么留给不完整的部分肯定就变少了。

既然留给不完整的花坛的花变少了，j势必也要向左移动。

这道题的思路很不直观，并且边边角角的情况非常多，因此编码还是很有难度的。

建议大家可以结合图片和代码一起理解，会容易一些。

class Solution {
public:
    long long maximumBeauty(vector<int>& flowers, long long newf, int target, int full, int partial) {
        int n = flowers.size();
        vector<long long> sums(n+2, 0);
        
        sort(flowers.begin(), flowers.end());
        for (int i = 0; i < n; i++) {
            if (flowers[i] >= target) flowers[i] = target;
            sums[i+1] = flowers[i] + sums[i];
        }
       
        long long ret = 0;
        int j = n-1;
        long long left = newf;
        for (int i = n; i > -1; i--) {
            // 当i减小时，剩余的花减去target - flower[i]
            if (i < n) left -= (target - flowers[i]);
            if (left < 0) break;
            if (j >= i) j = i-1;
            // 如果剩余的花朵不够弥补[0, j]到flower[j]时，j--
            while (j >= 0 && (flowers[j] == target || (1LL * flowers[j] * j - sums[j]) > left)) {
                j--;
            }
            // 计算收益值
            long long tmp = 1LL * (n-i) * full + (j < 0 ? 0 : 1LL * partial * min(target-1LL, (left + sums[j+1]) / (j+1)));
            ret = max(ret, tmp);
        }
        return ret;
    }
};

这道题我在比赛的时候推导了很久，最后虽然想出了前缀和来维护，但也没看出j这一层枚举的单调性。最终卡在了极端的case上，没能通过。

从我个人的角度来看，这道题无疑是很有难度的，绝对算得上是难题。

整理思路、推导以及编码都不简单，极端的case也多，确实很不简单，尤其是比赛的时候，想要能顺利做出来，确实很考验人。因此如果没能做出来也不用气馁，难题与其说是用来做的，倒不如说是用来磨炼的。

难题就在那里，只要你坚持不懈发起冲锋，总有一天，你会战胜它。

感谢大家的阅读。