题目描述:
大餐 是指 恰好包含两道不同餐品 的一餐,其美味程度之和等于 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 的幂。
题源:https://leetcode-cn.com/problems/count-good-meals/
注意点:
map容器的find函数比键值查找快!!!!
代码:
class Solution { public: int countPairs(vector<int>& deliciousness) { long long f[25]; f[0]=1; for(int i=1;i<=21;i++) f[i]=f[i-1]*2; map<int, long long> mp; for(int i=0;i<deliciousness.size();i++) mp[deliciousness[i]]++; long long res=0; long long m=1e9+7; for(auto i : mp) { // 速度相对较快,花费160ms int cur=i.first; long long num=i.second; for(int j=21;j>=0;j--) if (f[j]-cur>=cur) { if (f[j]-cur==cur) { res+=num*(num-1)/2; res%=m; } else if(mp.find(f[j]-cur)!=mp.end()) // if (mp[f[j]-cur]>0) //这样也会超时,只有前面写法可以,终于找到了一直tle的原因 { res+=num * mp[f[j]-cur]; res%=m; } } else break; /* // 下面这种写法也不超时,但会比上面慢,花费232ms for(int j=21;j>=0;j--) if (f[j]-i.first>=i.first) { if (f[j]-i.first==i.first) { res+=i.second*(i.second-1)/2; res%=m; } else if(mp.find(f[j]-i.first)!=mp.end()) // if (mp[f[j]-cur]>0) //这样也会超时,只有前面写法可以 { res+=i.second * mp[f[j]-i.first]; res%=m; } } else break; */ } return res; } };