Python程式：求數字列表所有子序列寬度之和

假設我們有一個名為nums的數字列表，序列的寬度定義為序列中最大值和最小值的差。我們需要找到nums的所有子序列的寬度之和。如果結果非常大，則將結果模 10^9+7。

例如，如果輸入是nums = [7, 4, 9]，則輸出為15，因為子序列有：[7]，[4]，[9]，[7, 4]，[7, 9]，[4, 9]，[7, 4, 9]。它們的寬度分別為：0, 0, 0, 3, 2, 5, 5，總和為15。

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

  • m := 10^9 + 7

  • 對列表nums進行排序

  • ans := 0

  • power := 一個大小與(nums + 1)相同的列表，並填充為1

  • 對於範圍從1到nums大小+1的i：

    • power[i] := power[i - 1] * 2 mod m

    • 對於範圍從0到nums大小的i：

      • positive := (power[i] - 1) * nums[i]

      • negative := (power[nums大小 - i - 1] - 1) * nums[i]

      • ans := (ans + positive - negative) mod m

  • 返回ans

示例

讓我們看下面的實現來更好地理解：

線上演示

class Solution:
   def solve(self, nums):
      m = 10**9 + 7
      nums.sort()
      ans = 0
      power = [1] * (len(nums) + 1)
      for i in range(1, len(nums) + 1):
         power[i] = power[i - 1] * 2 % m
      for i in range(0, len(nums)):
         positive = (power[i] - 1) * nums[i]
         negative = (power[len(nums) - i - 1] - 1) * nums[i]
         ans = (ans + positive - negative) % m
      return ans
ob = Solution()
nums = [7, 4, 9]
print(ob.solve(nums))

輸入

[7, 4, 9]

輸出

15

更新於：2020-12-23

98 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告