計算最大按位或子集的數量

2044。計算最大位元或子集的數量

難度：中

主題：陣列、回溯、位元操作、枚舉

給定一個整數數組nums，找到nums 子集最大可能的按位或，並回傳不同非空子集的數量最大位元或.

如果可以透過刪除 b 的一些（可能為零）元素從 b 得到 a，則數組 a 是數組 b 的 子集。如果所選元素的索引不同，則兩個子集被視為不同。

陣列 a 的位元或等於 a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed)。

範例1：

• 輸入： nums = [3,1]
• 輸出： 2
• 解釋： 子集的最大可能位元或為 3。有 2 個子集的位元或為 3：
  • [3]
  • [3,1]

範例2：

• 輸入： nums = [2,2,2]
• 輸出： 7
• 解釋： [2,2,2] 的所有非空子集都以位元或為 2。總共有 23 - 1 = 7 個子集。

範例 3：

• 輸入： nums = [3,2,1,5]
• 輸出： 6
• 解釋： 子集的最大可能位元或為 7。按位或為 7 的子集有 6 個：
  • [3,5]
  • [3,1,5]
  • [3,2,5]
  • [3,2,1,5]
  • [2,5]
  • [2,1,5]

約束：

• 1
• 1 5

提示：

1. 我們可以列舉所有可能的子集嗎？
2. 最大位元或是整個陣列的位元或。

解：

我們可以按照以下步驟操作：

1. 計算最大位元或：子集的最大位元或可以透過對陣列的所有元素執行位元或運算來確定。這給了我們最大可能的按位或。

2. 列舉所有子集：由於陣列的大小很小（最多 16 個），因此我們可以使用位元操作技術列舉所有可能的子集。對於大小為 n 的數組，有 2^n 個可能的子集。

3. 計算有效子集：對於每個子集，計算其按位或併檢查它是否與最大按位或匹配。如果是，則增加一個計數器。

讓我們用 PHP 實作這個解決方案：2044。計算最大位元或子集的數量

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function countMaxBitwiseORSubsets($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$nums1 = [3, 1];
echo countMaxBitwiseORSubsets($nums1) . "\n"; // Output: 2

$nums2 = [2, 2, 2];
echo countMaxBitwiseORSubsets($nums2) . "\n"; // Output: 7

$nums3 = [3, 2, 1, 5];
echo countMaxBitwiseORSubsets($nums3) . "\n"; // Output: 6
?>

解釋：

1. 最大位元或計算:

   • 我們使用循環透過對每個元素執行位元或來計算陣列的最大位元或。

2. 子集枚舉:

   • 我們循環遍歷 1 到 2^n - 1 之間的所有數字（其中 n 是 nums 的長度），代表所有非空子集。
   • 對於每個數字，我們檢查每一位以查看子集中包含哪些元素。

3. 有效子集計數:

   • 計算目前子集的位元或之後，我們檢查它是否等於 maxOR。如果是，我們就會增加計數器。

考慮到限制條件，該解決方案非常高效，並且應該適用於大小最多 16 的數組，最多可評估 65,535 個子集。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是計算最大按位或子集的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！