文章目錄

• • 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^20

https://leetcode-cn.com/problems/count-good-meals/

2. 解題

class Solution { public:int countPairs(vector<int>& deliciousness) {map<int,long long> m;for(auto d : deliciousness)m[d]++;//計數long long ans = 0, mod = 1e9+7;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 = (ans+it->second*m[d1])%mod;else//相等 Cn2ans = (ans+m[d1]*(m[d1]-1)/2)%mod;}}return ans;} };

684 ms 58 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1711. 大餐计数（map计数 + 二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。