leetcode71双周赛

竞赛链接

T1: 5984. 拆分数位后四位数字的最小和

---

思路

贪心

Code

class Solution {
public:
    int minimumSum(int num) {
        string s=to_string(num);     
        vector<int>a;
        for(int i=0;i<4;++i)
            a.emplace_back(s[i]-'0');
        sort(a.begin(),a.end());
        if(a[0]==0&&a[1]==0)
            return a[2]+a[3];
        if(a[0]==0){
            return a[1]*10+a[2]+a[3];
        }
        return a[0]*10+a[1]*10+a[2]+a[3];
    }
};

复杂度分析

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

T2: 5985. 根据给定数字划分数组

---

思路

模拟

Code

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int>a,b,c;
        for(auto& i:nums){
            if(i>pivot)
                c.emplace_back(i);
            else if(i==pivot)
                b.emplace_back(i);
            else
                a.emplace_back(i);
        }
        vector<int>ans;
        for(auto& i:a)
            ans.emplace_back(i);
        for(auto& i:b)
            ans.emplace_back(i);
        for(auto& i:c)
            ans.emplace_back(i);
        return ans;
    }
};

复杂度分析

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

T3: 5986. 设置时间的最少代价

---

思路

枚举每种可能，取最小的

Code

class Solution {
public:
    int dfs(int st, int mc, int pc,string s){
        int ans=0;
        for(auto& i:s){
            int now=i-'0';
            if(st==now)
                ans+=pc;
            else
                st=now,ans+=mc+pc;
        }
        return ans;
    }
    int minCostSetTime(int st, int mc, int pc, int ts) {
        int ans=INT_MAX;
        string s1=to_string(ts);
        string s3;
        if(ts%60==0){
           int now=ts;
           now-=60;
           s3=to_string(now/60)+"60"; 
           ans=min(ans,dfs(st,mc,pc,s3));
        }

        if(ts>120){
           int minn=ts/60;
           int cc=ts%60;
           if(cc<=39)
              cc+=60,minn--;
            string ss=to_string(minn)+to_string(cc);
            ans=min(ans,dfs(st,mc,pc,ss));
            cout<<ss<<" "<<ans<<endl;
        }

        int minues=ts/60,se=ts%60;

        string s2;
        if(minues>99){
            minues--;
            se+=60;
        }
        if(se!=0){
            if(se>=10)
                s2=to_string(minues)+to_string(se);
            else
                s2=to_string(minues)+"0"+to_string(se);
        }
        else
            s2=to_string(minues)+"00";

        if(ts<=60){ 
            ans=min(ans,dfs(st,mc,pc,s1));
        }
        else if(ts>=60&&ts<=99){
            ans=min(ans,dfs(st,mc,pc,s1));
            ans=min(ans,dfs(st,mc,pc,s2));    
        }
        else if(ts>99){
            ans=min(ans,dfs(st,mc,pc,s2));    
            cout<<s2<<" "<<dfs(st,mc,pc,s2);
        }
        return ans;
    }
};

复杂度分析

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

T4: 5987. 删除元素后和的最小差值

---

思路

前缀最小和+后缀最大和+堆

将 nums 拆分成两部分，左半部分的最小和（前缀最小和）减右半部分的最大和（后缀最大和）即为两部分和的最小差值，枚举拆分位置（保证左右两部分至少有 nn 个元素），所有差值的最小值就是答案。

因此我们需要计算出 nums 的前缀最小和，即前 i 个元素中的最小的 n 个元素之和，以及后缀最大和，即后 i 个元素中的最大的 n 个元素之和。

计算前缀最小和时，可以维护一个包含 n 个元素的最大堆，我们不断向右遍历 nums 中的元素 v，计算前缀最小和，若 v 比堆顶元素小，则弹出堆顶元素，并将 v 入堆。

计算后缀最大和，则需要维护一个包含 n 个元素的最小堆，我们不断向左遍历 nums 中的元素 v，计算后缀最大和，若 v 比堆顶元素大，则弹出堆顶元素，并将 v 入堆。

代码实现时，可以先计算出后缀最大和，然后在计算前缀最小和的同时计算出答案。

Code

class Solution {
public:
    long long minimumDifference(vector<int> &nums) {
        int m = nums.size(), n = m / 3;
        priority_queue<int, vector<int>, greater<int>> minPQ;
        long sum = 0L;
        for (int i = m - n; i < m; ++i) {
            minPQ.push(nums[i]);
            sum += nums[i];
        }
        vector<long> sufMax(m - n + 1); // 后缀最大和
        sufMax[m - n] = sum;
        for (int i = m - n - 1; i >= n; --i) {
            minPQ.push(nums[i]);
            sum += nums[i] - minPQ.top();
            minPQ.pop();
            sufMax[i] = sum;
        }

        priority_queue<int> maxPQ;
        long preMin = 0L; // 前缀最小和
        for (int i = 0; i < n; ++i) {
            maxPQ.push(nums[i]);
            preMin += nums[i];
        }
        long ans = preMin - sufMax[n];
        for (int i = n; i < m - n; ++i) {
            maxPQ.push(nums[i]);
            preMin += nums[i] - maxPQ.top();
            maxPQ.pop();
            ans = min(ans, preMin - sufMax[i + 1]);  //取前i个元素的最小的n个数之和  减去  后m-i个数的最大的n个数之和
        }
        return ans;
    }
};

复杂度分析

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

个人总结

---

本次双周赛，t1、t2水题飘过,t3以为很麻烦，仔细读题后发现模拟就行了，于是开始了漫长的debug阶段，在连wa三次后终于ac了，接着t4就被罚坐了😓