Medium

题目描述

给你三个正整数 a、b 和 c。

你需要对 a 和 b 的二进制表示中的某些位进行翻转，使得 a OR b == c，请你返回所需的最小翻转次数。

翻转操作包括将任意一个位从 1 变为 0 或从 0 变为 1。

示例 1：

输入：a = 2, b = 6, c = 5
输出：3
解释：翻转后 a = 1, b = 4, c = 5 使得 (a OR b == c)

示例 2：

输入：a = 4, b = 2, c = 7
输出：1

示例 3：

输入：a = 1, b = 2, c = 3
输出：0

约束条件：

  • 1 <= a <= 10^9
  • 1 <= b <= 10^9
  • 1 <= c <= 10^9

提示：

  • 逐位检查是否需要翻转。

解题思路

这道题需要逐位比较三个数的二进制表示，分析每一位是否满足 OR 运算的要求。

核心思路：

对于二进制的每一位，我们有以下情况：

  1. 如果 c 的当前位为 1：那么 a 或 b 至少有一位需要为 1。如果 a 和 b 当前位都为 0，则需要翻转其中一位。
  2. 如果 c 的当前位为 0：那么 a 和 b 的当前位都必须为 0。如果 a 为 1 需要翻转，如果 b 为 1 也需要翻转。

算法步骤：

  1. 从最低位开始，逐位检查 a、b、c 的对应位
  2. 使用位运算 & 1 获取当前位的值
  3. 根据上述规则计算需要的翻转次数
  4. 将三个数都右移一位，继续处理下一位
  5. 直到三个数都变为 0

这种方法时间复杂度为 O(log(max(a,b,c)))，最多需要检查 32 位。

推荐解法： 逐位检查法，思路清晰且效率高。

代码实现

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int flips = 0;
        
        while (a || b || c) {
            int bitA = a & 1;
            int bitB = b & 1;
            int bitC = c & 1;
            
            if (bitC == 1) {
                // c的当前位为1，a或b至少有一个为1
                if (bitA == 0 && bitB == 0) {
                    flips++;
                }
            } else {
                // c的当前位为0，a和b都必须为0
                flips += bitA + bitB;
            }
            
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        
        return flips;
    }
};

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        
        while a or b or c:
            bit_a = a & 1
            bit_b = b & 1
            bit_c = c & 1
            
            if bit_c == 1:
                # c的当前位为1，a或b至少有一个为1
                if bit_a == 0 and bit_b == 0:
                    flips += 1
            else:
                # c的当前位为0，a和b都必须为0
                flips += bit_a + bit_b
            
            a >>= 1
            b >>= 1
            c >>= 1
        
        return flips

public class Solution {
    public int MinFlips(int a, int b, int c) {
        int flips = 0;
        
        while (a != 0 || b != 0 || c != 0) {
            int bitA = a & 1;
            int bitB = b & 1;
            int bitC = c & 1;
            
            if (bitC == 1) {
                // c的当前位为1，a或b至少有一个为1
                if (bitA == 0 && bitB == 0) {
                    flips++;
                }
            } else {
                // c的当前位为0，a和b都必须为0
                flips += bitA + bitB;
            }
            
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        
        return flips;
    }
}

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var minFlips = function(a, b, c) {
    let flips = 0;
    
    while (a > 0 || b > 0 || c > 0) {
        let bitA = a & 1;
        let bitB = b & 1;
        let bitC = c & 1;
        
        if (bitC === 1) {
            if (bitA === 0 && bitB === 0) {
                flips++;
            }
        } else {
            flips += bitA + bitB;
        }
        
        a >>= 1;
        b >>= 1;
        c >>= 1;
    }
    
    return flips;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log(max(a,b,c)))需要检查最多32位二进制位
空间复杂度O(1)只使用了常数个变量

相关题目