class Solution {
public:
int countPairs(vector<int>& deliciousness) {
}
};
1711. 大餐计数
大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
你可以搭配 任意 两道餐品做一顿大餐。
给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 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 <= 1050 <= deliciousness[i] <= 220原站题解
cpp 解法, 执行用时: 448 ms, 内存消耗: 70.6 MB, 提交时间: 2023-09-06 23:42:41
class Solution {
public:
static constexpr int MOD = 1'000'000'007;
int countPairs(vector<int>& deliciousness) {
int maxVal = *max_element(deliciousness.begin(), deliciousness.end());
int maxSum = maxVal * 2;
int pairs = 0;
unordered_map<int, int> mp;
int n = deliciousness.size();
for (auto& val : deliciousness) {
for (int sum = 1; sum <= maxSum; sum <<= 1) {
int count = mp.count(sum - val) ? mp[sum - val] : 0;
pairs = (pairs + count) % MOD;
}
mp[val]++;
}
return pairs;
}
};
javascript 解法, 执行用时: 224 ms, 内存消耗: 54.8 MB, 提交时间: 2023-09-06 23:42:25
/**
* @param {number[]} deliciousness
* @return {number}
*/
var countPairs = function(deliciousness) {
const MOD = 1000000007;
let maxVal = 0;
for (const val of deliciousness) {
maxVal = Math.max(maxVal, val);
}
const maxSum = maxVal * 2;
let pairs = 0;
const map = new Map();
const n = deliciousness.length;
for (let i = 0; i < n; i++) {
const val = deliciousness[i];
for (let sum = 1; sum <= maxSum; sum <<= 1) {
const count = map.get(sum - val) || 0;
pairs = (pairs + count) % MOD;
}
map.set(val, (map.get(val) || 0) + 1);
}
return pairs;
};
golang 解法, 执行用时: 184 ms, 内存消耗: 8.7 MB, 提交时间: 2023-09-06 23:42:11
func countPairs(deliciousness []int) (ans int) {
maxVal := deliciousness[0]
for _, val := range deliciousness[1:] {
if val > maxVal {
maxVal = val
}
}
maxSum := maxVal * 2
cnt := map[int]int{}
for _, val := range deliciousness {
for sum := 1; sum <= maxSum; sum <<= 1 {
ans += cnt[sum-val]
}
cnt[val]++
}
return ans % (1e9 + 7)
}
java 解法, 执行用时: 145 ms, 内存消耗: 52.9 MB, 提交时间: 2023-09-06 23:41:59
class Solution {
public int countPairs(int[] deliciousness) {
final int MOD = 1000000007;
int maxVal = 0;
for (int val : deliciousness) {
maxVal = Math.max(maxVal, val);
}
int maxSum = maxVal * 2;
int pairs = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int n = deliciousness.length;
for (int i = 0; i < n; i++) {
int val = deliciousness[i];
for (int sum = 1; sum <= maxSum; sum <<= 1) {
int count = map.getOrDefault(sum - val, 0);
pairs = (pairs + count) % MOD;
}
map.put(val, map.getOrDefault(val, 0) + 1);
}
return pairs;
}
}
python3 解法, 执行用时: 140 ms, 内存消耗: 23.5 MB, 提交时间: 2023-09-06 23:41:18
class Solution:
def countPairs(self, deliciousness: List[int]) -> int:
MOD = 1000000007
count = Counter(deliciousness)
res = 0
# 由于每个数只遍历了最接近自己的2的次幂的组合，所以不可能重复;比如说1和3构成4，只在3的时候计算；3和5构成8只在5的时候计算。
for i in count:
if i == 0:
continue
# i的下一个2的幂次
target = self.nextPower(i)
# 如果i能和任意的count中的key够成这个幂次
res += count[i] * count[target - i]
# 如果i自身是一个2的幂次
if i == target:
res += count[i] * (count[i] - 1) // 2
return res % MOD
def nextPower(self, x: int):
x -= 1
x |= x >> 1
x |= x >> 2
x |= x >> 4
x |= x >> 8
x |= x >> 16
return x + 1