Problem#
給你 m×n 的二維陣列 grid
裡面只包含 0
和 1
,你可以對每行、列進行 flip 操作(0
變 1
,1
變 0
),每列可以組成一個 binary 數字,最後加總起來就是分數,你可以 flip 無限次(或不 flip),問你最大的分數是多少。

測資限制#
- 1≤m,n≤20
想法#
貪心
目標要找最大,所以最左邊的 bit 一定要是 1
,如果有一列的最左 bit 是 0
的話,就 flip 整列。接著剩下的行,就看 0
與 1
的數量,目標是所有 1
的數量都要「大於等於」 0
的數量,所以遇到 1
的數量小於 0
的數量的行,就 flip 該行,如此一來便是最大的數字。
加總 m 列即是答案。
AC Code#
Copy
class Solution { public: int matrixScore(vector<vector<int>>& grid) { int n = grid.size(), m = grid[0].size(); // First column must be 1 -> find max for(int i = 0; i < n; i++) if(grid[i][0] == 0) for(int j = 0; j < m; j++) grid[i][j] = 1 - grid[i][j]; // Flip the column if the #0 > #1 for(int i = 1; i < m; i++) { int r = 0; for(int j = 0; j < n; j++) if(grid[j][i]) r++; if(n-r > r) for(int j = 0; j < n; j++) grid[j][i] = 1 - grid[j][i]; } // Compute the answer int ans = 0; for(int i = 0; i < n; i++) { int num = 0; for(int j = 0; j < m; j++) { num <<= 1; num |= grid[i][j]; } ans += num; } return ans; } };
- 時間複雜度: O(mn)
- 空間複雜度: O(1)