碎碎念

由于各种事情比赛开始后十分钟才开始做题,状态也心不在焉
由于最后急着刷排名,心态很急,思路没有整理就上手敲代码
结果只AC了前三题,最后一题实在没心态了


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

解题思路

很明显的贪心,对于四位数,用一个长度为4的数组a保存各位的数值
题目要求构成的两个两位数之和最小;
首先对数组a从小到大排序,
两位小的一定分别是两个数的十位,而两位大的一定分别是两个数的个位

代码

class Solution {
public:
    int a[4];
    int minimumSum(int num) {
        a[0] = num / 1000;
        a[1] = num / 100 % 10;
        a[2] = num % 100 / 10;
        a[3] = num % 10;
        
        sort(a, a + 4);
        
        return (a[0] * 10 + a[2]) + (a[1] * 10 + a[3]);
    }
};

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

解题思路

额外开了两个vector,扫描一遍,分别将小于p的数放入a
对等于p的计数
对大于p的数放入b
最后将所有元素放入a;

代码

class Solution {
public:
    vector<int>a, b;
    int cnt = 0;
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] < pivot)  a.push_back(nums[i]);
            else if (pivot == nums[i]) cnt++;
            else b.push_back(nums[i]);
        }

        for (int i = 0; i < cnt; i++) a.push_back(pivot);
        for (auto& x : b)   a.push_back(x);
        return a;
    }
};

5986. 设置时间的最少代价

解题思路

分钟数和秒数的范围都是0~99;
我们可以对分钟数从0~99枚举,秒数自然可以由公式int j = targetSeconds - i * 60得出
如果算出来的秒数不在正常范围内,则进行下一次循环,否则去除前导0后开始比大小
而反过来对秒数从0~99枚举,并不能算出分钟数

TIPS:对于此题,我们要尽量避免的前导0的计算,因为前导0只会额外增加cost

代码

class Solution {
int ans = 1e9;
int c[4];
public:
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        for (int i = 0; i <= 99; i++) {
            int j = targetSeconds - i * 60;
            if (j < 0 || j > 99)    continue;
            c[0] = i / 10; c[1] = i % 10;
            c[2] = j / 10; c[3] = j % 10;

            bool flag = false;
            int res = 0, d = startAt;
            for (int k = 0; k < 4; k++) {
                if (c[k])  flag = true;  // 只有不是前导0时,才开始操作
                if (flag) {
                    if (c[k] != d)
                        res += moveCost, d = c[k];
                    res += pushCost;  
                }
            }
            ans = min(ans, res);
        }
        return ans;
    }
};

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

题目描述

avatar

解题思路

可以参考这个题解
简而言之,由于我们最后只需要2 * n 个元素,并分为两半,
题目要求前一半减去后一半的差值最小 => 要求前一半最小,后一半最大
因此我们可以用一个小根堆求出前缀最小和,用一个大根堆求出后缀最大和

当小根堆/大根堆的数量到达了n之后,
对于下一个num[i]可以先加入堆,然后弹出堆顶,并更新某个区间的前缀最小和/后缀最大和

代码

class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        int m = nums.size(), n = m / 3;
        priority_queue<int, vector<int>, greater<int>> minQ;
        long long sum = 0;

        for (int i = m - n; i < m; i++) {
            minQ.push(nums[i]);
            sum += nums[i];
        }

        vector<long long> sufMax(m - n + 1);
        sufMax[m - n] = sum;
        for (int i = m - n - 1; i >= n; i--) {
            minQ.push(nums[i]);
            sum += nums[i] - minQ.top();
            minQ.pop();
            sufMax[i] = sum;  // 更新后缀最大值
        }

        priority_queue<int> maxQ;
        long long preMin = 0;
        for (int i = 0; i < n; i++) {
            maxQ.push(nums[i]);
            preMin += nums[i];
        }

        long long ans = preMin - sufMax[n]; 
        for (int i = n; i < m - n; i++) {
            maxQ.push(nums[i]);  // 先加入堆
            preMin += nums[i] - maxQ.top();  
            maxQ.pop();  // 将最大值弹出
            ans = min(ans, preMin - sufMax[i + 1]);
        }
        return ans;
    }
};
上一篇 下一篇