Python陣列中計數優質對的程式

假設我們有一個名為nums的陣列，其中包含非負值。如果答案過大，我們需要找到陣列中存在的優質索引對的數量，則返回答案模10^9+7。這裡，當一對索引(i, j)滿足所有這些條件時，則被稱為優質對：1. 0 <= i < j < nums的大小 2. nums[i] + rev(nums[j]) 等於 nums[j] + rev(nums[i])

注意 − 這裡rev()只反轉整數的正數部分，所以如果存在rev(564)，則表示465，但如果存在rev(540)，則返回45。

因此，如果輸入類似於nums = [97,2,42,11]，則輸出將為2，因為存在兩個對(0,2)和(1,3)，對於第一個[97 + rev(42) = 97+24 = 121，以及42 + rev(97) = 42 + 79 = 121]，對於第二個[2 + rev(11) = 2 + 11 = 13以及11 + rev(2) = 13]。

為了解決這個問題，我們將遵循以下步驟：

  • m := (10^9) + 7

  • dic := 一個空的對映，其預設值為0

  • 對於nums中的每個num，執行：

    • rev := num的反轉

    • 將dic[num - rev]增加1

  • res := 0

  • 對於dic所有值的列表中的每個val，執行：

    • res := res + (val*(val-1))/2 的商

  • 返回res mod m

示例

讓我們看看下面的實現，以便更好地理解：

from collections import defaultdict
def solve(nums):
   m = (10**9)+7
   dic = defaultdict(int)
   for num in nums:
      rev=int(str(num)[::-1])
      dic[num-rev]+=1

   res=0
   for val in dic.values():
      res += (val*(val-1)) // 2

   return res % m

nums = [97,2,42,11]
print(solve(nums))

輸入

[97,2,42,11]

輸出

2

更新於：2021年10月7日

317 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始
廣告