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

这是 LeetCode 2835 的 C 语言实现核心思路同样是 贪心 位运算。核心思路1. 操作本质将一个 2^k 拆成两个 2^(k-1)代价为 1 次操作。这相当于把一个二进制高位借位到低位。2. 可行性判断操作不改变总和如果 sum(nums) target直接返回 -1。3. 贪心策略从低位到高位处理 target 的每一位。如果当前位缺少 1就找最近的高位进行拆分拆分代价 位差。C 语言实现cint 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^(i1)无代价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;// 使用当前位的一个 1bitCount[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两个 1bitCount[1]1一个 2bitCount[5]1一个 32- 处理 bit 2低位合并后不够需要从 bit 5 拆到 bit 2代价 3。但 bit 5→bit 4→bit 3 时bit 3 多出一个 8所以实际只需拆分 32→16→82 次操作然后 8→41 次共 3 次不对优化后- 32 拆成两个 161 次→ 16 拆成两个 81 次→ 用一个 8另一个 8 拆成两个 41 次- 但答案是 2 次因为 32→16,161次然后一个16→8,82次此时数组有 [1,1,2,16,8,8]取 112812。确实是 2 次。算法会自动找到最小代价因为优先合并低位再向最近的高位借位。