ETH官方钱包

前往
大廳
主題

LeetCode - 2411. Smallest Subarrays With Maximum Bitwise OR 解題心得

Not In My Back Yard | 2023-08-08 12:00:04 | 巴幣 0 | 人氣 124

題目連結:


題目意譯:
你被給定一個索引值從 0 開始且長度為 n 的陣列 nums,其由非負整數所組成。對於每個索引值 i 從 0 到 n - 1,你必須判斷出 nums 中從 i 開始(含)的最小非空子陣列之大小,使得該子陣列有著最大的按位元 OR(Bitwise OR)之值。

換句話說,令 Bij 為子陣列 nums[i...j] 的按位元 OR 之值。你需要找到從 i 開始的最小子陣列,使得其按位元 OR 之值等於 max(Bik),其中 i ≦ k ≦ n - 1。

一陣列按位元 OR 之值為當中所有數字按位元 OR 之後的結果。

回傳一個長度為 n 的整數陣列 answer,其中 answer[i] 為從 i 開始的、有著最大按位元 OR 之值的最小子陣列之長度。

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

限制:
n == nums.length
1 ≦ n ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: nums = [1,0,2,1,3]
輸出: [3,3,2,2,1]
解釋:
從任一索引值開始的最大按位元 OR 之值為 3。
- 從索引值 0 開始,可以得到該值的最短子陣列為 [1,0,2]。
- 從索引值 1 開始,可以得到該值的最短子陣列為 [0,2,1]。
- 從索引值 2 開始,可以得到該值的最短子陣列為 [2,1]。
- 從索引值 3 開始,可以得到該值的最短子陣列為 [1,3]。
- 從索引值 4 開始,可以得到該值的最短子陣列為 [3]。
因此,我們回傳 [3,3,2,2,1]。

範例 2:
輸入: nums = [1,2]
輸出: [2,1]
解釋:
- 從索引值 0 開始,可以得到最大按位元 OR 之值的最短子陣列之長度為 2。
- 從索引值 1 開始,可以得到最大按位元 OR 之值的最短子陣列之長度為 1。
因此,我們回傳 [2,1]。


解題思維:
其實跟這題基本一樣(都可以用滑動視窗(Sliding Window)解),而且該題剛好也有用到按位元 OR 之值,不過是往左延伸。所以想要套用類似的作法需要反著掃過 nums。




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

創作回應

更多創作