LeetCode 3022. Minimize OR of Remaining Elements Using Operations

January 30, 2024

周賽382。

題目

輸入整數陣列 nums，還有整數 k。

每次操作，你可以選擇一個滿足 0 <= i < nums.length - 1 的索引 i，然後將 nums[i] 和 nums[i+1] 替換成 nums[i] & nums[i + 1] 的值。& 指的是位元 AND 運算。

求最多 k 次操作後，將 nums 剩餘所有元素做 OR 運算後的最小值。

解法

老樣子，碰到位元運算的題目，把每個位元分開來處理，叫做拆位。
以下討論都是對於單獨第 i 位元。

每次操作可以挑兩個相鄰數做 AND ，合併成一個數。
AND 運算只有當兩個位元都是 1 時，結果才會是 1，否則都是 0。運算結果只減不增。

最後剩下的數都要做 OR 運算。
OR 運算只有兩個位元都是 0 時，結果才會是 0，否則都是 1。運算結果只增不減，跟 AND 剛好相反。

也就是說，只要 nums 中存在任意一個數字的有 1 位元，那麼最終結果肯定是 1。
所以想要確保最終 OR 結果是 0，則一定要把有 1 的數全部清掉。

這下題目轉換成：找到操作可刪除的最大值。

操作是 AND 運算。要想清掉有 1 的數，則必須找隔壁的 0來做 AND。
如果有一連串的 1 構成子陣列，那麼從左方(或右方)的 0 開始做 AND，每個 1 正好需要一次操作。
我們只要計算 nums 中有幾個數有 1，就是刪除這位元的操作次數。

注意：如果全部數都是 1、沒有半個 0，這樣是無法讓結果變成 0 的。
除此之外，這些連續的 1所組成的子陣列，其左邊或右邊肯定有一個 0。

試想以下例子：

nums = [0b10, 0b00, 0b01], k = 1 想消掉第 0 位，需要一次操作
想消掉第 1 位，也需要一次操作

兩個位元各需要一次操作，且操作位置不相同。
為了使答案最小化，我們優先選擇較高的位元，能夠將結果減去更大的值。
因此我們應該從最高位元(MSB) 向下枚舉，判斷各位元能否成功刪除。

選擇 nums[0] AND nums[1]
nums = [0b00, 0b01]
ans = 0b01 = 1

剛才的例子是操作範圍不同，但有時候其實是重疊的範圍，一次操作可以同時消掉多個位元：

nums = [0b11, 0b00], k = 1
只要一次操作，可以同時消掉第 0, 1 位
ans = 0b00

又有時候高位元所需的操作次數超過 k，無法刪除。這時候只能考慮較低的位元：

nums = [0b11, 0b10, 0b10], k = 1
第 1 位無法刪除，直接忽略
nums = [0b_1, 0b_0, 0b_0]
選擇 nums[0] AND nums[1]
nums = [0b10, 0b10]
ans = 0b10 = 2

這樣看來，拆位並沒辦法得到正確答案。我們應該同時考慮多個位元。

在位元操作的題型，常常使用遮罩(bit mask) 進行過濾，只留下我們在乎(想刪除)的位元。
設變數 ans 代表確定可以刪除的位元，初始值為 0。

雖然剛才討論過拆位不可行，但是從大到小貪心地枚舉位元還是正確的。
枚舉第 i 位時，要試著在能刪除 ans大前提之下，也順便把第 i 位刪除。
因此遮罩 mask = ans & (1 « i)，之後遍歷 nums 時，其中每個數 x 都必須先和 mask 做 AND，只留下在乎的位元，其他都會變成 0，不影響答案。
如果能順利在不超過 k 次操作內，將 mask 裡面的所有位元都清除，則更新 ans 為 mask。

至於如何計算操作次數？剛才已經討論過拆位的情形：把有 1 的連續子陣列找出來，操作次數就是子陣列長度總和。
現在改成同時考慮多個位元，因此子陣列分組條件改成AND 結果不為 0。在遍歷 x 的過程中不斷做 AND，只要結果不為 0，則操作次數加1；成功變成 0，則將結果初始化，等待下一個子陣列的開頭元素。
本題測資範圍內最多有 30 個位元，因此初始值等於二進位表示法中的 30 個 1，也就是 (2^30) - 1。

最後得出的 ans 就是可刪除的位元最大值，從 30 個 1 扣掉 ans 就是最終答案。

時間複雜度 O(N log MX)，其中 MX = max(nums)，此為 10^9。
空間複雜度 O(1)。

細心的同學可能會想起來，剛才說過某位元沒有 0 的話沒辦法刪除，怎麼沒有特別判斷？
本題中有規定 k < nums.length，依照上述邏輯，沒法刪除的話得到的操作數 ops 會正好等於 nums.length，不會觸發更新答案的條件。

如果 k 沒有這個限制的話，可能就要額外將 nums 中所有數先 AND 起來，判斷結果是否為 0。

class Solution:
    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
        ans = 0 # maximum bits we can delete
        
        for i in reversed(range(30)):
            mask = ans | (1 << i) # try to delete ans, and i-th bit
            ops = 0
            val = -1 # init subarray value, equals to (1 << 30) - 1
            for x in nums:
                x &= mask # all the bits we care about x
                val &= x # subarray AND with x
                if val == 0: # can delete all bits in mask
                    val = -1
                else: # need more ops to delete bits    
                    ops += 1
                
            if ops <= k:
                ans = mask
                    
        return (1 << 30) - 1 - ans

mocowcow

題目

解法