用 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

Dev Prakash Sharma

更新時間： 2021 年 2 月 5 日

282 次瀏覽

開啟您的 職業生涯

完成課程以獲得認證

立即開始