题目:
给你一个 m x n
的二进制矩阵 grid
。
如果矩阵中一行或者一列从前往后与从后往前读是一样的,那么我们称这一行或者这一列是 回文 的。
你可以将 grid
中任意格子的值 翻转 ,也就是将格子里的值从 0
变成 1
,或者从 1
变成 0
。
请你返回 最少 翻转次数,使得矩阵 要么 所有行是 回文的 ,要么所有列是 回文的 。
示例 1:
输入:grid = [[1,0,0],[0,0,0],[0,0,1]]
输出:2
解释:
将高亮的格子翻转,得到所有行都是回文的。
示例 2:
输入:grid = [[0,1],[0,1],[0,0]]
输出:1
解释:
将高亮的格子翻转,得到所有列都是回文的。
示例 3:
输入:grid = [[1],[0]]
输出:0
解释:
所有行已经是回文的。
提示:
m == grid.length
n == grid[i].length
1 <= m * n <= 2 * 105
0 <= grid[i][j] <= 1
思路:
我们可以分别考虑将所有行变为回文所需要的翻转次数 rowCnt 或将所有列变为回文所需要的翻转次数 colCnt,那么所需要的最少反转次数就是 min(rowCnt, colCnt)。
可以使用双指针同时从一行或一列的开头和结尾开始枚举,如果两个指针指向的矩阵元素不同,那么所需要的翻转次数就增加 1。使用双指针遍历矩阵的每一行和每一列,就能够得到 rowCnt 和 colCnt。
代码:
class Solution {
public:
int getRowCnt(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int i = 0; i < m; i++) {
int left = 0, right = n - 1;
while (left < right) {
if (grid[i][left] != grid[i][right]) ans++;
left++;right--;
}
}
return ans;
}
int getColCnt(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for (int j = 0; j < n; j++) {
int top = 0, dowm = m - 1;
while (top < dowm) {
if (grid[top][j] != grid[dowm][j]) ans++;
top++;dowm--;
}
}
return ans;
}
int minFlips(vector<vector<int>>& grid) {
int rowAns = getRowCnt(grid);
int colAns = getColCnt(grid);
return min(rowAns,colAns);
}
};