网站建设seo视频,学生个人网页设计素材图片,wordpress 本地配置文件,小城镇建设网站的观点目录 100233. 重新分装苹果 简单100247. 幸福值最大化的选择方案 中等100251. 数组中的最短非公共子字符串 中等100216. K 个不相交子数组的最大能量值 困难 100233. 重新分装苹果 简单
100233. 重新分装苹果
分析#xff1a; 排序贪心
代码#xff1a;
class Solution {… 目录 100233. 重新分装苹果 简单100247. 幸福值最大化的选择方案 中等100251. 数组中的最短非公共子字符串 中等100216. K 个不相交子数组的最大能量值 困难 100233. 重新分装苹果 简单
100233. 重新分装苹果
分析 排序贪心
代码
class Solution {
public:int minimumBoxes(vectorint apple, vectorint capacity) {int cnt accumulate(apple.begin(), apple.end(), 0);sort(capacity.begin(), capacity.end());int icapacity.size()-1;for(;i0cnt0;i--){cnt-capacity[i];}return capacity.size()-i-1;}
};100247. 幸福值最大化的选择方案 中等
100247. 幸福值最大化的选择方案
分析 排序贪心。 每次选择当前幸福值最大的孩子其余孩子幸福值均减小1直至减小至0。
代码
class Solution {
public:long long maximumHappinessSum(vectorint happiness, int k) {long long ans0;sort(happiness.begin(), happiness.end());int ihappiness.size()-1,cnt0;while(k--){ans(1LL*(max(happiness[i]-cnt,0)));cnt;i--;}return ans;}
};100251. 数组中的最短非公共子字符串 中等
100251. 数组中的最短非公共子字符串
分析
代码 利用map实现哈希表后续需要学习字符串哈希
class Solution {
public:vectorstring shortestSubstrings(vectorstring arr) {unordered_mapstring, int m,mine;vectorstring ans;int narr.size();for(int i0;in;i){int larr[i].length();mine.clear();for(int j1;jl;j){for(int k0;kj-1l;k){string s arr[i].substr(k,j);if(mine[s]0){ // 同一个字符串中的字符只计算一次m[s];mine[s];}}}}for(int i0;in;i){int larr[i].length();for(int j1;jl;j){vectorstring a;for(int k0;kj-1l;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:vectorstring shortestSubstrings(vectorstring arr) {int n arr.size();vectorstring ans(n);for(int i0;in;i){for(int len1;lenarr[i].size();len){for(int j0;jlenarr[i].size();j){string s arr[i].substr(j,len);bool flag true;for(int k0;kn;k) if(k!i arr[k].find(s) ! string::npos) {flagfalse; 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(vectorint nums, int k) {int n nums.size();vectorlong long s(n 1);for (int i 0; i n; i) {s[i 1] s[i] nums[i];// 前缀和}vectorvectorlong long f(k 1, vectorlong 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];}
};
