大餐计数 | 阿犇

Trace

7.7 每日一题

传送门：https://leetcode-cn.com/problems/count-good-meals/

Problem

大餐是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。

你可以搭配任意两道餐品做一顿大餐。

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i 道餐品的美味程度，返回你可以用数组中的餐品做出的不同大餐的数量。结果需要对 1e9 + 7 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

示例 1：

输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。

示例 2：

1
2
3

输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。

提示：

1 2	1 <= deliciousness.length <= 1e5 0 <= deliciousness[i] <= 2的20次方

哈希表

朴素做法，两层循环枚举两个点，判断和是否为2的幂。

优化：判断是否为2的幂，有五种方法。

方法一

求出第一个大于等于$x$的2的幂，然后判断是否等于。

bool check(int x){
	int k=1;
	while(k<x){
	k*=2;
	}
	return k==x;
}

时间复杂度$O(logx)$。

方法二

思路同方法一，但求第一个大于等于$x$的2的幂时通过位运算实现。

举个栗子，$x=65$，$x-1=64$，二进制表示为$10000000$

$x|=x>>1$，$x=10000000|01000000=11000000$

$x|=x>>2$，$x=11000000|00110000=11110000$

$x|=x>>4$，$x=11110000|00001111=11111111$

之后$x$无改变，二进制表示每一位均变为$1$，$+1$为$128$。

bool check(int x){
	int t=x;
	x-=1;
	x|=x>>1;
	x|=x>>2;
	x|=x>>4;
	x|=x>>8;
	x|=x>>16;
	x=x<0?1:x+1;
	return x==t;
}

时间复杂度$O(1)$。

方法三

为$0$时需要特判

bool check(int x){
	if(x==0) return false;
	return (x&(x-1))==0;
}

时间复杂度$O(1)$。

方法四

为$0$时需要特判

$ps$：$’==’$优先级比’&’高，所以要加$’()’$，不然结果会出错。

bool check(int x){
	if(x==0) return false;
	return (x&-x)==x;
}

时间复杂度$O(1)$。

方法五

除此之外此题可以先打表，以便判断是否为2的幂，又$x$最大2的21次幂，所以打到21就好。

unordered_map<int,bool> ump1; 
int tmp=1;
for(int i=0;i<=21;i++){
    ump1[tmp]=true;
    tmp*=2;
}

时间复杂度$O(1)$。

但枚举的时间复杂度为$O(n^2)$，还是会$TLE$，这里只是趁机总结了几种判断一个数是否为2的幂次的方法。

优化：对第二层枚举，可以考虑枚举2的幂，然后判断差是否在数组中，此处可以通过哈希表实现。边插入边统计，保证不会重复计算。

class Solution {
public:
    int countPairs(vector<int>& d) {
        // 哈希表
        // 两个数之和最大为2的21次方，先打个表，存2的0,1,2...,21次幂，记2的幂次共有c个，c=22
        const int mod = 1e9+7;
        long long cnt=0;
        unordered_map<int,bool> ump1; 
        int tmp=1;
        for(int i=0;i<=21;i++){
            ump1[tmp]=true;
            tmp*=2;
        }
        unordered_map<int,int> ump2; // d中元素的数量
        // 边插入边统计，保证不会重复计算
        for(auto i:d){
            for(auto j:ump1){                
                if(ump2.count(j.first-i)){
                    cnt=(cnt+ump2[j.first-i])%mod;
                }
            }
            ump2[i]++;
        }
        
        return cnt;
    }
};

时间复杂度$O(n*logC)$，$C$为元素值上限。