LeetCode Weekly Contest 276 题解
第一题
题解：直接模拟
class Solution {
public:
vector divideString(string s, int k, char fill) {
vector res;
int n = s.size();
string t ="";
for(int i=0; i 0){
int len = k - t.size();
for(int i=0; i 第二题
题解： 模拟，逆向思维，倒着求解
class Solution {
public:
int minMoves(int target, int maxDoubles) {
int res = 0;
while(target > 1){
if(maxDoubles == 0){
return res + target-1;
}
if(target%2 == 0){
target /= 2;
maxDoubles--;
res++;
}else{
target--;
res++;
}
}
return res;
}
};
第三题
比赛想到的是dfs，写完提交 TLE， 比赛快结束了，想到DP，比赛期间没有写出来，看其他人的提交，发现记忆化dfs可以过。
class Solution {
public:
long long mostPoints(vector>& questions) {
int n = questions.size();
vector dp(n+1);
for(int i=0; i 第四题
题解： 二分， 参考 https://leetcode-cn.com/problems/maximum-running-time-of-n-computers/solution/er-fen-da-an-by-newhar-swi2/
class Solution {
public:
bool check(int n, long long t, vector& batteries){
long long sum = 0;
for(auto c : batteries){
sum += min(t, (long long)c);
}
return (sum/t) >= n;
}
long long maxRunTime(int n, vector& batteries) {
long long l = 1, r = 1e15;
while(l < r){
long long mid = l+r+1 >>1;
if(check(n, mid, batteries)){
l = mid;
}else{
r = mid-1;
}
}
return l;
}
};