leetcode276周赛

竞赛链接

T1: 5980. 将字符串拆分为若干长度为 k 的组

---

思路

模拟，按题意操作即可

Code

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        vector<string>ans;
        string ss="";
        for(auto& i:s){
            ss+=i;
            if(ss.size()==k)
                ans.emplace_back(ss),ss="";
        }
        if(ss.size()>0&&ss.size()<k){
            for(int i=ss.size();i<k;++i){
                ss+=fill;
            }
            ans.emplace_back(ss);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

T2: 5194. 得到目标值的最少行动次数

---

思路

不妨逆向考虑这一问题，此时加一操作变为减一，乘二操作变为除以二。我们从目标值开始。如果当前值为奇数，那么只能使用减一；如果当前值为偶数，且可以进行除以二操作，显然要优于使用减一。

Code

class Solution {
public:
    int minMoves(int tar, int mds) {
        long long x=2,cnt=1;
        while(tar!=1){
            while(mds>=1&&tar%2==0){   
                cnt++;
                mds--;
                tar/=2;
            }
            if(mds>0&&tar%2==1&&tar!=1){  //除的次数还有，但不能够整除
                tar--;
                cnt++;
            }
            else if(mds==0&&tar>1){   //除的次数不够了，直接可以算出结果
                cnt+=tar-1;
                tar=1;
            }
        }
        return cnt-1;
    }
};

复杂度分析

• 时间复杂度：O(log(N))
• 空间复杂度：O(1)

T3: 5982. 解决智力问题

---

思路

容易想到动态规划求解。

令 dp[i][0] 表示第 i 天开始时不解决问题可以取得的最高分数，从第 i 天开始解决问题 dp[i][1] 可以取得的最高分数。

• 如果这一天不做题，则直接以 max(dp[i+1][0],dp[i+1][1]) 分数更新当天开始时的最高分数。

• 如果这一天选择做题，dp[i][1]=que[i][0]，若 idx=i+que[i][1]+1 不越界的话，则需累加上 max(dp[idx][1],dp[idx][0])

Code

class Solution {
public:
    long long dp[100010][2];
    long long mostPoints(vector<vector<int>>& que) {
        int n=que.size();
        dp[n-1][1]=que[n-1][0];
        for(int i=n-2;i>=0;--i){
            int idx=i+que[i][1]+1;   //上一个解决问题的位置
            dp[i][0]=max(dp[i+1][0],dp[i+1][1]);
            dp[i][1]=que[i][0];
            if(idx<n&&idx>=0)
                dp[i][1]+=max(dp[idx][1],dp[idx][0]);
        }

        return max(dp[0][0],dp[0][1]);
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

T4: 5983. 同时运行 N 台电脑的最长时间

---

思路

有这么一个暴论：
若总的供电时间为 t ，则容量大于 t 的部分都可以被忽略。此时总能找到一种方案让每一个电池不同时为两台电脑供电且供电时间为总容量的平均值。
所以二分答案 ans ，对于容量大于 ans 的电池视为容量为 ans ，然后计算总容量，当它不小于 n * ans 的时候视为判定成功。

Code

class Solution {
public:
    long long maxRunTime(int n, vector<int>& batteries) {
        int m = batteries.size();
        sort(batteries.begin(), batteries.end());
        vector<long long> pre(m + 1);
        for (int i = 0; i < m; ++i)  //前缀和，方便后续直接计算结果
            pre[i + 1] = pre[i] + batteries[i];

        auto check = [&](long long mid) {
            int k = upper_bound(batteries.begin(), batteries.end(), mid) - batteries.begin();
            return pre[k] + mid * (m - k) >= mid * n;   //当m>k时，肯定会多出m-k个空闲的来替换前面不足的电池
        };

        long long lo = 0, hi = pre[m] / n;
        while (lo <= hi) {
            long long mid = (lo + hi) >> 1;
            if (check(mid))
                lo = mid + 1;
            else
                hi = mid - 1;
        }

        return hi;
    }
};

复杂度分析

• 时间复杂度：O((M+logN∑batteries)logM)
• 空间复杂度：O(M)

个人总结

---

本次周赛，t2刚开始没有想到逆向做，卡了好久，t3看完题目知道是dp，写完大体后发现正向比例，中间跳过的问题不好处理，于是又反向遍历才解决，t4的贪心思路比较难想，其他处理起来倒是不难。总之思维还是不太敏捷，有点呆。。