前往
大廳
主題

LeetCode - 2275. Largest Combination With Bitwise AND Greater Than Zero 解題心得

Not In My Back Yard | 2023-03-29 12:00:01 | 巴幣 1000 | 人氣 123

題目連結:


題目意譯:
一個陣列 nums 的按位元(Bitwise)之 AND 操作為 nums 中所有整數的按位元 AND 之結果。

例如說,對於 nums = [1, 5, 3],按位元 AND 之值等於 1 & 5 & 3 = 1。

而對於 nums = [1, 5, 3],按位元 AND 之值等於 7。

你被給定一正整數陣列 candidates。請對 candidates 的每一種組合求出按位元 AND 之值。candidates 中每一個數字在一個組合中只能使用一次。

回傳有著按位元 AND 之值大於 0 的 candidates 組合之最大的大小為何。

限制:
1 ≦ candidates.length ≦ 10 ^ 5
1 ≦ candidates[i] ≦ 10 ^ 7



範例測資:
範例 1:
輸入: candidates = [16,17,71,62,12,24,14]
輸出: 4
解釋: 組合 [16,17,62,24] 有著按位元 AND 之值 16 & 17 & 62 & 24 = 16 > 0。
該組合的大小為 4。
可以證明沒有其他組合有著大小大於 4 並且滿足按位元 AND 之值大於 0。
注意到可能有多於一個組合有著最大的大小。
例如說,組合 [62,12,24,14] 有著按位元 AND 之值 62 & 12 & 24 & 12 = 8 > 0。

範例 2:
輸入: candidates = [8,8]
輸出: 2
解釋: 最大的組合 [8,8] 有著按位元 AND 之值 8 & 8 = 8 > 0。
該組合的大小為 2,所以我們回傳 2。


解題思維:
掃過 candidates 中所有數字並用一個陣列來統計對於每個位元(2 ^ i)有多少數字的二進位表示法中第 i 個位元為「1」。

接著掃過每一個位元,看哪個位元的統計值最大即為所求(代表我們只要挑該位元對應的原先那些數字 AND 之後便保證 > 0)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作