JZX轻语:简

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

发表于2024年08月09日

#贪心 #矩阵

在3239的基础上,条件升级为行回文列回文,且1的次数必须被4整除。分析可知,由于两种方向都对称,每个元素都可能会有3个镜像位置,也就是题目中为什么要求能被4整除: 无论该位置是0还是1,通过翻转满足题目要求后,这四个位置要么全0,要么全11的个数都会被4整除。这样就解决了吗?并不是!我们还需要考虑奇数行和奇数列的情况:

证明为啥取最大值即可:首先证明情况1和情况2的翻转次数的奇偶性是一样的:首先,如果某个对称位置对的数字是一样的,则要么全0,要么全1,这些已经保持对称的位置对集合中,01的个数为偶数。而不对称的位置对中,必定恰好有一个为0,有一个为1,所以此时这些集合中01的个数恰好为不对称位置对数

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_cnt1对称位置对的个数one_pair_cnt

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;
    }
};

闪念标签:LC

题目链接:https://leetcode.cn/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/