3094. 使用按位查询猜测数字 II 🔒

题目描述

你需要找到一个在 0 和 2³⁰ - 1 （均包含）之间的数字 n。

有一个预定义的 API int commonBits(int num) 能帮助你完成任务。但挑战是每次你调用这个函数，n 都会以某种方式改变。但是记住，你需要找到的是 n 的 初始值。

commonBits(int num) 的操作如下：

计算 n 和 num 的二进制表示中值相同的二进制位的位的数量 count。
n = n XOR num
返回 count。

返回数字 n。

注意：在这个世界中，所有数字都在 0 和 2³⁰ - 1 之间（均包含），因此在计算公共二进制位时，我们只看那些数字的前 30 个二进制位。

提示：

0 <= n <= 2³⁰ - 1
0 <= num <= 2³⁰ - 1
如果你查询的 num 超出了给定的范围，输出将会是不可靠的。

解法

方法一：位运算

思考

\(\texttt{commonBits}(x)\) 先把 \(n\) 异或上 \(x\)，再返回与 \(n\) 的公共 \(1\) 个数。每次询问会永久改写 \(n\)。

对同一 \(x\) 询问两次，第二次把 \(n\) 变回原值。比较两次返回值可知该位在异或前是否为 \(1\)：先变大说明原来是 \(1\)。

对每一位询问 \(1\ll i\) 两次，按两次计数的大小关系置位。

根据题目描述，我们观察到：

如果我们对同一个数调用两次 commonBits 函数，那么 \(n\) 的值将不会发生变化。
如果我们调用 commonBits(1 << i)，那么 \(n\) 的第 \(i\) 位将会被翻转，即 \(n\) 的第 \(i\) 位为 \(1\) 时，调用后变为 \(0\)，反之亦然。

因此，对于每一位 \(i\)，我们可以调用 commonBits(1 << i) 两次，分别记为 count1 和 count2，如果 count1 > count2，那么说明 \(n\) 的第 \(i\) 位为 \(1\)，否则为 \(0\)。

时间复杂度 \(O(\log n)\)，空间复杂度 \(O(1)\)。

Python3JavaC++Go

# Definition of commonBits API.
# def commonBits(num: int) -> int:


class Solution:
    def findNumber(self) -> int:
        n = 0
        for i in range(32):
            count1 = commonBits(1 << i)
            count2 = commonBits(1 << i)
            if count1 > count2:
                n |= 1 << i
        return n

/**
 * Definition of commonBits API (defined in the parent class Problem).
 * int commonBits(int num);
 */

public class Solution extends Problem {
    public int findNumber() {
        int n = 0;
        for (int i = 0; i < 32; ++i) {
            int count1 = commonBits(1 << i);
            int count2 = commonBits(1 << i);
            if (count1 > count2) {
                n |= 1 << i;
            }
        }
        return n;
    }
}

/**
 * Definition of commonBits API.
 * int commonBits(int num);
 */

class Solution {
public:
    int findNumber() {
        int n = 0;
        for (int i = 0; i < 32; ++i) {
            int count1 = commonBits(1 << i);
            int count2 = commonBits(1 << i);
            if (count1 > count2) {
                n |= 1 << i;
            }
        }
        return n;
    }
};

/**
 * Definition of commonBits API.
 * func commonBits(num int) int;
 */

func findNumber() (n int) {
    for i := 0; i < 32; i++ {
        count1 := commonBits(1 << i)
        count2 := commonBits(1 << i)
        if count1 > count2 {
            n |= 1 << i
        }
    }
    return
}

3094. 使用按位查询猜测数字 II 🔒

题目描述

解法

方法一：位运算

评论