LeetCode第 71 场双周赛题解

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

题目描述：给你一个四位整数，让你重排这个整数中的数字然后分成两部分，允许有前导\(0\)。问分成的两部分的十进制表示的和的最小值。

思路：根据题意模拟即可、

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

参考代码：

class Solution {
public:
    int minimumSum(int num) {
        string s = to_string(num);
        vectorcnt(10 , 0);
        for(auto c : s) cnt[c - '0'] ++;
        int res = 0, dx = 0 , ct = 0;
        for(int i = 0 ; i < 10 ; ++i){
            if(cnt[i] == 0) continue;
            while(cnt[i]){
                if(ct < 2) res += i * 10;
                else res += i;
                --cnt[i];
                ++ct;
            }
        }
        return res;
    }
};

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

题目描述：给你一个长度为\(n\)的数组\(nums\)，和一个分界数\(x\)，让你将数组中小于\(x\)的数字放在所有\(x\)的左边且不改变其原来的相对顺序，将数组中大于\(x\)的数字放在所有\(x\)的右边且不改变其原来的相对顺序。

思路：根据题意模拟即可。

时间复杂度：\(O(n)\)

参考代码：

class Solution {
public:
    vector pivotArray(vector& nums, int pivot) {
        vectorres , rs;
        int cnt = 0;
        for(auto num : nums){
            if(num < pivot) res.push_back(num);
            else if(num == pivot) ++cnt;
            else rs.push_back(num);
        }
        for(int i = 1 ; i <= cnt ; ++i) res.push_back(pivot);
        for(auto num : rs) res.push_back(num);
        return res;
    }
};

5986. 设置时间的最少代价

题目描述：自己看题目吧

思路：根据题意，将时间先表示成\(m : s\)的形式其中\(s < 60\)，注意可能会存在\(m > 99\)的情况，需要特判。然后表示成\(4\)位，去除前导\(0\)之后计算价值。然后再\(m \neq 0 , s \leq 39\)的情况下表示\(m - 1 : s + 60\)。在算一次价值。二者取最小即可。

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

参考代码：

class Solution {
public:
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        auto solve = [&](vector& target){
            reverse(target.begin() , target.end());
            while(target.back() == 0) target.pop_back();
            reverse(target.begin() , target.end());
            int cur = startAt, res = 0;
            for(auto num : target){
                if(num == cur) res += pushCost;
                else res += pushCost + moveCost;
                cur = num;
            }
            return res;
        };
        int m = targetSeconds / 60 , s = targetSeconds % 60;
        if(m > 99) --m , s += 60;
        vectornums(4 , 0);
        auto process = [&](vector& nums , int m ,int s){
            nums[0] = m / 10;nums[1] = m % 10;
            nums[2] = s / 10; nums[3] = s % 10;
            return ;
        };
        process(nums , m , s);
        int res = solve(nums);
        nums = vector(4 , 0);
        if(m && s <= 39){
            --m;s += 60;
            process(nums , m , s);
            res = min(res , solve(nums));
        }
        return res;
    }
};

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

题目描述：给你一个长度为\(3 * n\)的数组\(nums\)，让你删除其中的\(n\)个，对于删除后的数组，定义其前\(n\)个数字的和为\(sum_{first}\)，后\(n\)个数字的和为\(sum_{second}\)。求\(sum_{first} - sum_{second}\)的最小值。

思路：显然我们要最小化\(sum_{first}\)，最大化\(sum_{second}\)。考虑定义分界点\(n - 1 \leq p < 2 *n\)。区间[0 , p]包含第一部分的所有元素，根据贪心策略需要删除其中\(p - n + 1\)个最大的元素，而区间[p + 1 , 3 * n - 1]包含第二部分的所有元素，根据贪心策略，需要删除其中$2 * n - p - 1 $个最小的元素。考虑如何维护，对于第一部分，使用一个大根堆即可；对于第二部分，我们使用两个multiset a , b分别存储较小的\(2 * n - p - 1\)个元素和较大的\(n\)个元素，若移动分界点对应的元素在a中存在，则直接删除，否则在b中删除该元素，并将a中的最大值加入b中。

时间复杂度：\(O(nlogn)\)

参考代码：

class Solution {
public:
    long long minimumDifference(vector& nums) {
        priority_queueheap;
        long long sum = 0;
        int n = nums.size();
        int m = n / 3;
        for (int i = 0; i < m; ++i) {
            sum += nums[i];
            heap.push(nums[i]);
        }
        multiset a, b;
        for (int i = m; i < n; ++i) {
            if (b.size() < m) {
                sum -= nums[i];
                b.insert(nums[i]);
            }
            else {
                if (*b.begin() >= nums[i]) a.insert(nums[i]);
                else {
                    int dx = *b.begin();
                    a.insert(*b.begin());
                    b.erase(b.begin());
                    b.insert(nums[i]);
                    sum += dx - nums[i];
                }
            }
        }
        long long res = sum;
        for (int i = m; i < 2 * m; ++i) {
            if (a.find(nums[i]) != a.end()) {
                a.erase(a.find(nums[i]));
            }
            else {
                b.erase(b.find(nums[i]));
                int dx = *a.rbegin();
                sum += nums[i] - dx;
                b.insert(dx);
                a.erase(a.find(dx));
            }
            if (nums[i] < heap.top()) {
                sum -= heap.top();
                heap.pop();
                heap.push(nums[i]);
                sum += nums[i];
            }
            res = min(res, sum);
        }
        return res;
    }
};