题目描述
思路解析动画文字版
记住两句:c 这位是 1 就「至少要有一个 1」;c 这位是 0 就「a、b 这位的 1 全要清掉」。下面逐列套用。
把 a、b、它们的 OR、以及目标 c 都摊成 9 位二进制对齐排好(高位在左)。接下来从最左一列开始,逐列裁决这一位要不要翻、翻几次。
第 1 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 1。
z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。
第 2 列(从左数):a 这位 x = 0,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 1。
z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。
第 3 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 0。
z=0 但有 1 个 1 → 这 1 个 1 要清成 0,本列代价 1。c 这位要 0,所以 a、b 这位上凡是 1 的都得翻成 0。这里有 1 个 1(标红),本列代价 1。
第 4 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 0。
z=0 但有 1 个 1 → 这 1 个 1 要清成 0,本列代价 1。c 这位要 0,所以 a、b 这位上凡是 1 的都得翻成 0。这里有 1 个 1(标红),本列代价 1。
第 5 列(从左数):a 这位 x = 0,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 1。
z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。
第 6 列(从左数):a 这位 x = 0,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 0。
z=0 但有 1 个 1 → 这 1 个 1 要清成 0,本列代价 1。c 这位要 0,所以 a、b 这位上凡是 1 的都得翻成 0。这里有 1 个 1(标红),本列代价 1。
第 7 列(从左数):a 这位 x = 1,b 这位 y = 0,当前 OR = 1,目标 c 这位 z = 1。
z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。
第 8 列(从左数):a 这位 x = 1,b 这位 y = 1,当前 OR = 1,目标 c 这位 z = 1。
z=1 且 x、y 里已有 1 → OR 已经是 1,达标,本列代价 0。c 这位要 1,而 a、b 这位至少已有一个 1,OR 天然是 1,无需翻转。本列代价 0。
第 9 列(从左数):a 这位 x = 0,b 这位 y = 0,当前 OR = 0,目标 c 这位 z = 0。
z=0 且 x=0、y=0 → OR 已是 0,达标,本列代价 0。c 这位要 0,而 a、b 这位本就都是 0,OR 是 0,无需翻转。本列代价 0。
九列逐位裁决完毕,把每列代价加起来:本例最少翻转 3 次。各位互不干扰,加法即得全局最优。
边界都落在「已达标」「高位的 1 要清」这两端,逐位规则同样成立。
面试重点是说清「按位独立」这一性质,它是逐位累加成立的根基。
参考代码
class Solution: def minFlips(self, a: int, b: int, c: int) -> int: ans = 0 for i in range(31): x = (a >> i) & 1 y = (b >> i) & 1 z = (c >> i) & 1 if z == 1: if x == 0 and y == 0: ans += 1 else: ans += x + y return ans复杂度
- 时间：O(1)，固定扫 31 个二进制位,与数值大小无关
- 空间：O(1)，只用几个整型变量累加
易错点
面试追问把动画讲成自己的话
追问为什么各位之间可以独立计算、直接相加?
追问如果不用循环逐位,能否用一行位运算搞定?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题