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

本题出自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），让所有的行或所有的列都成为回文。要解决这个问题，我们可以采取以下步骤：

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

2. 计算翻转次数：

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

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

---

题解 

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) 进行垂直翻转。
• 返回两者中较小的结果，即最少需要的翻转次数。

  

---

 制作不易，您的关注与点赞是我最大的动力！ 

原文地址：https://blog.csdn.net/yzxyy_zzb/article/details/143809638

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！