当前位置：首页 > article >正文

每日一题3239.最少翻转次数使二进制矩阵回文；

article 2024/11/19 13:47:20

本题出自LeetCode每日一题3239.最少翻转次数使二进制矩阵回文，初看想着就是一道暴力破解，双指针强硬遍历一横一竖

题目

给你一个 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

解题思路

这个问题要求我们在给定的 m x n 的二进制矩阵 grid 中，通过最少的翻转次数（即把某个位置的 0 变成 1 或者 1 变成 0），让所有的行或所有的列都成为回文。要解决这个问题，我们可以采取以下步骤：

定义回文：首先明确什么是回文。对于行来说，如果一个行从左到右读和从右到左读是一样的，那么这个行就是回文的。同样的规则适用于列。

计算翻转次数：

对于每一行，我们可以通过比较第 i 列和第 n-i-1 列（从左端和右端同时向中间靠拢）来检查是否需要翻转。如果这两个位置上的数字不同，则至少需要一次翻转才能使该行成为回文。
同样地，对于每一列，我们可以通过比较第 i 行和第 m-i-1 行来检查是否需要翻转，以确保该列是回文的。

选择最小的翻转次数：我们需要分别计算出使所有行成为回文所需的最少翻转次数，以及使所有列成为回文所需的最少翻转次数。最终的结果应该是这两者中的较小值。

题解

c++代码

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        auto flip = [&](int rows, int cols, bool horizontal) -> int {
            int cnt = 0;
            for (int i = 0; i < rows; ++i) {
                int l = 0, r = cols - 1;
                while (l < r) {
                    if ((horizontal && grid[i][l++] != grid[i][r--]) ||
                        (!horizontal && grid[l++][i] != grid[r--][i])) {
                        ++cnt;
                    }
                }
            }
            return cnt;
        };
        
        return min(flip(m, n, true), flip(n, m, false));
    }
};

详解

获取网格的维度
        int m = grid.size(), n = grid[0].size();
m 表示网格的行数。
n 表示网格的列数。

定义翻转操作的 lambda 函数
        auto flip = [&](int rows, int cols, bool horizontal) -> int {
            int cnt = 0;
            for (int i = 0; i < rows; ++i) {
                int l = 0, r = cols - 1;
                while (l < r) {
                    if ((horizontal && grid[i][l++] != grid[i][r--]) ||
                        (!horizontal && grid[l++][i] != grid[r--][i])) {
                        ++cnt;
                    }
                }
            }
            return cnt;
        };
flip 是一个 lambda 函数，用于计算需要多少次翻转才能使指定方向上的对称元素相等。
rows 和 cols 分别表示要检查的行数和列数。
horizontal 是一个布尔变量，指示是否进行水平翻转。
cnt 用于计数需要翻转的次数。
外层循环遍历每一行（或每一列，取决于 horizontal）。
内层循环使用两个指针 l 和 r 分别从两端向中间移动，比较对应位置的元素是否相等。如果不相等，则增加 cnt 计数器。

返回结果
        return min(flip(m, n, true), flip(n, m, false));
    }
};
调用两次 flip 函数：
第一次调用 flip(m, n, true) 进行水平翻转。
第二次调用 flip(n, m, false) 进行垂直翻转。
返回两者中较小的结果，即最少需要的翻转次数。