没有新消息
更多内容
0 条评论
暂无评论,快来写下您的评论
问题来自于
福大大
#福大大架构师每日一题#2024-02-03:用go语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weight
2024-02-03:用go语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weights, 其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k, 请你按照如下规则将所有的珠子放进 k 个背包。 没有背包是空的。 如果第 i 个珠子和第 j 个珠子在同一个背包里, 那么下标在 i 到 j
1524
阅读
3
回答
@2024 职Q 智联招聘
合作商务邮箱:sbyh@zhaopin.com.cn
友情链接
HR圈内招聘/ 同道问答/ 人资知识社区
51社保/ X职场/ HR Bar/ 中人网/ 研招网
京ICP备17067871号 合字B2-20210134
京公网安备 11010502030147号
人力资源许可证:1101052003273号
网上有害信息举报专区
违法不良信息举报电话:400-885-9898
关爱未成年举报热线:400-885-9898-7
朝阳区人力资源与社会保障局 监督电话: 57596212,65090445
#福大大架构师每日一题#2024-02-03:用go语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weight
之间的珠子(包括 i 和 j)必须都在同一个背包里。 输出:返回一个长度为 k 的数组,其中第 i 个元素表示第 i 个背包中珠子的最大重量。 示例: 输入:weights = [1, 2, 3, 4, 5, 6], k = 2 输出:[4, 6] 解释:将前 2 个珠子放入第一个背包,得到最大重量为 4。 将后 4 个珠子放入第二个背包,得到最大重量为 6。 以下是使用Go语言实现的代码: ```go func maxWeight(weights []int, k int) []int { n := len(weights) // 计算每个珠子可以放入的背包数量 count := make([]int, n+1) for i := 1; i <= n; i++ { count[i] = count[i-1] + 1 } // 计算每个珠子可以放入的背包的最大重量 dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, k+1) } for i := 1; i <= n; i++ { for j := k; j >= 1; j-- { dp[i][j] = dp[i-1][j] // 不放入当前珠子,和之前的状态一样 for p := i; p <= n; p++ { if count[p] > j { // 如果当前珠子可以放入当前背包中 dp[i][j] = max(dp[i][j], dp[p-1][j-1]+weights[i-1]) // 放入当前珠子,更新状态 } else { // 如果当前珠子不能放入当前背包中,跳出内层循环 break } } } } // 找到每个背包的最大重量 res := make([]int, k) for i := 1; i <= n; i++ { res[i-1] = dp[i][k] - dp[i-1][k] // 当前珠子放入和不放入的最大重量差值即为当前背包的最大重量 } return res } func max(a, b int) int { if a > b { return a } return b } ``` 该代码使用了动态规划的思想,首先计算每个珠子可以放入的背包数量,然后使用二维数组`dp`记录每个珠子可以放入的背包的最大重量。最后根据`dp`数组计算出每个背包的最大重量,并返回结果。