来LeetCode练下思维吧

3239.最少翻转使二进制矩阵回文|

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

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

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

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

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m * n <= 2 * 10^5
• 0 <= grid[i][j] <= 1

这题没什么好说的，在我看来难度应该改成简单。直接去暴力检查一遍就行了，m * n 只有 200000 肯定能过

代码

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int cnt1 = 0, cnt2 = 0;
        for(int i = 0;i < m;i ++){
            int l = 0, r = n - 1;
            while(l < r){
                if(grid[i][l] != grid[i][r]) cnt1 ++;
                l ++, r --;
            }
        }
        for(int i = 0;i < n;i ++){
            int l = 0, r = m - 1;
            while(l < r){
                if(grid[l][i] != grid[r][i]) cnt2 ++;
                l ++, r --;
            }
        }
        return min(cnt1, cnt2);
    }
};

3240.最少翻转使二进制矩阵回文||

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

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

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

请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m * n <= 2 * 10^5
• 0 <= grid[i][j] <= 1

当有“矩阵中 1 的数目可以被 4 整除 。”这个限制的时候，这个题就要思考了

首先我们去枚举每个点，然后去看每个点的“镜像”位置，如图

你可以发现每个相同图案位置上的元素必须要是一致的才能回文，所以第一步我们就去统计最少需要多少步使得这些图案所对应的元素都是一样的。

这里其实一个点对应4个位置，统计一下这四个位置有多少 1（cnt） 即可，变成一样的话就是  min（cnt（全变成0）， 4 - cnt（全变成1））

然后请看

对于孤立的中间列，孤立的中间行（当行、列长度是奇数时才有）需要去特判一下。首先对于中心点必须是 0 （行列长度都是奇数时存在），因为所有的点都是关于他对称的。然后去枚举孤立行和孤立列中不对称的组数有多少(diff),在枚举对称时 1 的个数（num）

如果 num % 4 == 0 那满足条件了不用管，反之就要挑一组 dif f出来都变成 1 即可

代码

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        for(int i = 0;i < m / 2;i ++){
            for(int j = 0;j < n / 2;j ++){
                int cnt = grid[i][j] + grid[i][n - j - 1] + grid[m - i - 1][j] + grid[m - i - 1][n - j - 1];
                ans += min(cnt, 4 - cnt);
            }
        }
        if((m & 1) && (n & 1)) ans += grid[m / 2][n / 2];
        int one = 0, diff = 0;
        if(m & 1){
            for(int i = 0, j = n - 1;i < n && i < j;i ++, j --){
                if(grid[m / 2][i] != grid[m / 2][j]) diff += grid[m / 2][i] + grid[m / 2][j];
                else{
                    if(i == j) continue;
                    one += grid[m / 2][i] + grid[m / 2][j];
                }
            }
        }
        if(n & 1){
            for(int i = 0, j = m - 1;i < m && i < j;i ++, j --){
                if(grid[i][n / 2] != grid[j][n / 2]) diff += grid[i][n / 2] + grid[j][n / 2];
                else{
                    if(i == j) continue;
                    one += grid[i][n / 2] + grid[j][n / 2];
                }
            }
        }
        return ans + (diff ? diff : one % 4);
    }
};

加油

原文地址：https://blog.csdn.net/AuRoRamth/article/details/143815854

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