力扣题解（最小翻转次数使得二进制矩阵回文II）
给你一个 m x n 的二进制矩阵 grid 。
如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。
你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。
请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。
思路：
首先，考虑回文字符的特点，对称行，列均相等，因此对于对应的两行，两列，一共四条线构成一个口字形，在化成回文后一定是有%4等于0个1，可以想成左上角，右下角，左下角，右上角对应四个，因此模4一定为0，因此对于这些位置，只需要考虑用最小次数翻转成回文就行，1的个数%4等于0一定恒满足。
然后，对于空出来的那一行或者一列（如果行或列是奇数的时候才会有这种情况），还需要额外处理这一行或者列的元素，此处以行为例子说明，列的做法同理。对于行k，需要处理每一列上这一行所在的元素，记录对应位置元素不相等的个数和元素相等且为1的个数，因为这些会对于最后1的个数产生影响，而相等且均为0的对于位置不会对1的个数有影响因此不用记录。假设对应位置不同的情况有diff个，对应相同且为1的元素个数是cnt1个，则如果diff==0时，只需要根据cnt1的情况进行处理就好，具体处理情况就是看cnt1%4的值，如果是2就翻转两个1变成0，如果是零已经满足无需变换。如果diff不为0，那么满足1的个数%4==0的最小翻转方法就是翻转diff次，因为翻转diff次绝对可以使得当前1的个数%4==0，比如diff等于1时，当前1的个数一定是奇数个，是1或者3，是1就将1翻转成0，是3就将0翻转成1，对于大于diff的情况，只需要一个按照上述翻转方法，其余无脑变成0就一定满足1的个数%4==0.
最后考虑特殊情况，如果行/列都是奇数的时候，会出现中心位置额外多出来一个元素，这个元素没有对应的匹配元素，因此只能变成0才行，因为如果是1，最后回文串中1的个数一定是奇数无法满足%4==0的条件。
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);
}
int diff=0,cnt1=0;
if(m&1)
{
for(int i=0;i<n/2;i++)
if(grid[m/2][i]==grid[m/2][n-1-i])
cnt1+=2*grid[m/2][i];
else diff++;
}
if(n&1)
{
for(int i=0;i<m/2;i++)
if(grid[i][n/2]==grid[m-1-i][n/2])
cnt1+=2*grid[i][n/2];
else diff++;
}
if(m&1&&n&1)
{
ans+=grid[m/2][n/2];
}
if (diff > 0) {
ans += diff;//哪怕只有一个diff，对于当前i%4的情况只有可能是1或者3，那么一定可以变成%4等于0
} else {
ans += cnt1 % 4;
}
return ans;
}
};原文地址：https://blog.csdn.net/yyssas/article/details/143811535
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！