最佳利益　調整後的分數的最大值 (二進位操作) Leetcode #861

Mae Mu on Unsplash

題目敘述

輸入給定一個二元的二維矩陣grid

也可以翻轉一條ｃｏｌｕｍｎ，讓每個元素的０１反相。

可以操作任意多次。

最後把每條ｒｏｗ視為一條二進位表達式的數字，並且進行加總，得到最後的分數。

請問分數的最大值是多少？

原本的英文題目敘述

測試範例

Example 1:

Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Example 2:

Input: grid = [[0]]
Output: 1

約束條件

Constraints:

• m == grid.length

m代表ｇｒｉｄ的高度

• n == grid[i].length

ｎ代表ｇｒｉｄ的寬度

• 1 <= m, n <= 20

高度ｍ和寬度ｎ都介於　１　～　２０之間。

• grid[i][j] is either 0 or 1.

每個陣列元素都是０或１。

演算法　讓１盡可能多，並且居首位（ＭＳＢ）

分數是row by row的二進位數字加總。

因此，為了分數最大化，推演出幾個想法。

一.

讓ｂｉｔ　１居首位（ＭＳＢ）？

因為１ＸＸＸ　．．．　Ｘ　＞　０ＸＸＸ　．．．　Ｘ

最高位是１永遠會比最高位是０的二進位數字還大，不論後面的分布情況為何。

二.

MSB決定之後，接下來就是讓bit1 盡可能多，為了一致性。

我們採取ｃｏｌｕｍｎ　ｗｉｓｅ的掃描方式，從第二高位掃描到最低位。

每個ｃｏｌｕｍｎ都採取讓１盡可能多的方式。

如果保持原狀的ｂｉｔ１必較多，就保持原狀。

如果反轉的ｂｉｔ１比較多，就反轉。

程式碼　讓１盡可能多，並且居首位（ＭＳＢ）

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        
        h, w = len(grid), len(grid[0])

        # Let MSB of each first column be 1
        score = h

        # Check from second column to last column
        for column in range(1, w):

            # Update score in binary representation
            score <<= 1

            # Option_1
            keep = sum( grid[row][column] ^ grid[row][0] for row in range(h) )

            # Option_2
            flip = h - keep

            # Add best score we can get on current column
            score += max(keep, flip)
        
        return score

複雜度分析

時間複雜度: O(ｈ＊ｗ)

需要一個２Ｄ掃描，掃描每個元素恰好一次。

空間複雜度: O(１)

主要計算都是ｉｎ－ｐｌａｃｅ計算，並且所用到的都是固定尺寸Ｏ(1)的臨時變數。

Reference:

[1] Score After Flipping Matrix - LeetCode