最少翻转次数使二进制矩阵回文I

2024-11-15

题目:

给你一个 m x n 的二进制矩阵 grid

如果矩阵中一行或者一列从前往后与从后往前读是一样的,那么我们称这一行或者这一列是 回文 的。

你可以将 grid 中任意格子的值 翻转 ,也就是将格子里的值从 0 变成 1 ,或者从 1 变成 0

请你返回 最少 翻转次数,使得矩阵 要么 所有行是 回文的 ,要么所有列是 回文的

示例 1:

输入:grid = [[1,0,0],[0,0,0],[0,0,1]]

输出:2

解释:

img

将高亮的格子翻转,得到所有行都是回文的。

示例 2:

输入:grid = [[0,1],[0,1],[0,0]]

输出:1

解释:

img

将高亮的格子翻转,得到所有列都是回文的。

示例 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);
    }
};