用 Python 统计美味餐点

美味餐点中包含正好两份不同类型的食品，美味度之和等于 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) 三份、(1, 3) 九份和 (1, 7) 三份。

本问题使用的方法为

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

  • 一个函数 count pairs 使用列表形式获取所有数组元素为整数。

  • 对输入数组元素按递增顺序排序。

  • 对数组的每个元素，找到使每个元素为 '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

更新时间： 2021 年 2 月 5 日

282 次浏览

开启您的 职业生涯

完成课程以获得认证

立即开始
广告