LeetCode 1318. 或运算的最小翻转次数

Table of Contents

中文版：

英文版：

My answer:

解题报告：

中文版：

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

英文版：

1318. Minimum Flips to Make a OR b Equal to c

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).

Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example 1:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (
a
 OR 
b
 == 
c
)

Example 2:

Input: a = 4, b = 2, c = 7
Output: 1

Example 3:

 Input: a = 1, b = 2, c = 3
 Output: 0

My answer:

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        binA = bin(a)[2:]
        binB = bin(b)[2:]
        binC = bin(c)[2:]
        lenA = len(binA)
        lenB = len(binB)
        lenC = len(binC)
        max_len = max(lenA, lenB, lenC)
        binA = '0'*(max_len-lenA) + binA
        binB = '0'*(max_len-lenB) + binB
        binC = '0'*(max_len-lenC) + binC
        ans = 0
        for i in range(len(binC)):          
            if binC[i] == '0':
                if binA[i] == '1' and binB[i] == '1':
                    ans += 2
                elif binA[i] == '1' or binB[i] == '1':
                    ans += 1
            elif binA[i] == '0' and binB[i] == '0':
                ans+=1
        return ans
"""
2
6
5
4
2
7
1
2
3
7
8
15
"""

Constraints:

1 <= a <= 10^9

1 <= b <= 10^9

1 <= c <= 10^9

解题报告：

1、把 a, b, c  的值都转换为二进制，Python 有可直接调用的函数 bin()，生成结果为字符串类型，且前边带两位 '0b'，所以从第三位开始取数，即 [2:]。

2、由于 a b c 的数值转换为二进制之后位数可能不同，所以要进行位数对齐，选取位数最长的一个对齐。

2、题目为或运算，即：只要有1，结果就为1。所以查看 a|b 之后的结果与 c 进行按位对比。按照 c 值每一位为 0  或 1 分开讨论，如果 c 中某位为0，则 a, b 对应位不应该有 1；如果c 中某位为 1 而 a, b 对应位都为 0，则有一位要转为1。