首頁 >後端開發 >php教程 >最小數組末尾

最小數組末尾

Linda Hamilton
Linda Hamilton原創
2024-11-14 11:45:02351瀏覽

Minimum Array End

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

提示:

  1. 陣列的每個元素應透過「合併」x 和 v 來獲得,其中 v = 0, 1, 2, …(n - 1)。
  2. 要將 x 與另一個數字 v 合併,請保持 x 的設定位不變,對於所有其他位,從右到左依序填滿 v 的設定位。
  3. 所以最終的答案是 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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn