VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 1711. 大餐计数

Posted on Edited on In , ,

摘要：
TwoSum升级版。

题目

大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 $2$ 的幂。

你可以搭配 任意 两道餐品做一顿大餐。

给你一个整数数组 $deliciousness$ ，其中 $deliciousness[i]$ 是第 $i$​​​​​​​​​​​​​​ 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 $10^9 + 7$ 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

示例 1：

输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。

示例 2：

输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。

提示：

  • $1 <= deliciousness.length <= 10^5$
  • $0 <= deliciousness[i] <= 2^{20}$

哈希表

对于数组中的每个元素，从 $2^0$ 到 $2^{21}$ 依次计算目标值，将目标值放入哈希表计数加一。
那么，对于每一个元素需要先从哈希表里面找自己是不是之前某数的目标值，如果是，则结果加上目标值的计数。
值得注意的是，$0 <= deliciousness[i] <= 2^{20}$，所以当数组存在多个最大范围的值时，目标值最高可取到 $2^20 + 2^{20}$ 也就是 $2^{21}$.

我们可以先求出原数组中的最大值，那么对于每个数循环 $[2^0,2^{21}]$ 时，目标值可能的范围在 $0 <= deliciousness[i] <= 2^{20}$，超出可以不考虑，因为数组元素在这个范围，不可能遇到超出范围的。

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
38
39
40
41
42
43
44
45
46
47
/*
 * 2021-7-7 13:15:21
 * author: etoa
 */
static const auto shutdown = [](){
    cin.tie(nullptr)->sync_with_stdio(false);
    return nullptr;
}();

class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    inline long long ksm(long long a, int b) {
        long long res = 1;
        for (; b; a = a * a, b >>= 1) {
            if (b & 1) res = res * a;
        }
        return res;
    }

    int countPairs(vector<int>& d) {
        int n = d.size();
        vector<long long> target;
        for (int i = 0; i <= 21; i++) {
            target.push_back(ksm(2, i));
        }   
        int mx = -1;
        for (int i = 0; i < n; i++) 
            mx = max(mx, d[i]);
        unordered_map<long long, int> hash; // expected - cnt
        long long res = 0;
        for (int i = 0; i < n; i++) {
            if (hash.count(d[i])) {
                res += hash[d[i]];
            }
            //cout << d[i] << "---" << endl;
            for (int j = 0; j <= 21; j++) {
                if (target[j] - d[i] > mx) break;
                if (target[j] - d[i] >= 0) {
                    hash[target[j] - d[i]]++;
                    //cout << target[j] - d[i] << '-' << hash[target[j] - d[i]] << endl;
                }
            }
        } 
        return res % MOD;
    }
};
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
/*
 * 优化：快速幂可以用位运算代替；
 * 求数组最值可以使用max_element;
 */
static const auto shutdown = [](){
    cin.tie(nullptr)->sync_with_stdio(false);
    return nullptr;
}();

class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    int countPairs(vector<int>& d) {
        int n = d.size();
        vector<long long> target;
        for (int i = 0; i <= 21; i++) {
            target.push_back(1 << i);
        }   
        int mx = *max_element(d.begin(), d.end());
        unordered_map<long long, int> hash; // expected - cnt
        long long res = 0;
        for (int i = 0; i < n; i++) {
            if (hash.count(d[i])) {
                res += hash[d[i]];
            }
            //cout << d[i] << "---" << endl;
            for (int j = 0; j <= 21; j++) {
                if (target[j] - d[i] > mx) break;
                if (target[j] - d[i] >= 0) {
                    hash[target[j] - d[i]]++;
                    //cout << target[j] - d[i] << '-' << hash[target[j] - d[i]] << endl;
                }
            }
        } 
        return res % MOD;
    }
};

原题链接： LeetCode 1711. 大餐计数