day-83 最少翻转次数使二进制矩阵回文 II

思路
关键在于1的个数要为4的倍数，首先镜像的四个位置肯定一定为4的倍数，如果行和列为奇数则需要单独考虑，如果行和列皆为奇数，那么中心的那个数一定为0

解题过程
再单独考虑如果行和列为奇数，具体参考灵神。如果diff>0，额外把diff加入答案；如果diff=0，额外把num%4加入答案

Code

class Solution {
    public int minFlips(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        for(int i=0;i<m/2;i++){
            for(int j=0;j<n/2;j++){
                int t=grid[i][j]+grid[m-1-i][n-1-j]+grid[m-1-i][j]+grid[i][n-1-j];
                ans+=Math.min(t,4-t);
            }
        }
        if(m%2!=0&&n%2!=0&&grid[m/2][n/2]==1) ans++;
        int diff=0;
        int num=0;
        if(m%2!=0){
            int left=0,right=n-1;
            while(left<right){
                if(grid[m/2][left]!=grid[m/2][right]){
                    diff++;
                }else{
                    num+=grid[m/2][left]*2;
                }
                left++;
                right--;
            }
        }


        if(n%2!=0){
            int top=0,bot=m-1;
             while(top<bot){
                if(grid[top][n/2]!=grid[bot][n/2]){
                  diff++;
                }else{
                    num+=grid[top][n/2]*2;    
                }
                top++;
                bot--;
            }
        }
        return ans+(diff>0?diff:num%4);
    }
}

作者：菜卷
链接：https://leetcode.cn/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/solutions/2990702/zui-shao-fan-zhuan-ci-shu-shi-er-jin-zhi-i9vh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

原文地址：https://blog.csdn.net/qq_53568730/article/details/143822061

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