用 Python 计算美食

• Z时代
• 2024-01-10
• 分类：综合

一顿美餐恰好包含两种不同的食物，其美味之和等于 2 的幂。你可以选择任何两种不同的食物来做一顿美餐。

让我们假设我们已经给出了一个整数数组 arr，其中 arr[i] 是第 i 项食物的美味程度，返回您可以从这个列表中制作的不同美食的数量。

例如，

输入 1 -

arr[ ] = {1, 3, 5, 7, 9}

输出-

4

说明- 好饭是 (1,3)、(1,7)、(3,5) 和 (7,9)。它们各自的和是 4、8、8 和 16，都是 2 的幂。

输入 2 -

arr[ ]= {1,1,1,3,3,3,7}

输出-

15

说明- 好饭是 (1,1) 3 种方式，(1,3) 9 种方式，和 (1,7) 3 种方式。

用来解决这个问题的方法

• 将输入作为正整数数组。

• 函数计数对将所有数组元素作为整数列表。

• 按升序对输入数组元素进行排序。

• 对于数组的每个元素，找到最大和，使得每个元素都在 '2' 的幂中。

示例

class Solution:
   def countpairs(self, arr: List[int]) -> int:
      """
         elem1 + elem2 == 1 << i
         elem1 = 2 << i - elem2
      """
      result = 0
      seen = defaultdict(int)
      arr.sort()
      for d in arr:
         n = 1
         while n <= d + d:
            ans = (ans + seen[n-d]) % (10 ** 9 + 7)
            n = n << 1
         seen[d] += 1
      return ans
sol1= Solution()
print(sol1.countpairs([1,1,1,3,3,3,7]))

4

以上是 用 Python 计算美食 的全部内容， 来源链接： utcz.com/z/341456.html