LeetCode 面试题 05.03. 翻转数位
目录
题目描述
题意分析
把一个 32 位整数的某一位从
0翻成1，求翻转后最长连续1的长度。只能翻0 → 1，不能把1翻成0；即使原数已经全是1，答案也最多是 32。问题等价于：在固定的 32 位二进制序列中，找一个最多包含一个 0 的最长连续区间。区间中的那个 0 就是被翻转的位置；若区间本来全是 1，可以把区间外的某个 0 翻转，长度不受影响。
必须扫描满 32 位，不能写成
while (num != 0)。高位补零也是合法的可翻转位，例如num = 0的答案应为 1；提前在数值变成零时停止会漏掉这些位。
解法：固定宽度滑动窗口
核心思路
暴力做法可以依次翻转 32 个位置，每次再扫描 32 位求最长连续 1。它在固定 32 位下也能通过，但没有抓住题目的结构；若推广到长度为
n的位串，就会变成 $O(n^2)$。用窗口
[j, i]表示当前候选区间，cnt记录窗口里的 0 的数量。每加入第i位，就把bit ^ 1加进cnt：位为 1 时贡献 0，位为 0 时贡献 1。若cnt > 1，不断右移左端j，并扣掉移出位对 0 数量的贡献，直到窗口重新至多含一个 0。循环不变量是：更新答案前，
[j, i]是以i结尾、最多包含一个 0 的最长区间。任何更靠左的起点都会含两个 0，因此不可能合法；所以用i - j + 1更新全局最大值不会漏解。
解题步骤
- 初始化左端点
j = 0、窗口零数cnt = 0、答案answer = 0。- 用
i = 0..31从低位到高位扫描；连续区间反向读取仍然连续，不影响长度。- 取出第
i位，若为 0 就让cnt加一。- 当
cnt > 1时移动j，移出的位若为 0，同时把cnt减一。- 此时窗口合法，用其长度更新答案。
以
num = 1775为例，二进制是11011101111，两段较长的 1 分别是111和1111，中间只隔一个 0。窗口扩到第二个 0 时会收缩掉更早的那段；最终保留1110 1111，翻转中间的 0 后得到连续 8 个 1，因此答案为 8。
代码实现
// 窗口中最多允许一个 0；这个 0 就是要翻转的位。
class Solution {
public int reverseBits(int num) {
int answer = 0, 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)$，只维护两个指针、窗口零数和答案。
关键点总结
- “允许翻转一个 0”就是“窗口内最多允许一个 0”，这是把修改次数转成窗口预算的典型模型。
bit ^ 1只是在 0/1 间取反，用来直接累计零的数量；面试时写成if (bit == 0) cnt++也完全可以，清晰优先。- 面试官若追问“允许翻转
k个 0”，只需把收缩条件从cnt > 1改成cnt > k，就是 LeetCode 1004。- 固定宽度整数题要主动说明扫描 32 位，尤其要覆盖
num = 0与全 1 两个边界。
易错点总结
- 只扫描到最高有效位：
num = 0时循环一次都不执行，错误返回 0；固定扫描 32 位才能得到 1。- 窗口允许两个 0：把收缩条件误写成
cnt > 2，num = 0b10101会把需要翻两个 0 的长度 5 当成答案，正确答案是 3。- 收缩时忘记扣掉左端位的贡献：
cnt只增不减，遇到第二个 0 后窗口会一直收缩到末尾。- 不加括号直接解释位运算优先级：代码虽然可运行，但白板表达容易产生歧义；讲解时应明确写成
((num >> i) & 1) ^ 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 424. 替换后的最长重复字符 | 中等 | 替换窗口 |
| 485. 最大连续 1 的个数 | 简单 | 替换窗口 |
| 487. 最大连续1的个数 II | 中等 | 替换窗口 |
| 1004. 最大连续1的个数 III | 中等 | 替换窗口 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 替换窗口 |