【LeetCode】每日一题 2024_11_16 最少翻转次数使二进制矩阵回文 II（矩阵，分类讨论）

前言

每天和你一起刷 LeetCode 每日一题~

本期看点：究极分类讨论

LeetCode 启动！

今天发现力扣多了一个新功能，在题目右下角可以看到同时在线刷题的有几个人：

题目：最少翻转次数使二进制矩阵回文 II

代码与解题思路

先读题：题目要求我们找到把矩阵的行和列全部变成回文且 1 的数量能被 4 整除的最小操作数

怎么样才能满足这个条件呢？

核心操作：让矩阵的四角全变成 1 或者全变成 0（取最小的操作次数）这样既能达成回文，也能达成被 4 整除的条件，接着对特殊情况进行分类讨论：

1、如果矩阵行列都是偶数，直接返回结果就行

2、如果矩阵行列都是奇数，需要增加将中间的 1 改成 0 这个操作（把中间多出来的那个元素处理掉，保证 1 的数量能够被 4 整除）

3、如果矩阵的 行/列 是奇数，那就需要对多出来的那一 行/列 进行特殊处理

如何处理？再进行分类讨论：（可以直接看代码中的解释）

1、如果 1 的数量能整除，直接累加修改次数

2、如果修改过元素，又因为 1 的数量是偶数次出现的，比如出现 2 个 1 或 6 个 1 等情况，那直接修改 diff 次就能符合被 4 整除的这个条件

3、如果没修改过元素，1 的数量又不是 4 的倍数，那就只剩一种情况了，比如出现 2 个 1 或 6 个 1 等情况，直接进行 2 次修改就能被 4 整除了

（可以尝试用样例模拟一下）代码如下：

func minFlips(grid [][]int) (ans int) {
    n, m := len(grid), len(grid[0])

    // 将四角的元素都改成 0 或 1
    for i := 0; i < n/2; i++ {
        for j := 0; j < m/2; j++ {
            x, y := n-1-i, m-1-j
            cnt := grid[i][j]+grid[i][y]+grid[x][j]+grid[x][y]
            ans += min(cnt, 4-cnt)
        }
    }

    // 如果矩阵行列都是奇数，需要增加将中间的 1 改成 0 这个操作
    if n&1 == 1 && m&1 == 1 {
        ans += grid[n/2][m/2]
    }

    // diff 记录需要修改的点，cnt1 记录 1 的数量（因为 1 数量需要被 4 整除）
    diff, cnt1 := 0, 0

    // 如果矩阵的行是奇数
    if n&1 == 1 {
        for j := 0; j < m/2; j++ {
            if grid[n/2][j] == grid[n/2][m-1-j] {
                cnt1 += grid[n/2][j]*2
            } else {
                diff++
            }
        } 
    }

    // 如果矩阵的列是奇数
    if m&1 == 1 {
        for i := 0; i < n/2; i++ {
            if grid[i][m/2] == grid[n-1-i][m/2] {
                cnt1 += grid[i][m/2]*2
            } else {
                diff++
            }
        }
    }

    // 分类讨论：
    // 1、如果 1 的数量能整除，直接累加修改次数
    // 2、如果修改过元素，又因为 1 的数量是偶数次出现的
    // 比如出现 2 个 1 || 6 个 1 等情况，那直接修改 diff 次就能符合被 4 整除的这个条件
    // 3、如果没修改过元素，1 的数量又不是 4 的倍数，那就只剩一种情况了
    // 比如出现 2 个 1 || 6 个 1 等情况，直接进行 2 次修改就能被 4 整除了
    if cnt1%4 == 0 || diff > 0 {
        ans += diff
    } else {
        ans += 2
    }

    // 如果矩阵行列都是偶数，直接返回即可
    return ans
}

每天进步一点点，我们明天不见不散~

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。

原文地址：https://blog.csdn.net/Locky136/article/details/143815512

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