【LeetCode周赛】第388场周赛

100233. 重新分装苹果 简单

100233. 重新分装苹果

分析：
排序+贪心

代码：

class Solution {
public:int minimumBoxes(vector<int>& apple, vector<int>& capacity) {int cnt = accumulate(apple.begin(), apple.end(), 0);sort(capacity.begin(), capacity.end());int i=capacity.size()-1;for(;i>=0&&cnt>0;i--){cnt-=capacity[i];}return capacity.size()-i-1;}
};

100247. 幸福值最大化的选择方案 中等

100247. 幸福值最大化的选择方案

分析：
排序+贪心。
每次选择当前幸福值最大的孩子，其余孩子幸福值均减小1，直至减小至0。

代码：

class Solution {
public:long long maximumHappinessSum(vector<int>& happiness, int k) {long long ans=0;sort(happiness.begin(), happiness.end());int i=happiness.size()-1,cnt=0;while(k--){ans+=(1LL*(max(happiness[i]-cnt,0)));cnt++;i--;}return ans;}
};

100251. 数组中的最短非公共子字符串 中等

100251. 数组中的最短非公共子字符串

分析：

代码：
利用map实现哈希表，后续需要学习字符串哈希

class Solution {
public:vector<string> shortestSubstrings(vector<string>& arr) {unordered_map<string, int> m,mine;vector<string> ans;int n=arr.size();for(int i=0;i<n;i++){int l=arr[i].length();mine.clear();for(int j=1;j<=l;j++){for(int k=0;k+j-1<l;k++){string s= arr[i].substr(k,j);if(mine[s]==0){ // 同一个字符串中的字符只计算一次m[s]++;mine[s]++;}}}}for(int i=0;i<n;i++){int l=arr[i].length();for(int j=1;j<=l;j++){vector<string> a;for(int k=0;k+j-1<l;k++){string s = arr[i].substr(k, j);if(m[s]==1){a.push_back(s);}}if(a.size()>0){sort(a.begin(),a.end());ans.push_back(a[0]);}if(ans.size()>i) break;}if(ans.size()<=i) ans.push_back("");}return ans;}
};

利用 string.find()来进行优化，去除哈希表(利用map实现hash)的使用。

class Solution {
public:vector<string> shortestSubstrings(vector<string>& arr) {int n = arr.size();vector<string> ans(n);for(int i=0;i<n;i++){for(int len=1;len<=arr[i].size();len++){for(int j=0;j+len<=arr[i].size();j++){string s = arr[i].substr(j,len);bool flag = true;for(int k=0;k<n;k++) if(k!=i && arr[k].find(s) != string::npos) {flag=false; break;}if(flag && (ans[i].empty() || s < ans[i])) ans[i]=s;}if(ans[i].size() > 0) break;}}return ans;}
};

100216. K 个不相交子数组的最大能量值 困难

100216. K 个不相交子数组的最大能量值

分析：
前缀和+划分DP，目前还在尝试理解中。

代码：

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)); //dp[i][j]表示将0~j-1分成i段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);// 要保证前0~j-1至少有i个元素，同时保证j~n-1至少有k-i个元素for (int j = i; j <= n - k + i; j++) {// 维护 i-1 到 当前 j-1 的最大值// 选择 nums[j-1]且为 第i个子数组的最右端元素，但第 i 个子数组有多少，需要从 i-1 开始一直到 j-1 计算 mx = max(mx, f[i - 1][j - 1] - s[j - 1] * w);// 选择当前值的最大值，选nums[j-1]（包含怎么选）或者不选f[i][j] = max(f[i][j - 1], s[j] * w + mx);}}return f[k][n];}
};