写点什么

2024-02-03:用 go 语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weights, 其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k, 请你按照如下规则将所有

  • 2024-02-03
    北京
  • 本文字数:1200 字

    阅读完需:约 4 分钟

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.分别将 ij 的值增加和减少 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 = 2result = putMarbles(weights, k)print(result)
复制代码



发布于: 刚刚阅读数: 4
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2024-02-03:用go语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weights, 其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k, 请你按照如下规则将所有_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区