5980. 将字符串拆分为若干长度为 k 的组
题目描述:给定字符串\(s\),和一个整数\(k\),将字符串划分成长度为\(k\)的子串,若最后一个子串长度不足\(k\),则使用\(fill\)填充。
思路:根据题意模拟即可
时间复杂度:\(O(n)\)
参考代码:
class Solution {
public:
vector<string> divideString(string s, int k, char fill) {
vector<string> res;
string t;
for(auto c : s){
t += c;
if(t.size() == k) res.push_back(t) , t.clear();
}
if(t.size() == 0) return res;
while(t.size() < k) t += fill;
res.push_back(t);
return res;
}
};
5194. 得到目标值的最少行动次数
题目描述:给你一个整数\(x = 1\),每次你可以执行下列操作中的某一个:
- \(x = x + 1\)
- \(x = 2 * x\)
操作二至多maxDoubles
次。问将\(x\)变成\(target\)的最小操作次数。
思路:考虑倒着做,若当前\(target\)为计数,减一,若为偶数就除以\(2\),直到\(target\)变成\(1\)或者操作二的次数用完,剩下的全部用操作一
复杂度:\(O(logn)\),\(n = target\)。
参考代码:
class Solution {
public:
int minMoves(int target, int maxDoubles) {
int res = 0;
while(target != 1 && maxDoubles != 0){
if(target & 1) target --;
else target >>= 1, --maxDoubles;
++res;
}
res += target - 1;
return res;
}
};
5982. 解决智力问题
题目描述:给你一个下标从\(0\)开始的二维整数数组 questions
,其中 questions[i] = [pointsi, brainpoweri]
。这个数组表示一场考试里的一系列题目,你需要 按顺序 (也就是从问题 \(0\) 开始依次解决),针对每个问题选择 解决 或者 跳过 操作。解决问题\(i\)将让你 获得 \(points_i\)的分数,但是你将无法解决接下来的\(brainpower_i\)个问题(即只能跳过接下来的 \(brainpower_i\) 个问题)。如果你跳过问题 \(i\),你可以对下一个问题决定使用哪种操作。
比方说,给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
:
- 如果问题 \(0\) 被解决了, 那么你可以获得 \(3\) 分,但你不能解决问题 \(1\) 和 \(2\) 。
- 如果你跳过问题 \(0\) ,且解决问题 \(1\) ,你将获得 \(4\)分但是不能解决问题 \(2\) 和 \(3\) 。
请你返回这场考试里你能获得的最高分数。
思路:比较明显的\(dp\)。设状态\(f_i\)表示选择第\(i\)个任务所能获得的最高分数,则转移方程为:
\[f_i = max(f_i , f_{i - 1})\\ f_{i + j + 1} = max(f_{i+ j + 1} , f_i + position_i)\;j = brainpower_i \]时间复杂度:\(O(n)\)
参考代码:
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<long long>f(n + 1 , 0);
for(int i = 0 ; i < n ; ++i){
int j = questions[i][1] , val = questions[i][0];
if(i != 0) f[i] = max(f[i] , f[i - 1]);
int k = min(n , i + j + 1);
f[k] = max(f[k] , f[i] + val);
}
return f[n];
}
};
5983. 同时运行 N 台电脑的最长时间
题目描述:给你\(n\)台电脑和\(m\)个电池,每个电池可以让一台电脑运行\(batteries_i\)分钟。问可以让\(n\)台电脑同时运行的最长分钟数数。
数据范围:\(1 \leq n \leq m , 1 \leq batteries_i \leq 10^9\)
思路:比较明显的二分答案,二分最终的运行时间mid
,那么每个电池的供电时间为min(mid , batteries_i)
,总的供电时间为\(sum = \sum\limits_{i = 1}^{m} min(mid , batteries_i)\)。只需检验\(\frac{sum}{mid} \geq n\)即可。
时间复杂度:\(O(mlog10^{14})\) \(10^{14}\)为最大的和。
参考代码:
class Solution {
public:
long long maxRunTime(int n, vector<int>& batteries) {
auto check = [&](long long mid)->bool{
long long sum = 0;
for(auto& batterie : batteries) sum += min(mid , 1ll * batterie);
return sum / mid >= n;
};
long long lr = 1 , rs = 1e14, res = 1;
while(lr <= rs){
long long mid = lr + rs >> 1;
if(check(mid)) res = mid , lr = mid + 1;
else rs = mid - 1;
}
return res;
}
};