当前位置：首页 > news >正文

Kimi LeetCode 2835. 使子序列的和等于目标的最少操作次数 Go实现

news 2026/6/13 10:25:51

这是 LeetCode 2835 的 Go 实现，核心思路同样是贪心 + 位运算。

核心思路

1. 操作本质：将一个 `2^k` 拆成两个 `2^(k-1)`，代价为 1 次操作。这相当于把一个二进制高位"借位"到低位。
2. 可行性判断：操作不改变总和，如果 `sum(nums) < target`，直接返回 `-1`。
3. 贪心策略：从低位到高位处理 `target` 的每一位。如果当前位缺少 `1`，就找最近的高位进行拆分（拆分代价 = 位差）。

Go 实现

```go
func minOperations(nums []int, target int) int {
totalSum := 0
bitCount := make([]int, 32) // bitCount[i] 表示 2^i 出现的次数

// 统计每个数字的位信息
for _, num := range nums {
totalSum += num
for bitPos := 0; bitPos < 32; bitPos++ {
if (num>>bitPos)&1 == 1 {
bitCount[bitPos]++
}
}
}

// 总和不够，无法达成
if totalSum < target {
return -1
}

targetBit := 0 // 当前需要满足的 target 的位
processBit := 0 // 当前处理的位
operations := 0

for {
// 找到 target 下一个为 1 的位
for targetBit < 32 && (target>>targetBit)&1 == 0 {
targetBit++
}
if targetBit == 32 {
return operations // 所有需要的位都已满足
}

// 将低位向上合并（两个 2^i 可以合并为一个 2^(i+1)，无代价）
for processBit < targetBit {
bitCount[processBit+1] += bitCount[processBit] / 2
bitCount[processBit] %= 2
processBit++
}

// 如果当前位没有可用的 1，需要向高位拆分
for bitCount[processBit] == 0 {
bitCount[processBit] = 1 // 标记该位会被拆分出来
processBit++
}

// 拆分代价 = 高位到低位的距离
operations += processBit - targetBit

// 使用当前位的一个 1
bitCount[processBit]--

// 重置 processBit，继续处理下一个 target 位
processBit = targetBit
targetBit++
}
}
```

复杂度分析

指标复杂度
时间 O(n × log(max(nums)))，约 O(32n)，即 O(n)
空间 O(1)，固定大小 32 的数组

示例说明

以 `nums = [1,32,1,2], target = 12` 为例：

- `target = 12 = 1100₂`，需要 bit 2（值为 4）和 bit 3（值为 8）
- 初始：`bitCount[0]=2`（两个 1），`bitCount[1]=1`（一个 2），`bitCount[5]=1`（一个 32）
- 处理 bit 2：低位合并后不够，需要从 bit 5 拆到 bit 2，代价 3。但 bit 5→bit 4→bit 3 时，bit 3 多出一个 8，所以实际只需拆分 32→16→8（2 次操作），然后 8→4（1 次），共 3 次？不对，优化后：
- 32 拆成两个 16（1 次）→ 16 拆成两个 8（1 次）→ 用一个 8，另一个 8 拆成两个 4（1 次）
- 但答案是 2 次，因为 32→16,16（1次），然后一个16→8,8（2次），此时数组有 `[1,1,2,16,8,8]`，取 `1+1+2+8=12`。确实是 2 次。

算法会自动找到最小代价，因为优先合并低位，再向最近的高位借位。

查看全文

http://www.rkmt.cn/news/1428105.html