1711.大餐计数

发表于： 分类于：
字数： 1188 阅读：≈ 3分钟

🍽 1711.大餐计数

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

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

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

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

思路

基本思想

按照读题之后的第一想法，首先就是求出所有的组合情况，然后依次判断每一个组合的和是不是2的幂并且最终的结果对 10000000007 取余即可，求出所有的组合数可以使用回溯法，判断和是不是2的幂可以使用位运算，所以最终的代码为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    //找到所有的组合，然后判断其和是不是2的幂
    //如何判断和是2的幂:二进制只有一位为1
    int res=0;
    public int countPairs(int[] deliciousness) {
        help(deliciousness,0,0,-1);
        return res;
    }
    private void help(int[] deliciousness,int sum,int level,int index){
        //已经得到一个组合，判断其是不是2的幂
        if(level==2&&(sum&(sum-1))==0){
            ++res;
            return;
        }
        //得到每一个组合
        for(int i=index+1;i<deliciousness.length;++i){
            sum+=deliciousness[i];
            help(deliciousness,sum,level+1,i);
            sum-=deliciousness[i];
        }
    }
}

但是这种代码只能解决一部分案例，数字过多时会超时，主要体现在如果出现[1,3,3,3,3]这种情况时，每一个3都会与1进行配对从而逐步计算出结果，这是耗时的地方，所以需要改进计算组合的情况

为了计算出所有与当前数相加的和是2的幂的所有数，我们需要一个容器记录所有出现的数字，并且为了记录所有数字出现的次数，我们选择使用哈希表

整体的流程就是遍历给定的数组中的所有元素，针对每一个元素去哈希表中找哪个元素与其相加是哪个2的幂，其中2的幂代表0,2,4,8,16...，这种元素有几个，最终的结果数就加几次。需要注意的是，判断是哪个2的幂时需要有一个终点，不然就会陷入死循环

给定一个数组一定会存在一个最大值，数组中任意两个数的和相加肯定不会超过这个最大值的二倍，所以我们可以以这个最大值的二倍当成2的幂的终点，然后判断哈希表中哪些元素可以相加出现哪些2的幂

执行流程

  1. 找到数组中的最大值的二倍当成2的幂的终点，数组中两个数的最大值不可能超过这个数
  2. 针对每一个元素，判断当前元素与哈希表中哪些元素可以相加得到2的幂中的任意一个
  3. 这种元素有几个，结果数就加几，然后与1000000007取余
  4. 返回最终的结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int countPairs(int[] deliciousness) {
        int max=0,res=0;
        int mod=1000000007;

        //找到最大的值
        for(int i=0;i<deliciousness.length;++i){
            max=max<deliciousness[i]?deliciousness[i]:max;
        }
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<deliciousness.length;++i){
            //每次判断当前这个2的幂是否被可以组成
            for(int sum=1;sum<=max*2;sum<<=1){
                //有几个数能与当前的数相加得到一个2的幂
                int count=map.getOrDefault(sum-deliciousness[i],0);
                res=(res+count)%mod;
            }
            map.put(deliciousness[i],map.getOrDefault(deliciousness[i],0)+1);
        }
        return res;
    }
}

核心就是在统计完每个数都能组成哪些2的幂之后，然后将其加入到哈希表中

总结

从直观的角度解决问题之后，然后发现会有重复的元素会被使用，所以使用哈希表来保存遍历到的数，便于后期直接使用，并且一旦组成了一个哈希表之后，后期的元素可以直接使用sum-deliciousness[i]得到当前有几个数可以与deliciousness[i]组成2的幂，并不用一遍一遍的去统计，这样就大大减少了时间