1711. 大餐计数 力扣(中等) map函数用法

题目描述:

大餐 是指 恰好包含两道不同餐品 的一餐,其美味程度之和等于 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;
    }
};

 

1711. 大餐计数 力扣(中等) map函数用法

上一篇:首次打开Word2016时,总是提示“很抱歉,,此功能看似已中断,并需要修复。请使用Windows控制面板中的“程序与功能”选项修复Microsoft Office”


下一篇:openpyxl:二次封装