2024-02-03:用go语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weights,
其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k,
请你按照如下规则将所有的珠子放进 k 个背包。
没有背包是空的。
如果第 i 个珠子和第 j 个珠子在同一个背包里,
那么下标在 i 到 j 之间的所有珠子都必须在这同一个背包中,
如果一个背包有下标从 i 到 j 的所有珠子,那么这个背包的价格是 weights[i] + weights[j] 。
一个珠子分配方案的 分数 是所有 k 个背包的价格之和。
请你返回所有分配方案中,最大分数 与 最小分数 的 差值 为多少。
输入:weights = [1,3,5,1], k = 2。
输出:4。
答案2024-02-03:
来自左程云。
灵捷3.5
大体步骤如下:
1.初始化变量:
• 将权重数组weights的长度保存在变量n中。
• 创建一个长度为n-1的整数数组sums。
2.计算相邻珠子重量之和:
• 遍历weights数组中的元素,对于每个元素 weights[i],计算 weights[i] 和 weights[i+1] 的和,并将结果保存在sums[i]中。
3.对sums数组进行排序:
• 使用排序函数对sums数组进行升序排序。
4.循环分配珠子到背包:
4.1.初始化变量ans为 0,用于保存最终的结果。
4.2.使用循环,从i=0,j=n-2,p=1开始循环,其中p表示已经形成背包的数量。
4.3.当p小于k时,执行以下操作:
4.3.1.计算sums[j] - sums[i]的差值,并将其累加到ans中。
4.3.2.分别将i和j的值增加和减少 1,将p增加 1。
5.返回结果ans,即最大分数与最小分数之差。
总的时间复杂度:排序操作的时间复杂度为 O(n log n),其中 n 是珠子的数量。其他步骤的时间复杂度都是 O(n)。因此,总的时间复杂度为 O(n log n)。
总的额外空间复杂度:除了输入的权重数组weights外,在算法执行过程中需要额外使用的空间为sums数组,其长度为n-1,因此额外空间复杂度为 O(n)。
go完整代码如下:
package main
import (
"fmt"
"sort"
)
func putMarbles(weights []int, k int) int64 {
n := len(weights)
sums := make([]int64, n-1)
for i := 1; i < n; i++ {
sums[i-1] = int64(weights[i-1] + weights[i])
}
sort.Slice(sums, func(i, j int) bool {
return sums[i] < sums[j]
})
var ans int64
for i, j, p := 0, n-2, 1; p < k; i, j, p = i+1, j-1, p+1 {
ans += sums[j] - sums[i]
}
return ans
}
func main() {
weights := []int{1, 3, 5, 1}
k := 2
result := putMarbles(weights, k)
fmt.Println(result)
}
在这里插入图片描述python完整代码如下:
# -*-coding:utf-8-*-
def putMarbles(weights, k):
n = len(weights)
sums = [weights[i-1] + weights[i] for i in range(1, n)]
sums.sort()
ans = 0
for i, j, p in zip(range(n-1), range(n-2, -1, -1), range(1, k)):
ans += sums[j] - sums[i]
return ans
weights = [1, 3, 5, 1]
k = 2
result = putMarbles(weights, k)
print(result)
在这里插入图片描述
领取专属 10元无门槛券
私享最新 技术干货