从数量最多的堆取走礼物

题目链接

从数量最多的堆取走礼物

解题思路

直接按照流程模拟即可，将数组 gifts 的元素放入优先队列中，然后每次从中选出最大值 maxGift，再将 sqrt(maxGift) 放回队列，重复 k 次，计算队列剩余的值总和。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        // 这里求 gifts 总和要注意累加初始值定义为 0ll（long long 类型），否则 int 可能溢出
        // 当然也可以不求初始总数量，而在循环结束后直接统计剩余的数量
        long long sum = accumulate(gifts.begin(), gifts.end(), 0ll);
        priority_queue<int> Q(gifts.begin(), gifts.end());
        long long res = 0;
        for (int i = 0; !Q.empty() && i < k; ++i) {
            int maxGift = Q.top();
            Q.pop();
            int maxSqrt = (int)sqrt(maxGift);
            res += maxGift - maxSqrt;
            Q.emplace(maxSqrt);
        }
        return sum - res;
    }
};

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

题目链接

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

解题思路

题目要求解多个区间的元音字符串个数，可以考虑使用前缀和的技巧：即指定一个前缀和数组 preSum，preSum[i] 表示区间 [0, i)（左闭右开）上元音字符串的个数，那么任意区间 [l, r] 的元音字符串个数为 preSum[r + 1] - preSum[l].

而求前缀和就比较简单了，从 i = 0 开始循环，如果字符串 words[i] 为元音字符串，则 preSum[i + 1] = preSum[i] + 1，否则 preSum[i + 1] = preSum[i].

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        unordered_set<char> alphaSet = { 'a','e','i','o','u' };
        int sum = 0, n = words.size();
        vector<int> preSum(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            string str = words[i];
            if (alphaSet.count(str.front()) && alphaSet.count(str.back())) {
                preSum[i + 1] = preSum[i] + 1;
            }
            else {
                preSum[i + 1] = preSum[i];
            }
        }
        vector<int> res;
        for (int i = 0; i < queries.size(); ++i) {
            int l = queries[i][0], r = queries[i][1];
            int cnt = preSum[r + 1] - preSum[l];
            res.emplace_back(cnt);
        }
        return res;
    }
};

重排水果

题目链接

重排水果

解题思路

由于交换两水果的成本为 min(basket1[i], basket2[i])，很容易想到的交换方法忽视两果篮中共有的水果，挨个让 basket1 中成本最大的水果和 basket2 中成本最小的水果进行交换。但事实上这样忽视了一种情况：假设 basket1 中有水果 …basket1[i]…basket1[j]…，basket2 中有水果 …basket2[i]…，如果 2 * basket1[j] < min(basket1[i], basket2[i])，那么如果以 basket1[j] 为中介，分别与 basket2[i] 和 basket1[i] 交换，所花的代价更小，因此交换成本为 min(basket1[i], basket2[i], 2 * minVal).

具体代码实现部分，可以用哈希表记录 basket1 和 basket2 中各水果成本和相对数量（basket1 相对数量为正，basket2 相对数量为负）。统计完成后，分别将相对数量大于零的和相对数量小于零的成本值存放在两个数组中，分别升序排序和降序排序，按照上述交换方案计算总交换成本。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> fruitCnt;
        for (int i = 0; i < basket1.size(); ++i) {
            ++fruitCnt[basket1[i]];
        }
        for (int i = 0; i < basket2.size(); ++i) {
            --fruitCnt[basket2[i]];
        }
        int minVal = INT32_MAX;
        vector<int> fruits1, fruits2;
        for (const auto& fc : fruitCnt) {
            int f = fc.first, c = fc.second;
            if (abs(c) % 2 == 1) return -1; // 若相对数量为奇数，则必定无法相等
            minVal = min(minVal, f);
            if (c > 0) { // 一次交换使相对数量的绝对值减小2
                for (int i = abs(c) / 2; i > 0; --i) {
                    fruits1.emplace_back(f);
                }
            }
            else if (c < 0) {
                for (int i = abs(c) / 2; i > 0; --i) {
                    fruits2.emplace_back(f);
                }
            }
        }
        if (fruits1.size() != fruits2.size()) return -1;
        long long res = 0;
        sort(fruits1.begin(), fruits1.end(), less<int>());
        sort(fruits2.begin(), fruits2.end(), greater<int>());
        for (int i = 0; i < fruits1.size(); ++i) {
            res += min(min(fruits1[i], fruits2[i]), 2 * minVal);
        }
        return res;
    }
};