Leetcode 第 388 场周赛题解

Leetcode 第 388 场周赛题解

题目1：3074. 重新分装苹果

思路

设苹果总数为 sum，从贪心的角度想，为了使选择的箱子数量尽可能小，我们要选择容量尽可能大的箱子。

代码

/*
 * @lc app=leetcode.cn id=3074 lang=cpp
 *
 * [3074] 重新分装苹果
 */

// @lc code=start
class Solution
{
public:
    int minimumBoxes(vector<int> &apple, vector<int> &capacity)
    {
        int sum = accumulate(apple.begin(), apple.end(), 0);
        sort(capacity.begin(), capacity.end(), greater<int>());
        int box = 0;
        for (int &cap : capacity)
        {
            sum -= cap;
            box++;
            if (sum <= 0)
                break;
        }
        return box;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n + mlogm)，其中 n 是数组 apple 的长度， m 是数组 capacity 的长度。

空间复杂度：O(1).

题目2：3075. 幸福值最大化的选择方案

思路

排序 + 贪心。

为了使选中的孩子幸福值之和最大，由于幸福值减到 0 就不再继续减少了，我们从幸福值大的孩子开始选。

代码

/*
 * @lc app=leetcode.cn id=3075 lang=cpp
 *
 * [3075] 幸福值最大化的选择方案
 */

// @lc code=start
class Solution
{
public:
    long long maximumHappinessSum(vector<int> &happiness, int k)
    {
        int n = happiness.size();
        sort(happiness.begin(), happiness.end(), greater<int>());
        long long sum = 0;
        for (int i = 0; i < k; i++)
            sum += max(happiness[i] - i, 0);
        return sum;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组 happiness 的长度。

空间复杂度：O(1)。

题目3：3076. 数组中的最短非公共子字符串

思路

分别计算每个 answer[i]。

对于 arr[i]，从小到大枚举长度 len，然后枚举 arr[i] 的长为 len 的所有子串 temp，判断 temp 是否在其它字符串中，如果不在，就更新 answer[i] 的最小值。

代码

/*
 * @lc app=leetcode.cn id=3076 lang=cpp
 *
 * [3076] 数组中的最短非公共子字符串
 */

// @lc code=start
class Solution
{
public:
    vector<string> shortestSubstrings(vector<string> &arr)
    {
        int n = arr.size();
        vector<string> answer(n);

        // 若 sub 不是 arr 中其他（下标不为 i）任何字符串的子字符串，返回 true
        auto check = [&](int i, string &sub)
        {
            for (int j = 0; j < n; j++)
            {
                if (j != i && arr[j].find(sub) != string::npos)
                    return false;
            }
            return true;
        };

        for (int i = 0; i < n; i++)
        {
            int m = arr[i].size();
            string res;
            for (int len = 1; len <= m && res.empty(); len++)
                for (int begin = 0; begin <= m - len; begin++)
                {
                    string temp = arr[i].substr(begin, len);
                    if ((res.empty() || temp < res) && check(i, temp))
                        res = temp;
                }
            answer[i] = res;
        }

        return answer;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n²m⁴)，其中 n 为字符串数组 arr 的长度，m 为字符串 arr[i] 的长度。

空间复杂度：O(1)。

题目4：3077. K 个不相交子数组的最大能量值

思路

题解：前缀和+划分型DP+式子变形（附题单！）Python/Java/C++/Go

代码

class Solution {
public:
    long long maximumStrength(vector<int> &nums, int k) {
        int n = nums.size();
        vector<long long> s(n + 1);
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + nums[i];
        }
        vector<vector<long long>> f(k + 1, vector<long long>(n + 1));
        for (int i = 1; i <= k; i++) {
            f[i][i - 1] = LLONG_MIN;
            long long mx = LLONG_MIN;
            int w = (k - i + 1) * (i % 2 ? 1 : -1);
            // j 不能太小也不能太大，要给前面留 i-1 个数，后面留 k-i 个数
            for (int j = i; j <= n - k + i; j++) {
                mx = max(mx, f[i - 1][j - 1] - s[j - 1] * w);
                f[i][j] = max(f[i][j - 1], s[j] * w + mx);
            }
        }
        return f[k][n];
    }
};

复杂度分析

时间复杂度：O(k⋅(n−k))，其中 n 是数组 nums 的元素个数。

空间复杂度：O(n)，其中 n 是数组 nums 的元素个数。。