JZX轻语:简
LeetCode 3240 - 最少翻转次数使二进制矩阵回文 II
发表于2024年08月09日
在3239的基础上,条件升级为行回文且列回文,且1
的次数必须被4
整除。分析可知,由于两种方向都对称,每个元素都可能会有3
个镜像位置,也就是题目中为什么要求能被4
整除: 无论该位置是0
还是1
,通过翻转满足题目要求后,这四个位置要么全0
,要么全1
,1
的个数都会被4
整除。这样就解决了吗?并不是!我们还需要考虑奇数行和奇数列的情况:
如果行数和列数都是奇数,那么中心位置必须为
0
,否则1
的个数不可能被4
整除。如果行或列为奇数,我们需要考虑中心行和中心列: 在中心行/列中,除了最中央的元素(只有行和列都为奇数的时候,才会有这个元素)外,每个元素有
1
个镜像位置。我们可以统计中央行和列的1
的个数,以及不对称的位置对个数。然后使用贪心的方法计算最少翻转次数: 首先考虑保证对称的情况,此时需要翻转的次数为不对称位置对的个数;然后再考虑能被4
整除的情况,此时需要翻转的次数为min(4, 4 - (1的个数 % 4))
。我们需取两种情况的最大值即可保证两种情况都能满足!
证明为啥取最大值即可:首先证明情况1和情况2的翻转次数的奇偶性是一样的:首先,如果某个对称位置对的数字是一样的,则要么全0
,要么全1
,这些已经保持对称的位置对集合中,0
和1
的个数为偶数。而不对称的位置对中,必定恰好有一个为0
,有一个为1
,所以此时这些集合中0
和1
的个数恰好为不对称位置对数
。
- 如果情况1的翻转次数比情况2多:
- 如果情况2的翻转策略为
0 -> 1
,对于每个不对称位置对,我们可以将其中的0
翻转为1
,优先保证1
的计数能被4
整除。此时,由于两种情况的翻转次数奇偶性相同,所以情况1剩余的翻转次数必定为偶数,此时可以交替翻转(一个对0 -> 1
;另一个对1 -> 0
, …),能保证使得1
的计数不会变化! - 如果情况2的翻转策略为
1 -> 0
,雷同。
- 如果情况2的翻转策略为
- 如果情况2的翻转次数比情况1多,不难得知,情况2的翻转次数只会有
0, 1, 2
,如果为1
,根据奇偶性相同,情况1所需翻转次数必然也为1
,此时根据情况2的策略,对那个不对称位置对进行相应翻转即可;如果为2
,则情况1的翻转次数要么为0
,要么为2
。如果为0
,随便选一个已经对称的位置对,全都改为0
或1
即可;如果为2
,则该两个不对称位置对都按照情况1的策略进行翻转即可。
class Solution:
def minFlips(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
ans = 0
# 先遍历有3个镜像位置的情况
for i in range(m // 2):
for j in range(n // 2):
one_cnt = (
grid[i][j] +
grid[m - i - 1][j] +
grid[i][n - j - 1] +
grid[m - i - 1][n - j - 1]
)
ans += min(one_cnt, 4 - one_cnt)
# 处理中心位置
if m % 2 and n % 2:
ans += grid[m // 2][n // 2] == 1
grid[m // 2][n // 2] = 0
# 处理中心行和列
one_cnt = 0
rev_pair_cnt = 0
if m % 2: # 有中心行
one_cnt += sum(grid[m // 2][j] for j in range(n))
rev_pair_cnt += sum(grid[m // 2][j] != grid[m // 2][n - j - 1] for j in range(n // 2))
if n % 2: # 有中心列
one_cnt += sum(grid[i][n // 2] for i in range(m))
rev_pair_cnt += sum(grid[i][n // 2] != grid[m - i - 1][n // 2] for i in range(m // 2))
# 保证对称的最少翻转次数
diff = one_cnt % 4
diff = min(diff, 4 - diff)
# 保证能被4整除的最少翻转次数为rev_pair_cnt
# 两种情况取最大值
return ans + max(diff, rev_pair_cnt)
2024/11/16更新:每日一题遇到了这道题,使用C++重新做了一遍。在处理中心行/列的时候,和上面的做法有点差异:统计不对称位置对的个数need_rev_pair_cnt
和1
对称位置对的个数one_pair_cnt
。
- 如果
1
对称位置对的个数one_pair_cnt
为奇数,且不对称位置对的个数need_rev_pair_cnt
为0
或者1
(此时满足one_pair_cnt % 2 + need_rev_pair_cnt == 1
):则根据need_rev_pair_cnt
的取值:- 如果为
0
(即不存在不对称的位置对),则需要翻转2
次(翻转1
对称位置对中的其中一对为0
); - 如果为
1
,则需要翻转1
次(翻转不对称位置对中的0
为1
);
- 如果为
- 否则(即
one_pair_cnt + need_rev_pair_cnt > 1
):则只需要翻转need_rev_pair_cnt
次(即只翻转不对称的位置对中的其中一员)即可。翻转策略如下:首先,优先翻转0
为1
,使得1
的个数能被4
整除;然后再翻转1
为0
。由于one_pair_cnt + need_rev_pair_cnt > 1
,所以总能找到合适的策略。
class Solution {
public:
int minFlips(vector<vector<int>>& grid) {
int ans = 0;
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m / 2; ++i) {
for (int j = 0; j < n / 2; ++j) {
int one_cnt = grid[i][j] + grid[m - 1 - i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][n - 1 - j];
ans += min(one_cnt, 4 - one_cnt);
}
}
if (m % 2 && n % 2 && grid[m / 2][n / 2]) { ++ans; grid[m / 2][n / 2] = 0; }
int need_rev_pair_cnt = 0, one_pair_cnt = 0;
if (m % 2) {
for (int i = 0; i < n / 2; ++i) {
if (grid[m / 2][i] != grid[m / 2][n - 1- i]) ++need_rev_pair_cnt;
else if (grid[m / 2][i] == 1) ++one_pair_cnt;
}
}
if (n % 2) {
for (int i = 0; i < m / 2; ++i) {
if (grid[i][n / 2] != grid[m - 1 - i][n / 2]) ++need_rev_pair_cnt;
else if (grid[i][n / 2] == 1) ++one_pair_cnt;
}
}
if (one_pair_cnt % 2 + need_rev_pair_cnt == 1) {
ans += need_rev_pair_cnt ? 1 : 2;
} else {
ans += need_rev_pair_cnt;
}
return ans;
}
};