LeetCode 题解工作台
最小异或
给你两个正整数 num1 和 num2 ，找出满足下述条件的正整数 x ： x 的置位数和 num2 相同，且 x XOR num1 的值 最小 注意 XOR 是按位异或运算。 返回整数 x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。 整数的 置位数 是其二进制表示中 1 的数目。 示…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
根据题目描述，我们先求出 的置位数 ，然后从高位到低位枚举 的每一位，如果该位为 ，则将 的对应位设为 ，并将 减 ，直到 为 。如果此时 仍不为 ，则从低位开始将 的每一位为 的位置设为 ，并将 减 ，直到 为 。 时间复杂度 $O(\log n)$，其中 为 和 的最大值。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你两个正整数 num1 和 num2 ，找出满足下述条件的正整数 x ：
x的置位数和num2相同，且x XOR num1的值 最小
注意 XOR 是按位异或运算。
返回整数 x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。
整数的 置位数 是其二进制表示中 1 的数目。
示例 1：
输入：num1 = 3, num2 = 5
输出：3
解释：
num1 和 num2 的二进制表示分别是 0011 和 0101 。
整数 3 的置位数与 num2 相同，且 3 XOR 3 = 0 是最小的。
示例 2：
输入：num1 = 1, num2 = 12
输出：3
解释：
num1 和 num2 的二进制表示分别是 0001 和 1100 。
整数 3 的置位数与 num2 相同，且 3 XOR 1 = 2 是最小的。
提示：
1 <= num1, num2 <= 109
解题思路
方法一：贪心 + 位运算
根据题目描述，我们先求出 的置位数 ，然后从高位到低位枚举 的每一位，如果该位为 ，则将 的对应位设为 ，并将 减 ，直到 为 。如果此时 仍不为 ，则从低位开始将 的每一位为 的位置设为 ，并将 减 ，直到 为 。
时间复杂度 ，其中 为 和 的最大值。空间复杂度 。
class Solution:
def minimizeXor(self, num1: int, num2: int) -> int:
cnt = num2.bit_count()
x = 0
for i in range(30, -1, -1):
if num1 >> i & 1 and cnt:
x |= 1 << i
cnt -= 1
for i in range(30):
if num1 >> i & 1 ^ 1 and cnt:
x |= 1 << i
cnt -= 1
return x
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\log{n}) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to apply greedy strategies to minimize XOR.
- question_mark
Check if they understand how to manipulate individual bits using bitwise operations.
- question_mark
Evaluate how clearly they explain the process of matching set bits and minimizing the XOR result.
常见陷阱
外企场景- error
Forgetting to match the number of set bits between x and num2.
- error
Incorrectly applying XOR operations or not fully understanding their properties.
- error
Failing to ensure that the solution works for all edge cases, including when num1 and num2 are very different.
进阶变体
外企场景- arrow_right_alt
Allow num1 and num2 to be larger or smaller, testing how the algorithm handles different ranges.
- arrow_right_alt
Introduce more complex constraints or multiple test cases to challenge optimization.
- arrow_right_alt
Modify the problem to find the maximum XOR value instead of the minimum.