leetcode 周赛 171 5308. 或运算的最小翻转次数 Minimum Flips to Make a OR b Equal to c

目录

1. 解答

赛题链接 英文赛题 题库本题目链接

题目描述

给你三个正整数 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

解答

python3

先把 int 转成二进制串，python 内置的 bin 函数，转出来的字符串是以 0b 开头，所以用 [2:] 去掉 0b。

然后用 [::-1] 把二进制串反转过来，便于对齐处理。这时候从下标 0 开始，一位一位的比较 a、b、c。

如果 c 是 0：

1. 如果 a 这一位是 1，操作数加 1
2. 如果 b 这一位是 1，操作数加 1

如果 c 是 1：

​ 如果 a 和 b 这一位都是 0 操作数加 1

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        def to_binary_str(num):
            return bin(num)[2:] # bin(b) -> '0b110'
        a2 = to_binary_str(a)[::-1] # reverse str
        b2 = to_binary_str(b)[::-1]
        c2 = to_binary_str(c)[::-1]
        cnt = 0
        for i in range(len(c2)):
            if c2[i] == '0':
                if len(a2) > i and a2[i] == '1':
                    cnt += 1
                if len(b2) > i and b2[i] == '1':
                    cnt += 1
            if c2[i] == '1':
                if (len(a2) <= i or a2[i] == '0') and (len(b2) <= i or b2[i] == '0'):
                    cnt += 1
        for i in range(len(c2), max(len(a2), len(b2))):
            if len(a2) > i and a2[i] == '1':
                cnt += 1
            if len(b2) > i and b2[i] == '1':
                cnt += 1
        return cnt