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

\]

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;
    }
};