目录
100233. 重新分装苹果
原题链接
思路分析
直接模拟
降序排序capacity，倒序累加，当大于苹果总重量的时候我们就返回
时间复杂度：O(nlgon)
AC代码
class Solution {
public:
int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
int s = accumulate(apple.begin(), apple.end(), 0);
int n = capacity.size();
sort(capacity.begin(), capacity.end(), [](int x, int y){return y < x;});
for(int i = 0, t = 0; i < n; i++) {
t += capacity[i];
if(t >= s) return i + 1;
}
return n;
}
};100247. 幸福值最大化的选择方案
原题链接
思路分析
贪心
优先分配幸福值大的孩子，然后直接模拟
时间复杂度：O(nlgon)
AC代码
class Solution {
public:
long long maximumHappinessSum(vector<int>& a, long long k) {
long long ret = 0;
sort(a.begin(), a.end(), [](int x, int y){return x > y;});
for(int i = 0, t = 0; i < k; i++, t++){
if(a[i] > t) ret += a[i] - t;
}
return ret;
}
};100251. 数组中的最短非公共子字符串
原题链接
思路分析
其实直接暴力就行了
用哈希表或者字典树存储所有字符串的所有子串，然后遍历每个字符串的子串找到不在哈希表或者字典树中的子串中最短并且字典序最小的那个
想着复习下字典树就敲了下字典树
时间复杂度分析：
子串长度有k种，起点有k个，那么存储一个长度为k的字符串的所有子串就是O(k^3)
然后枚举n个字符串的所有字串并判断就是O(n*k^3)
因为k最大也就20，n最大100，因而整体也就1e6左右
故时间复杂度O(n*k^3)是可以的
AC代码
struct node{
unordered_map<char,node*>ch;
unordered_set<int> words;
};
class Solution {
public:
vector<string> shortestSubstrings(vector<string>& arr) {
node* rt = new node, *cur;
vector<string> ret;
for(int k = 0, sz = arr.size(); k < sz; k++)
for(int i = 0, n = arr[k].size(); i < n; i++){
cur = rt;
for(int j = i; j < n; j++){
if(!cur->ch.count(arr[k][j])) cur->ch[arr[k][j]] = new node;
cur = cur->ch[arr[k][j]], cur->words.insert(k);
}
}
for(int k = 0, sz = arr.size(); k < sz; k++){
string tmp;
for(int i = 0, j, n = arr[k].size(); i < n; i++){
cur = rt;
for(j = i; j < n; j++){
cur = cur->ch[arr[k][j]];
if(cur->words.size() == 1){
if(tmp.empty() || j - i + 1 < tmp.size() || (j - i + 1 == tmp.size() && arr[k].substr(i, j - i + 1) < tmp)) tmp = arr[k].substr(i, j - i + 1);
break;
}
}
}
ret.emplace_back(tmp);
}
return ret;
}
};100216. K 个不相交子数组的最大能量值
原题链接
思路分析
考虑题目说n*k <= 1e6，所以想到用dp
定义状态
f[i][j][0]为前i个元素拆出j个子数组且第i个元素在第j个子数组中的最大能量和
f[i][j][1]为前i个元素拆出j个子数组且第i个元素不在第j个子数组中的最大能量和
那么有转移方程
f[i][j][1] = max(f[i - 1][j][0], f[i - 1][j][1]);即不选第i个数，那么直接由上一行转移
选第i个数并且单独成第j组，那么前i-1个数要拆出j-1组，第i-1个数在不在第j-1组取大的那个
if(j)
f[i][j][0] = max(f[i][j][0], max(f[i - 1][j - 1][1], f[i - 1][j - 1][0]) + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);
选第i个数并且加入第j组
f[i][j][0] = max(f[i][j][0], f[i - 1][j][0] + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);
时间复杂度O(nk)
AC代码
class Solution {
public:
long long maximumStrength(vector<int>& nums, int k) {
int n = nums.size();
vector<vector<vector<long long>>> f(n + 1, vector<vector<long long>>(k + 1, vector<long long>(2, -1e18)));
f[0][0][1] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
//不选
f[i][j][1] = max(f[i - 1][j][0], f[i - 1][j][1]);
//选
//单独成组
if(j)
f[i][j][0] = max(f[i][j][0], max(f[i - 1][j - 1][1], f[i - 1][j - 1][0]) + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);
//加到前面
f[i][j][0] = max(f[i][j][0], f[i - 1][j][0] + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);
}
}
return max(f[n][k][0], f[n][k][1]);
}
};
