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

千问 LeetCode 2835. 使子序列的和等于目标的最少操作次数 C语言实现

news 2026/5/30 14:22:34

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

核心思路

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

C 语言实现

```c
int minOperations(int* nums, int numsSize, int target) {
long long totalSum = 0;
int bitCount[32] = {0}; // bitCount[i] 表示 2^i 出现的次数

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

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

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

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

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

// 如果当前位没有可用的 1，需要向高位拆分
while (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.gsyq.cn/news/1428046.html