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

English Version

题目描述

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

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

commonBits(int num) 的操作如下：

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

返回数字 n。

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

 

示例 1：

输入：n = 31

输出：31

解释：可以证明，使用提供的 API 可以找到 31。

示例 2：

输入：n = 33

输出：33

解释：可以证明，使用提供的 API 可以找到 33。

 

提示：

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

解法

方法一：位运算

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

• 如果我们对同一个数调用两次 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)$。

# 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
}