LeetCode 面试题 05.03. 翻转数位
题目描述
题意分析
可以把一个 32 位整数中的一个
0翻成1，求能得到的最长连续1的长度。处理的是固定的 32 位表示，包括高位零和负数的补码位，答案不会超过32。一段连续位能通过这次操作变成全
1，当且仅当其中至多有一个0。因此问题转化为：在这 32 位中，寻找最多包含一个零的最长连续区间。只有一个零就翻转它；没有零的区间本来就全为一，全 1 输入的答案就是32。不能在最高有效位处停止，因为其上方的零也可能用来延长连续段。固定扫描还自然覆盖
num=0，此时能得到的最长长度为1。
解法：固定宽度滑动窗口
核心思路
[!blue]
从低位向高位扫描，用
[j,i]作为窗口，cnt表示其中零的个数。连续位反向读取仍然连续，因此这个方向不会改变要求的最大长度。
((num >> i) & 1)取得原数第i位，再与1异或，就得到“这一位是否为零”的计数贡献。加入当前位后，如果cnt>1，就不断移出左端位，并扣掉它对零数的贡献，直到窗口重新合法。更新答案时，
j是以当前i结尾的最靠左合法起点。收缩只在窗口含有两个零时发生，并在刚刚移出更早的零后停止；更靠左的起点仍会包含这两个零。以前已经排除的起点也不会因右侧再加入字符而重新合法，所以左端无需回退。因而
i-j+1是以当前位结尾的最长可行长度。每个连续区间都有一个右端点，枚举所有i并取这些长度的最大值，就不会漏掉最优区间。两个指针只向前移动，窗口计数始终与当前区间一致。
解题步骤
- 初始化左端点
j = 0、窗口零数cnt = 0、答案answer = 0。- 用
i = 0..31从低位到高位扫描；连续区间反向读取仍然连续，不影响长度。- 取出第
i位，若为 0 就让cnt加一。- 当
cnt > 1时移动j，移出的位若为 0，同时把cnt减一。- 此时窗口合法，用其长度更新答案。
对负数，算术右移虽然会补符号位，但再与
1相与，只取出原来的指定位置。只扫描0..31，不会把更宽机器字上的符号扩展算进答案。
代码实现
// 窗口中最多允许一个 0；这个 0 就是要翻转的位。
class Solution {
public int reverseBits(int num) {
int answer = 0;
int cnt = 0;
for (int i = 0, j = 0; i < 32; ++i) {
cnt += num >> i & 1 ^ 1;
while (cnt > 1) {
cnt -= num >> j & 1 ^ 1;
++j;
}
answer = Math.max(answer, i - j + 1);
}
return answer;
}
}
// 窗口中最多允许一个 0；这个 0 就是要翻转的位。
func reverseBits(num int) (answer int) {
var cnt, j int
for i := 0; i < 32; i++ {
cnt += num>>i&1 ^ 1
for cnt > 1 {
cnt -= num>>j&1 ^ 1
j++
}
answer = max(answer, i-j+1)
}
return
}
复杂度分析
- 时间复杂度：对 32 位整数固定扫描 32 次，严格来说是 $O(1)$；推广到长度为
b的位串是 $O(b)$，左右指针都至多移动b次。- 空间复杂度：$O(1)$，只维护两个指针、窗口零数和答案。
关键点总结
[!green]
- 一次翻转预算转化为窗口内至多一个零。
- 收缩到刚好合法，才能保留当前右端点下的最长区间。
- 固定扫描
32位，统一处理高位零、负数与全一情况。
易错点总结
[!yellow]
- 只扫描到最高有效位，会漏掉可翻转的高位零。
- 收缩后要同步更新
cnt，不能只移动左指针。- 位运算表达式的含义是
((num >> i) & 1) ^ 1，先提取单个位，再把它转换为零的数量贡献。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1004. 最大连续1的个数 III | 中等 | 同样寻找至多包含限定数量零的最长窗口，本题只扫描整数低 32 位且最多翻一个零。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！