最小数组末尾

3133。最小数组末尾

难度：中等

主题： 位操作

给定两个整数 n 和 x。您必须构造一个大小为 n 的 正 整数 nums 数组，其中每个 0 大于 nums[i]，nums 所有元素按位与运算的结果为 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。

示例 3：

• 输入：
成本 = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
• 输出：
10

约束：

• ^{1 8}

提示：

数组的每个元素应通过“合并”x 和 v 来获得，其中 v = 0, 1, 2, …(n - 1)。
要将 x 与另一个数字 v 合并，请保持 x 的设置位不变，对于所有其他位，从右到左依次填充 v 的设置位。
所以最终的答案是 x 和 n - 1 的“合并”。

解决方案：

我们需要构造一个大小为 n 的正整数数组 nums，其中每个连续元素都大于前一个元素。 nums 中所有元素的按位与应产生 x。我们被要求找到 nums[n-1] 的最小可能值。

详细内容如下：

1. 位操作洞察

   ：我们可以观察到 nums[i] 应该通过将 x 与整数 0, 1, ..., n-1 合并来构建。这将有助于确保按位与结果产生 x，因为我们以 x 为基数开始。

2. 构建数组元素

   ：每个元素都可以被认为是 x 与某个整数的合并，我们的目标是保持 x 的位完整。我们从整数中填充额外的位以获得递增的数字，同时将 AND 结果保持为 x。

3. 合并策略

   ：要找到最小的nums[n-1]，我们只需要将x与n-1合并。在这种情况下，合并意味着如果 x 中的任何位为 1，则它仍为 1。我们使用 n-1 中的位来添加任何所需的附加位，而不更改 x 中设置的位。

让我们用 PHP 实现这个解决方案：3133。最小数组末尾

<?php
/**
 * @param Integer $n
 * @param Integer $x
 * @return Integer
 */
function minEnd($n, $x) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
echo minimumArrayEnd(3, 4) . "\n";  // Output: 6

// Example 2
echo minimumArrayEnd(2, 7) . "\n";  // Output: 15
?>

解释：

1. 位检查和设置:

   • 我们检查 ans 的每一位（从 x 开始），如果 ans 中的某个位为 0，我们查找 k 中的相应位（即 n-1）。
   • 如果 k 中的该位为 1，我们将 ans 中的位设置为 1。此过程确保值的增量最小，同时保留 x 中设置的位。

2. 循环约束:

   • 我们迭代每个位位置直到计算出的最大值 (kMaxBit)，确保我们覆盖 x 和 n 所需的位。

3. 结果：

   • ans 的最终值为 nums[n-1] 满足条件的最小可能值。

复杂：

• 该算法以恒定时间运行，因为此范围内任何整数的位数都以 32 为界，因此即使对于较大的 n 和 x 值，该方法也非常有效。

该解决方案产生所需的最小 nums[n-1]，同时保持所需的属性。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是最小数组末尾的详细内容。更多信息请关注PHP中文网其他相关文章！