第 331 场周赛

Date: 2023-02-05

A 从数量最多的堆取走礼物

堆模拟题，Python 写法略胜一筹

C++Python

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> q;
        for (auto x : gifts) q.push(x);
        long long res = 0;
        while (k--) {
            int x = q.top(); q.pop();
            q.push(int(sqrt(x)));
        }
        while (q.size()) {
            int x = q.top(); q.pop();
            res += x;
        }
        return res;
    }
};

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        h = sorted([-x for x in gifts])
        while k > 0:
            x = heappop(h)
            x = -x
            heappush(h, -int(x ** 0.5))
            k -= 1
        return -sum(h)

复杂度分析

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

B 统计范围内的元音字符串数

前缀和模拟题

C++Python

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int n = words.size();
        vector<int> s(n + 1);
        auto check = [&](char c) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                return true;
            }
            return false;
        };
        for (int i = 1; i <= n; i++) {
            if (check(words[i - 1][0]) && check(words[i - 1].back())) {
                s[i] = s[i - 1] + 1;
            } else {
                s[i] = s[i - 1];
            }
        }
        vector<int> res;
        for (auto &v : queries) {
            res.push_back(s[v[1] + 1] - s[v[0]]);
        }
        return res;
    }
};

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        presum = [0]
        for s in words:
            presum.append(presum[-1])
            if s[0] in "aeiou" and s[-1] in "aeiou":
                presum[-1] += 1

        res = []
        for l, r in queries:
            res.append(presum[r + 1] - presum[l])
        return res

复杂度分析

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

C 打家劫舍 IV

枚举小偷的最大偷窃能力 \(m\)，然后大于 \(m\) 的不能考虑。

设 \(d[i][0], d[i][1]\) 分别为第 \(i\) 个不偷或者偷的情况下，前 \(i\) 个里面最多可以偷几次。然后转移方程：

若 \(\textit{nums}[i] > m\)，则: 1. \(d[i][0] = \max\{d[i - 1][0], d[i - 1][1]\}\) 2. \(d[i][1] = 0\)

若 \(\textit{nums}[i] <= m\), 则: 1. \(d[i][0] = \max\{d[i - 1][0], d[i - 1][1]\}\) 2. \(d[i][1] = d[i - 1][0] + 1\)

不开数组也是可以的（比赛时我把数组开到二分里面 T 了，亏死），两个变量转移即可。

C++

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int l = 0, r = 1E9;
        int n = nums.size();
        auto check = [&](int m) {
            int x = 0, y = 0;
            for (int i = 1; i <= n; i++) {
                int nx = max(x, y);
                int ny = nums[i - 1] > m ? 0 : x + 1;
                x = nx; 
                y = ny;
            }
            return max(x, y) >= k;
        };
        while (l < r) {
            int m = (l + r) >> 1;
            if (check(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};

复杂度分析

时间复杂度：\(O(n\log C)\)，其中 \(C\) 是数据范围，本题中为 \(10^9\)
空间复杂度：\(O(1)\)。

D 重排水果

首先用哈希表记录两个数组中每种数字出现的次数，然后通过比对同种数字出现次数的差值可以判断数字交换的方向以及是否有解。如果某个数字出现次数的差值是奇数则无解。

知道了每个数组中需要交换的数字之后，将它们分别排序。很直接的想法是一头一尾分别配对交换可以使得答案较小。但容易忽略掉的做法是，我们可以找到两个数组中的最小值，使用这个最小值通过两次调包来交换两个数字。

比如现在要交换的数字是 \(x\) 和 \(y\)，分别在 \(\textit{basket}_1\) 和 \(\textit{basket}_2\) 中。那么假设全局最小值为 \(z\)，出现在 \(\textit{basket}_1\) 中，那么我们先交换 \(z\) 和 \(y\)，然后再交换 \(z\) 和 \(x\)。这样 \(z\) 最终又回到了 \(\textit{basket}_1\) 中。（借群友一句话，四两拨千斤）

两种不同的做法代价分别是 \(\min(x, y)\) 和 \(2\times z\)，取最小即可。

C++

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> diff;
        for (auto x : basket1) {
            diff[x]++;
        }
        for (auto x : basket2) {
            diff[x]--;
        }
        for (auto &[x, y] : diff) {
            if (y & 1) {
                return -1;
            }
        }
        vector<int> a, b;
        for (auto x : basket1) {
            if (diff[x] > 0) {
                a.push_back(x);
                diff[x] -= 2;
            }
        }
        for (auto x : basket2) {
            if (diff[x] < 0) {
                b.push_back(x);
                diff[x] += 2;
            }
        }

        sort(a.begin(), a.end());
        sort(b.begin(), b.end(), greater<int>());
        int z = min(*min_element(basket1.begin(), basket1.end()), *min_element(basket2.begin(), basket2.end()));
        long long res = 0;
        for (int i = 0; i < a.size(); i++) {
            res += min(min(a[i], b[i]), 2 * z);
        }
        return res;
    }
};

复杂度分析

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

ID: 2335 TITLE: 装满杯子需要的最短总时长 TAG: C++, Java, C#, C, JavaScript, 数组, 贪心, 排序

本文访问次