LeetCode 面试题 05.01. 插入
题目描述
题意分析
位号从最低位的
0开始，把M的二进制表示写入N的闭区间[i,j]，窗口以外的位保持不变。题目保证这j-i+1位足以容纳M；若M不够长，窗口剩余高位要补零。这是替换已有位段，不只是把其中若干位设为
1。因此需要先清掉窗口里的旧值，再写入M。
解法：先清目标位段再左移合并
核心思路
[!blue]
对某个目标位
k，1 << k只有第k位为1，取反后的~(1 << k)则只有这一位为0。将N与这个掩码按位与，就能把第k位清零，并保留其他位。依次处理i..j后，整个窗口归零，窗口外仍与原来的N一致。接着把
M左移i位，使它的最低位对齐窗口起点。因为M能放进窗口，移位后的有效位不会超过j，低于i的位置也全是零。与清理后的N按位或，就恰好把M写进窗口，而不会影响外部位。清除和写入缺一不可：按位或只能保留或增加
1，不能用M中的零覆盖旧的1。先清完整个窗口，还能保证M较短时，未覆盖的窗口高位确实补零。
解题步骤
- 对闭区间
i..j的每一位，用~(1 << k)清掉N的对应位。- 把
M左移i位，与清理后的N按位或。
M=0时只留下清零结果；窗口只有一位时，循环也会处理该位。逐位清除不需要构造1 << 32这样的整段掩码，避免 Java 将移位距离折回零位的边界问题。
代码实现
class Solution {
public int insertBits(int N, int M, int i, int j) {
// 先把窗口 [i, j] 逐位清零，或运算才等价于赋值。
for (int k = i; k <= j; ++k) {
N &= ~(1 << k);
}
return N | M << i;
}
}
func insertBits(N int, M int, i int, j int) int {
// 先把窗口 [i, j] 逐位清零，或运算才等价于赋值。
for k := i; k <= j; k++ {
N &= ^(1 << k)
}
return N | M<<i
}
复杂度分析
- 时间复杂度：$O(j-i+1)$，每个窗口位清除一次；固定 32 位模型下为 $O(1)$。
- 空间复杂度：$O(1)$，只使用常数个变量。
关键点总结
[!green]
- 单位掩码负责只清一个位置，循环负责覆盖整个闭区间。
- 左移负责对齐，按位或负责合并；窗口外的位在两步中都保持不变。
- 题目已经保证
M能放下，不需要额外截断它的有效位。
易错点总结
[!yellow]
- 不能只做
N|(M<<i)，N 窗口里的旧 1 会残留。- 清位循环包含 j。
- Java 移位距离按低 5 位取值，构造掩码时不要直接写 1«32；逐位清除避开这个边界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 05.07. 配对交换 | 简单 | 都先用位掩码选中待修改位置，再移位并按位或合并；本题处理连续位段，该题把奇偶位置分成两组交换。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！