Skip to content

第 110 场双周赛

比赛链接

Date: 2023-08-05

A 取整购买后的账户余额

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int accountBalanceAfterPurchase(int p) {
        if (p % 10 < 5) {
            p -= p % 10;
        } else {
            p += 10 - p % 10;
        }
        return 100 - p;
    }
};

复杂度分析

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

B 在链表中插入最大公约数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        auto t = head;
        while (t != nullptr && t->next != nullptr) {
            int val = gcd(t->val, t->next->val);
            auto p = new ListNode(val, t->next);
            auto tmp = t->next;
            t->next = p;
            t = tmp;
        }
        return head;
    }
};

复杂度分析

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

C 使循环数组所有元素相等的最少秒数

遍历每一种数字，假设它作为数组最后的元素。拿到这一种数字出现的每一个位置，每个位置与上一个位置之间假设相隔 x 个字符，那么就需要 (x + 1) / 2 秒的时间去覆盖。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        unordered_map<int, vector<int>> mp;
        for (int i = 0; i < nums.size(); i++) {
            mp[nums[i]].push_back(i);
        }
        int res = nums.size();
        for (auto &[k, v] : mp) {
            // 头和尾需要单独处理
            int cur = (v[0] + nums.size() - v.back()) / 2;
            for (int i = 1; i < v.size(); i++) {
                cur = max(cur, (v[i] - v[i - 1]) / 2);
            }
            res = min(res, cur);
        }
        return res;
    }
};

复杂度分析

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

D 使数组和小于等于 x 的最少时间

首先注意到，如果问题有解，那么解一定小于等于 \(n\)。

假设当前算出了时间等于 \(t\) 时，数组的最小和，思考如果将时间降低至 \(t - 1\)，数组的最小和该如何变化。

时间等于 \(t\) 时，我们已经选择了 \(t\) 个数置为 \(0\)，剩余的 \(n - t\) 个数的贡献为 \(nums1 + t \times nums2\)。

对于置为 \(0\) 个 \(t\) 个数字，按照 \(nums2\) 的值从大到小排序。如果我们把时间降低至 \(t - 1\)，则一定是从这 \(t\) 个数中去除一个。假设去除了第 \(i\) 个，那么后面的 \(t - i\) 个数字，每个数字的贡献就少去了 \(nums2\)，将这一部分和记为 \(suf\)。另外，剔出第 \(i\) 个，将增加贡献 \(nums1[i] + (t - 1) \times nums2[i]\)，减小贡献 \(i \times nums2[i]\)。

选择增加贡献最小的去剔除。

注意答案不具有单调性，也就是说若 \(t2\) 不满足，不代表 \(t1(t1 \lt t2)\) 不满足，因此，需要遍历 \([0, n]\) 内所有的时间。

class Solution {
public:
    using PII = pair<int, int>;
    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
        int n = nums1.size();
        vector<pair<int, int>> v;
        for (int i = 0; i < n; i++) {
            v.push_back({nums2[i], nums1[i]});
        }
        sort(v.begin(), v.end(), greater<PII>());
        int res = -1;
        int nums1_sum = 0, nums2_sum = 0;
        for (int t = n; t >= 0; t--) {
            int cur = nums1_sum + nums2_sum * t;
            for (int i = 0; i < v.size(); i++) {
                cur += i * v[i].first;
            }
            if (cur <= x) {
                res = t;
            } 
            if (t >= 1) {
                int suf = 0;
                int min_val = INT_MAX, min_id = -1;
                for (int i = v.size() - 1; i >= 0; i--) {
                    // 将 i 去除的收益
                    int p = v[i].first * (t - 1) + v[i].second;
                    p -= suf;
                    p -= i * v[i].first;
                    if (min_id == -1 || min_val > p) {
                        min_val = p;
                        min_id = i;
                    }
                    suf += v[i].first;
                }
                nums1_sum += v[min_id].second;
                nums2_sum += v[min_id].first;
                v.erase(v.begin() + min_id);
            }
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n^2)\)
  • 空间复杂度：\(O(n)\)
本文访问 次