题目:
给你两个整数 n
和 x
。你需要构造一个长度为 n
的 正整数 数组 nums
,对于所有 0 <= i < n - 1
,满足 nums[i + 1]
大于 nums[i]
,并且数组 nums
中所有元素的按位 AND
运算结果为 x
。
返回 nums[n - 1]
可能的 最小 值。
示例 1:
输入:n = 3, x = 4
输出:6
解释:
数组 nums
可以是 [4,5,6]
,最后一个元素为 6
。
示例 2:
输入:n = 2, x = 7
输出:15
解释:
数组 nums
可以是 [7,15]
,最后一个元素为 15
。
提示:
1 <= n, x <= 108
思路:
目标是构造数组,数组中所有元素的 AND 结果是 x, 没有思路的主要原因是一下需要构造 n 个数字,这是没有直接抓手的
没有思路时就需要从已经条件发掘, AND 操作就是已知条件, 多个元素 AND, 只有该位上全是1,才能做到 结果位是 1, 那么要想 数组元素 AND 结果是 x, 那么 x 的bit位上为 1 的, x 的数组元素那位也是 1。
那么可以提供给我们变化的就是 x 的bit位为 0 的位,其中第一个最小的一定是那些位置全是 0, 然后逐步增长即可。
具体实现直接看代码吧,我真不知道怎么自然语言描述了
代码:
class Solution {
public:
long long minEnd(int n, int x) {
n--; // 先把 n 减一,这样下面讨论的 n 就是原来的 n-1
long long ans = x;
int i = 0, j = 0;
while (n >> j) {
// x 的第 i 个比特值是 0,即「空位」
if ((ans >> i & 1) == 0) {
// 空位填入 n 的第 j 个比特值
ans |= (long long) (n >> j & 1) << i;
j++;
}
i++;
}
return ans;
}
};