数组最后一个元素的最小值

2024-08-22

题目:

给你两个整数 nx 。你需要构造一个长度为 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;
    }
};