leetcode
leetcode 1951 ~ 2000
转换数字的最少位翻转次数

转换数字的最少位翻转次数

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 15.9 MB


/*
题目思路:
使用 Java Stream API 可以简化位操作的步骤。首先,计算 start 和 goal 的异或值,然后将其转换为二进制字符串,最后统计其中 '1' 的数量。
 */
import java.util.stream.Stream;

public class Solution {
    public int minBitFlips(int start, int goal) {
        // 计算 start 和 goal 的异或结果
        int xor = start ^ goal;
        // 统计 xor 中 '1' 的数量
        return (int) Stream.of(Integer.toBinaryString(xor).split(""))
                            .filter(bit -> bit.equals("1"))
                            .count();
    }
}

解释

方法:

这道题目的思路是利用异或运算的性质。异或运算的结果中,每一个为1的位表示两个数在该位上的数字不同。因此,我们可以对start和goal进行异或运算,然后统计结果中1的个数,这个数量就是需要翻转的位数。

时间复杂度:

O(logn)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么选择异或运算来确定需要翻转的位数?是否有其他算法可以达到相同的目的?
异或运算(XOR)非常适用于这种情况,因为它对于任何两个比特位,当且仅当这两个比特位不相同时,结果为1(即0 XOR 1 = 1 和 1 XOR 0 = 1),相同则为0(即0 XOR 0 = 0 和 1 XOR 1 = 0)。这样,将两个数字进行异或运算后,所有值为1的位就标记了需要翻转的位置。至于其他算法,虽然可以使用其他方法(比如逐位比较),但通常这会更复杂且不如直接使用异或运算来得简洁高效。
🦆
在解释中提到异或的结果中的每一个1代表两个数在该位上数字不同,请问这是异或运算的哪一特性体现?
这是异或运算的基本特性之一,即“不同为1,相同为0”。在二进制运算中,异或操作检查两个比特位,只有在它们不相同的情况下才返回1,相同情况则返回0。因此,通过异或运算得到的结果中的每个1都确切地指出了原始两个数字中相应位置的不同位。
🦆
如果start和goal的值非常接近,是否有更优的方法来计算需要翻转的位数,比如直接比较不同位?
当start和goal的值非常接近时,他们的二进制表示大部分位可能相同,但从算法复杂性和执行效率角度考虑,即使直接进行位比较也不见得比异或运算加计数更优。因为异或操作本身就是逐位比较的高效实现,且异或后统计1的数量(通过`bin(x).count('1')`)在实际执行中非常快速。因此,即使在数值接近的情况下,使用异或运算依然是一个简洁且效率高的方法。

相关问题