[LeetCode] 1711. Count Good Meals

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i??????th???????? item of food, return the number of different good meals you can make from this list modulo 109 + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Example 1:

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

Constraints:

  • 1 <= deliciousness.length <= 105
  • 0 <= deliciousness[i] <= 220

大餐计数。

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

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-good-meals
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题是一道 two sum 类型题目的延伸。题目给的是一些餐品的美味程度 deliciousness[i],问的是有多少种组合可以使得 deliciousness[a] + deliciousness[b] 的结果是 2 的幂。精简一下题意,就是问你数组里面有多少种组合可以满足A + B = C。由于结果比较大,需要对结果做 MOD 操作。

这里我们需要一个 hashmap 和一个 hashset。hashset 记录所有 2 的幂的结果,也就是记录所有的 C;hashmap里面存的是所有 unique 的美味程度和他的出现次数。扫描 input 数组,对于当前的美味程度 A,我们去hashmap里找是否存在另一个美味程度 B,满足A + B = C,如果存在,则看看 B 出现了几次,加入结果集。每次加法结束之后就需要对结果取模,这样才不会越界。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int countPairs(int[] deliciousness) {
 3         int MOD = (int) Math.pow(10, 9) + 7;
 4         int res = 0;
 5         HashSet<Integer> set = new HashSet<>();
 6         int len = deliciousness.length;
 7         for (int i = 0; i < 22; i++) {
 8             set.add((int) Math.pow(2, i));
 9         }
10 
11         HashMap<Integer, Integer> map = new HashMap<>();
12         for (int i = 0; i < len; i++) {
13             for (int key : set) {
14                 if (map.containsKey(key - deliciousness[i])) {
15                     res += map.get(key - deliciousness[i]);
16                     res %= MOD;
17                 }
18             }
19             map.put(deliciousness[i], map.getOrDefault(deliciousness[i], 0) + 1);
20         }
21         return res;
22     }
23 }

 

two sum题目总结

LeetCode 题目总结

[LeetCode] 1711. Count Good Meals

上一篇:初窥React-7(updateContainer方法-p2)


下一篇:“Microsoft.Build.Tasks.Xaml.PartialClassGenerationTask“ task could not be loaded from the assembly