按位與大於零的最大組合

Susan Sarandon
發布: 2024-11-07 22:24:03
原創
597 人瀏覽過

Largest Combination With Bitwise AND Greater Than Zero

2275。按位與大於零的最大組合

難度:

主題:陣列、雜湊表、位元運算、計數

陣列 nums 的位元與是 nums 中所有整數的位元與。

  • 例如,對於 nums = [1, 5, 3],按位與等於 1 & 5 & 3 = 1。
  • 此外,對於 nums = [7],位元 AND 為 7。

給你一個正整數候選數組。評估候選數字的每個組合按位與。候選中的每個數字在每個組合中只能使用一次

回傳最大候選組合的大小,位元與大於大於0

範例1:

  • 輸入: 候選人 = [16,17,71,62,12,24,14]
  • 輸出: 4
  • 解釋: 組合 [16,17,62,24] 的位元與為 16 & 17 & 62 & 24 = 16 > 0。
    • 組合的大小是4。
    • 可以證明,大小大於 4 的組合的位元與大於 0。
    • 請注意,可能有多個組合具有最大尺寸。
    • 例如,組合 [62,12,24,14] 的位元與為 62 & 12 & 24 & 14 = 8 > 0.

範例2:

  • 輸入:候選人= [8,8]
  • 輸出: 2
  • 解釋: 最大組合 [8,8] 的位元與為 8 & 8 = 8 > 0。
    • 組合的大小是 2,所以我們回傳 2。

約束:

  • 1 5
  • 1 7

提示:

  1. 要讓位元 AND 大於零,組合中的每個數字至少有一位為 1。
  2. 候選者有 24 位長,因此對於每個位位置,我們可以計算最大組合的大小,這樣按位 AND 將在該位位置得到 1。

解:

我們需要專注於識別數字組,其中二進位表示中至少有一位位置在組合中的所有數字中保持設定 (1)。

解決方案概要

  1. 位元分析:由於candidates中的每個數字都可以用最多24位的二進制數表示(如1

  2. 計算每個位置的設定位:對於每個位元位置,計算候選中有多少個數字將該位元設為 1。如果多個數字在同一位置共用一個位,則它們可以可能會在該位位置與大於零的按位 AND 形成組合。

  3. 找出最大計數:在任何給定位置具有一組位的數字的最大數量將是答案,因為它代表按位與結果大於的最大可能組合零。

例子

考慮候選人 = [16, 17, 71, 62, 12, 24, 14]:

  • 將每個數字轉換為二進位並分析位元位置。
  • 計算所有數字中每個位元被設定的次數。
  • 找出所有位元位置的最大計數。

讓我們用 PHP 實作這個解:2275。位元與大於零的最大組合

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

// Example usage
$candidates = [16, 17, 71, 62, 12, 24, 14];
echo largestCombination($candidates); // Output: 4
?>
登入後複製

解釋:

  1. 循環每個位元位置:我們迭代從 0 到 23 的每個位元位置。
  2. 使用位集計數數字:對於每個位置,計算候選者中有多少個數字具有該特定位集。
  3. 更新最大組合大小:追蹤所有位元位置的最高計數。
  4. 傳回結果:根據需要,結果是位元與大於零的最大組合大小。

複雜性分析

  • 時間複雜度: O(n x 24) = O(n),其中n 是候選人中的元素,因為我們對每個數字執行24 次運算(每個位元位置一次)。
  • 空間複雜度O(1),因為我們只使用固定數量的額外空間。

這種方法足以有效地處理輸入大小限制(candidates.length 5)。

聯絡連結

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

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

  • 領英
  • GitHub

以上是按位與大於零的最大組合的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:dev.to
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板