日期: 2024 年 11 月 15 日

目标

给你一个 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 * 10^5
• 0 <= grid[i][j] <= 1

思路

有一个二进制矩阵 grid，每次操作可以翻转任意格子，使 0 变为 1，或者使 1 变为 0。求使得矩阵 所有行 或者 所有列 变成回文的最少操作次数。

由于是所有行 或 所有列，每种情况下的翻转次数是确定的，直接返回其最小值即可。

优化点：

• 使用 ⌊n/2⌋ 缩小循环范围，使用 n - 1 - j 代替尾部指针
• 是使用异或运算代替条件判断

代码

/**
 * @date 2024-11-15 9:05
 */
public class MinFlips3239 {

    public int minFlips(int[][] grid) {
        int rowOpts = 0;
        int colOpts = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                rowOpts += grid[i][j] ^ grid[i][n - 1 - j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m / 2; j++) {
                colOpts += grid[j][i] ^ grid[m - j - 1][i];
            }
        }
        return Math.min(rowOpts, colOpts);
    }

}

性能