2024-09-25:用go语言,给定一个长度为 n 的整数数组 nums 和一个正整数 k, 定义数组的“能量“为所有和为 k

举报
福大大架构师每日一题 发表于 2024/09/25 17:17:05 2024/09/25
4k+ 0 0
【摘要】 2024-09-25:用go语言,给定一个长度为 n 的整数数组 nums 和一个正整数 k,定义数组的"能量"为所有和为 k 的子序列的数量之和。请计算 nums 数组中所有子序列的能量和,并对结果取模 10^9 + 7 后返回。输入: nums = [1,2,3], k = 3。输出: 6。解释:总共有 5 个能量不为 0 的子序列:子序列 [1,2,3] 有 2 个和为 3 的子序列:...

2024-09-25:用go语言,给定一个长度为 n 的整数数组 nums 和一个正整数 k,

定义数组的"能量"为所有和为 k 的子序列的数量之和。

请计算 nums 数组中所有子序列的能量和,并对结果取模 10^9 + 7 后返回。

输入: nums = [1,2,3], k = 3。

输出: 6。

解释:

总共有 5 个能量不为 0 的子序列:

子序列 [1,2,3] 有 2 个和为 3 的子序列:[1,2,3] 和 [1,2,3] 。

子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3] 。

子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3] 。

子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3] 。

子序列 [1,2,3] 有 1 个和为 3 的子序列:[1,2,3] 。

所以答案为 2 + 1 + 1 + 1 + 1 = 6 。

答案2024-09-25:

chatgpt

题目来自leetcode3082。

大体步骤如下:

1.定义一个数组 f 用于记录不同和值下的子序列数量,数组长度为 k+1,初始时令 f[0] = 1 表示和为 0 时只有空子序列存在。

2.遍历给定的整数数组 nums 中的每个元素 x,对于每个 x,从 k 开始向前遍历到 0,更新 f[j] 的值:

  • 如果当前值 j >= x,则更新 f[j] = (f[j]*2 + f[j-x]) % mod。这表示新的和为 j 的子序列数量是原来和为 j 的子序列数量的两倍加上和为 j-x 的子序列数量。

  • 如果当前值 j < x,则更新 f[j] = f[j] * 2 % mod。这表示由于当前的 j 无法和当前的 x 相加得到新的和值,因此只能将和为 j 的子序列数量乘以 2。

3.最终返回 f[k],即所有和为 k 的子序列的数量之和。

总体的时间复杂度是 O(n * k),其中 n 是 nums 的长度,k 是给定的正整数。

空间复杂度为 O(k)。

Go完整代码如下:

package main

import (
	"fmt"
)

func sumOfPower(nums []int, k int) int {
	const mod = 1_000_000_007
	f := make([]int, k+1)
	f[0] = 1
	for _, x := range nums {
		for j := k; j >= 0; j-- {
			if j >= x {
				f[j] = (f[j]*2 + f[j-x]) % mod
			} else {
				f[j] = f[j] * 2 % mod
			}
		}
	}
	return f[k]
}
func main() {
	nums:=[]int{1,2,3}
	k:=3
	fmt.Println(sumOfPower(nums,k))
}

在这里插入图片描述

Rust完整代码如下:

const MOD: i64 = 1_000_000_007;

fn sum_of_power(nums: Vec<i32>, k: i32) -> i64 {
    let k = k as usize;
    let mut f = vec![0; k + 1];
    f[0] = 1;
    
    for &x in nums.iter() {
        for j in (0..=k).rev() {
            if j >= x as usize {
                f[j] = (f[j] * 2 + f[j - x as usize]) % MOD;
            } else {
                f[j] = f[j] * 2 % MOD;
            }
        }
    }
    
    f[k]
}

fn main() {
    let nums = vec![1, 2, 3];
    let k = 3;
    println!("{}", sum_of_power(nums, k));
}

在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。