Processing math: 100%

Leetcode 861 - Score After Flipping Matrix

題目

Problem#

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

測資限制#

  • 1m,n20

想法#

貪心

目標要找最大,所以最左邊的 bit 一定要是 1,如果有一列的最左 bit 是 0 的話,就 flip 整列。接著剩下的行,就看 01 的數量,目標是所有 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;
}
};
view raw leetcode/861.cpp delivered with ❤ by emgithub
  • 時間複雜度: O(mn)
  • 空間複雜度: O(1)