leetcode3098. 求出所有子序列的能量和

2025/9/28 12:45:37 来源：https://blog.csdn.net/qq_40016005/article/details/140629593 浏览: 次关键词：leetcode3098. 求出所有子序列的能量和

官解

class Solution(object):# 定义常量mod = int(1e9 + 7)  # 模数，用于防止结果溢出inf = float('inf')  # 无穷大，用于初始化时的特殊值def sumOfPowers(self, nums, k):n = len(nums)  # 数组长度res = 0  # 用于存储最终结果# 三维动态规划表，d[i][p][v] 表示以 nums[i] 结尾的长度为 p 的子序列，最小绝对差为 v 的频次d = [[defaultdict(int) for _ in range(k + 1)] for _ in range(n)]nums.sort()  # 对 nums 进行排序，确保子序列的顺序for i in range(n):# 初始化：长度为 1 的子序列，最小绝对差为无穷大，频次为 1d[i][1][self.inf] = 1for j in range(i):# 计算 nums[i] 和 nums[j] 之间的绝对差diff = abs(nums[i] - nums[j])# 更新长度为 p 的子序列的最小绝对差，其中 p 从 2 到 kfor p in range(2, k + 1):for v, cnt in d[j][p - 1].items():# 更新 d[i][p][min(diff, v)]d[i][p][min(diff, v)] = (d[i][p][min(diff, v)] + cnt) % self.mod# 计算结果：遍历所有以 nums[i] 结尾的长度为 k 的子序列for v, cnt in d[i][k].items():# 累加 v * cnt 到 res 中，并取模res = (res + v * cnt % self.mod) % self.modreturn res  # 返回最终结果

Chatgpt解

这段代码实现了一个名为sumOfPowers的方法，它的目标是计算给定数组 nums 中所有长度为 k 的子序列的最小绝对差的和，并将结果对 1e9 + 7 取模。

代码分解与解释

变量和数据结构

mod = int(1e9 + 7): 模数，用于防止结果溢出。
inf = float('inf'): 表示无穷大，用于初始化时的特殊值。
d = [[defaultdict(int) for _ in range(k + 1)] for _ in range(n)]: 三维动态规划表，用于存储子序列的最小绝对差。
- d[i][p] 表示以 nums[i] 结尾的长度为 p 的子序列，其最小绝对差的频次。
- d[i][p][v] 表示上述子序列中，最小绝对差为 v 的子序列数量。

算法步骤

初始化:
- n = len(nums): 数组 nums 的长度。
- res = 0: 用于存储最终结果。
- nums.sort(): 对 nums 进行排序，确保子序列的顺序。
- 初始化 d[i][1][inf] = 1，表示长度为 1 的子序列，最小绝对差为无穷大。
动态规划填表:
- 遍历数组的每一个元素 nums[i]:
  - 对于每一个之前的元素 nums[j] (其中 j < i):
    - 计算 nums[i] 和 nums[j] 之间的绝对差 diff。
    - 更新长度为 p 的子序列的最小绝对差，其中 p 从 2 到 k:
      - 对于 d[j][p-1] 中的每个 v 和 cnt:
        更新 d[i][p][min(diff, v)]，其中 v 是子序列的最小绝对差，cnt 是其出现的频次。
        使用 min(diff, v) 确保当前子序列的最小绝对差。
计算结果:
- 遍历所有以 nums[i] 结尾的长度为 k 的子序列:
  - 对于每个最小绝对差 v 和其出现的频次 cnt:
    - 累加 v * cnt 到 res 中，并取模。