青岛市城阳区建设局网站,深圳机票网站建设,怎么建网站做淘宝客,wordpress改变文章字体大小文章目录1. 题目2. 解题1. 题目
大餐 是指 恰好包含两道不同餐品 的一餐#xff0c;其美味程度之和等于 2 的幂。
你可以搭配 任意 两道餐品做一顿大餐。
给你一个整数数组 deliciousness #xff0c;其中 deliciousness[i] 是第 i 道餐品的美…
文章目录1. 题目2. 解题1. 题目
大餐 是指 恰好包含两道不同餐品 的一餐其美味程度之和等于 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^20https://leetcode-cn.com/problems/count-good-meals/
2. 解题
class Solution {
public:int countPairs(vectorint deliciousness) {mapint,long long m;for(auto d : deliciousness)m[d];//计数long long ans 0, mod 1e97;for(int i 0; i 22; i){ // 枚举 2的幂int target 1 i;for(auto it m.begin(); it ! m.end() it-first target/2; it){int d1 target-it-first;//另一份餐的美味程度if(m.find(d1) m.end())//不存在continue;if(it-first ! d1)//不相等ans (ansit-second*m[d1])%mod;else//相等 Cn2ans (ansm[d1]*(m[d1]-1)/2)%mod;}}return ans;}
};684 ms 58 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
