文章目錄

• • • 本題分析
    • 題目鏈接

本題分析

大餐 是指 恰好包含兩道不同餐品 的一餐，其美味程度之和等于 2 的冪。
注意，只要餐品下標(biāo)不同，就可以認(rèn)為是不同的餐品，即便它們的美味程度相同。

示例

輸入：deliciousness = [1,3,5,7,9] 輸出：4 解釋：大餐的美味程度組合為 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。 它們各自的美味程度之和分別為 4 、8 、8 和 16 ，都是 2 的冪。

題意重述：給定一個(gè)數(shù)組a[ ]，求$$\begin{gathered} a_i+a_j=2^n(n=0,1,...,21. \\ i=j) \end{gathered}$$的種數(shù)

枚舉數(shù)組中的每個(gè)元素$a_k$，對(duì)于數(shù)組中$a_0?a_{k?1}$這些元素(暫時(shí)令為t)，查找有多少個(gè)t滿足$t+a_k=2^n(n=0,1,...,21)$。

使用哈希表unordered_map，遍歷完一個(gè)x: a[ ] ,使其在哈希表中的值++。

ac代碼

class Solution { public:int countPairs(vector<int>& d) {int res=0,mod=1e9+7;unordered_map<int,int> hash;//哈希表for(auto x:d){for(int i=0;i<=21;i++){int t =(1<<i)-x; //位運(yùn)算優(yōu)化2的i次方if(hash.count(t))res= (res+hash[t]) % mod; //勿忘取模}hash[x]++; //d數(shù)組中遍歷到的每個(gè)元素都要在hash表中記錄。}return res;} };

題目鏈接

Leetcode1711. 大餐計(jì)數(shù)

總結(jié)

以上是生活随笔為你收集整理的Leetcode1711. 大餐计数[C++题解]：哈希表和枚举的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。