数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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 次浏览
广告