LeetCode第276场周赛题解

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;
    }
};
上一篇:CodeForces-75A


下一篇:力扣每日一题21.07.24