class Solution {
public:
int sumOfPowers(vector<int>& nums, int k) {
}
};
100218. 求出所有子序列的能量和
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。
一个子序列的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。
请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。
由于答案可能会很大，将答案对 109 + 7 取余 后返回。
示例 1：
输入：nums = [1,2,3,4], k = 3
输出：4
解释：
nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。
示例 2：
输入：nums = [2,2], k = 2
输出：0
解释：
nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。
示例 3：
输入：nums = [4,3,-1], k = 2
输出：10
解释：
nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。
提示：
2 <= n == nums.length <= 50-108 <= nums[i] <= 108 2 <= k <= n原站题解
rust 解法, 执行用时: 132 ms, 内存消耗: 6.9 MB, 提交时间: 2024-07-23 09:56:55
use std::collections::HashMap;
const MOD: i64 = 1_000_000_007;
const INF: i32 = 0x3f3f3f3f;
impl Solution {
pub fn sum_of_powers(nums: Vec<i32>, k: i32) -> i32 {
let mut nums = nums.clone();
let n = nums.len();
let mut res = 0;
let mut d: Vec<Vec<HashMap<i32, i64>>> = vec![vec![HashMap::new(); k as usize + 1]; n];
nums.sort();
for i in 0..n {
d[i][1].insert(INF, 1);
for j in 0..i {
let diff = (nums[i] - nums[j]).abs();
for p in 2..=k {
let mut updates: Vec<(i32, i64)> = Vec::new();
for (&v, &cnt) in &d[j][p as usize - 1] {
let key = diff.min(v);
updates.push((key, cnt));
}
for &(key, cnt) in &updates {
let entry = d[i][p as usize].entry(key).or_insert(0);
*entry = (*entry + cnt) % MOD;
}
}
}
for (&v, &cnt) in &d[i][k as usize] {
res = (res + v as i64 * cnt % MOD) % MOD;
}
}
res as i32
}
}
golang 解法, 执行用时: 100 ms, 内存消耗: 27.3 MB, 提交时间: 2024-07-23 09:56:14
func sumOfPowers(nums []int, k int) int {
const mod int = 1e9 + 7
sort.Ints(nums)
n := len(nums)
f := map[int]int{}
var dfs func(i, j, k, mi int) int
dfs = func(i, j, k, mi int) int {
if i >= n {
if k == 0 {
return mi
}
return 0
}
if n-i < k {
return 0
}
key := mi<<18 | (i << 12) | (j << 6) | k
if v, ok := f[key]; ok {
return v
}
ans := dfs(i+1, j, k, mi)
if j == n {
ans += dfs(i+1, i, k-1, mi)
} else {
ans += dfs(i+1, i, k-1, min(mi, nums[i]-nums[j]))
}
ans %= mod
f[key] = ans
return ans
}
return dfs(0, n, k, math.MaxInt)
}
javascript 解法, 执行用时: 1422 ms, 内存消耗: 88 MB, 提交时间: 2024-04-12 00:05:17
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var sumOfPowers = function (nums, k) {
nums.sort((a, b) => {
return a - b;
});
const map = {}
var dfs = function (i, j, pre, diff) {
if (j == 0) {
return diff;
}
if (i < 0) {
return 0
}
if (i < j - 1) {
return 0
}
const key = i + '_' + j + '_' + pre + '_' + diff;
if (map[key]) {
return map[key]
}
let res1 = dfs(i - 1, j, pre, diff);
let res2 = dfs(i - 1, j - 1, nums[i], (pre !== null ? Math.min(diff, pre - nums[i]) : Number.MAX_VALUE))
map[key] = (res1 + res2) % (10 ** 9 + 7)
return (res1 + res2) % (10 ** 9 + 7)
}
let res = dfs(nums.length - 1, k, null, Number.MAX_VALUE)
return res
};
java 解法, 执行用时: 33 ms, 内存消耗: 48 MB, 提交时间: 2024-04-12 00:04:27
class Solution {
int[] nums;
int mod = 1000000007;
int n;
Map<Long, Integer> map = new HashMap<>();
public int sumOfPowers(int[] nums, int k) {
Arrays.sort(nums);
this.nums = nums;
this.n = nums.length;
return dfs(0, k, Integer.MAX_VALUE, -1);
}
public int dfs(int start, int k, int energy, int last) {
if (k == 0) {
return energy;
}
int ans = 0;
long key = ((long)energy << 18 | start << 12 | k << 6 | (last+1));
if (map.containsKey(key)) return map.get(key);
for (int i = start; i <= n-k; i++) {
if (last == -1){
ans = (ans + dfs(i+1, k-1, energy, i)) % mod;
} else {
ans = (ans + dfs(i+1, k-1, Math.min(energy, nums[i]-nums[last]), i)) % mod;
}
}
map.put(key, ans);
return ans;
}
}
cpp 解法, 执行用时: 152 ms, 内存消耗: 34.9 MB, 提交时间: 2024-04-12 00:03:48
class Solution {
public:
vector<int> num;
int _k{0};
using ll = long long;
ll MOD = 1000000007;
ll ans{0};
map<array<ll, 3>, ll> mem;
ll dfs(int cur, int step, ll minDiff, ll last) {
if(mem.contains(array{ll(cur), ll(step), minDiff})) {
return mem[array{ll(cur), ll(step), minDiff}];
}
if(step == _k) {
return minDiff % MOD;
}
ll sum{0};
for(int i = cur + 1; i < num.size() - (_k - step - 1); ++i) {
int minI = min(minDiff, ll(num[i]) - num[cur]);
sum += dfs(i, step + 1, minI, ll(num[i]));
sum %= MOD;
}
mem[array{ll(cur), ll(step), minDiff}] = sum;
return sum;
}
int sumOfPowers(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
num = nums;
_k = k;
for(int i = 0; i <= num.size() - (_k); ++i) {
ans += dfs(i, 1, INT_MAX, INT_MIN);
ans %= MOD;
}
return ans;
}
};
python3 解法, 执行用时: 1031 ms, 内存消耗: 21.9 MB, 提交时间: 2024-03-31 21:54:10
class Solution:
def sumOfPowers(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
mod = int(1e9 + 7)
'''
dp[i][j] = Counter()
到第i位，已选j个数，且i是最后一个数
Counter:
最小差值为key有value种情况
'''
dp = [[Counter() for _ in range(k+1)] for _ in range(n)]
for i in range(n):
dp[i][1][int(1e9)] = 1
for j in range(2,k+1):
for li in range(i):
for d,t in dp[li][j-1].items():
nd = min(d,nums[i]-nums[li])
dp[i][j][nd] += t
res = 0
for i in range(n):
for d,t in dp[i][k].items():
res += d * t
res %= mod
return res