前往
大廳
主題

LeetCode - 2419. Longest Subarray With Maximum Bitwise AND 解題心得

Not In My Back Yard | 2023-08-13 12:00:07 | 巴幣 0 | 人氣 92

題目連結:


題目意譯:
你被給定一個大小為 n 的整數陣列 nums。

考慮 nums 中一個非空子陣列,其有著最大可能的按位元(Bitwise)AND 之值。

換句話說,令 k 為 nums 中任一子陣列的最大按位元 AND 之值。則,只有按位元 AND 之值等於 k 的子陣列需要被考慮。

回傳此種子陣列最長者之長度。

一個陣列按位元 AND 之值為當中所有數字按位元 AND 之結果。

一個子陣列為一個陣列中的一個連續元素序列。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 6



範例測資:
範例 1:
輸入: nums = [1,2,3,3,2,2]
輸出: 2
解釋:
一個子陣列最大可能的按位元 AND 之值為 3。
有著該值的最長子陣列為 [3,3],所以我們回傳 2。

範例 2:
輸入: nums = [1,2,3,4]
輸出: 1
解釋:
一個子陣列最大可能的按位元 AND 之值為 4。
有著該值的最長子陣列為 [4],所以我們回傳 1。


解題思維:
可以看到最大的按位元 AND 之值會是 nums 中的數字最大值(稱其為 M)。

因此我們只要找到 nums 中 M 最多連續出現幾次即可求得所求最長子陣列。




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

創作回應

更多創作