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(n2m4)，其中 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 的元素个数。。
标签：周赛,arr,lc,int,题解,复杂度,long,vector,388 From： https://blog.csdn.net/ProgramNovice/article/details/137113008