最小數組末尾

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中文網其他相關文章！