LeetCode 3240.最少翻转次数使二进制矩阵回文 II：分类讨论

🕗 发布于 2024-11-17 14:47 leetcode 矩阵算法题解分类讨论

【LetMeFly】3240.最少翻转次数使二进制矩阵回文 II：分类讨论

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

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是回文的。

你可以将 grid 中任意格子的值翻转，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回最少翻转次数，使得矩阵中所有行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除。

示例 1：

输入：grid = [[1,0,0],[0,1,0],[0,0,1]]

输出：3

解释：

示例 2：

输入：grid = [[0,1],[0,1],[0,0]]

输出：2

解释：

示例 3：

输入：grid = [[1],[1]]

输出：2

解释：

提示：

m == grid.length
n == grid[i].length
1 <= m * n <= 2 * 10⁵
0 <= grid[i][j] <= 1

解题方法：分类讨论

step1: 先不考虑4的倍数个1，计算最小翻转次数

step2: 再考虑1的个数问题：

偶数行偶数列：(1必定是4的倍数个)直接返回
奇数行偶数列：看中间那一行有多少对11和多少对10/01
- 偶数对11：(step1时可以把所有01/10变成00)直接返回
- 奇数对11：看有无10/01：
  - 有10/01：(step1时把中间这一行的其中一对10/01变成11)直接返回
  - 无10/01：(step2必须把一对11变成00)step1结果+2后返回
偶数行奇数列：和奇数行偶数列同理
奇数行奇数列：要看“最中心元素”和“中间行中间列除最中间元素外的部分”两部分
- 最中心元素：
  - 若为1：(必须变为0)step1+1
  - 若为0：step1不变
- 中间行中间列除最中间元素外的部分：类似奇数行偶数列，统计这些元素中所有的11对和10/01对，之后同理
时间复杂度 $O (nm)$
空间复杂度 $O (1)$

不难发现，也可以直接判定是否存在“中间行”和“中间列”进行代码简化。

AC代码

C++ 复杂版

/*
step1: 先不考虑4的倍数个1，计算最小翻转次数

step2: 再考虑1的个数问题：

偶数行偶数列：(1必定是4的倍数个)直接返回
奇数行偶数列：看中间那一行有多少对11和多少对10/01
    + 偶数对11：(step1时可以把所有01/10变成00)直接返回
    + 奇数对11：看有无10/01：
        + 有10/01：(step1时把中间这一行的其中一对10/01变成11)直接返回
        + 无10/01：(step2必须把一对11变成00)step1结果+2后返回
偶数行奇数列：和奇数行偶数列同理
奇数行奇数列：要看“最中心元素”和“中间行中间列除最中间元素外的部分”两部分
    + 最中心元素：
        + 若为1：(必须变为0)step1+1
        + 若为0：step1不变
    + 中间行中间列除最中间元素外的部分：类似奇数行偶数列，统计这些元素中所有的11对和10/01对，之后同理
*/
class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int ans = 0;
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < m / 2; j++) {
                int cnt1 = grid[i][j] + grid[i][m - j - 1] + grid[n - i - 1][j] + grid[n - i - 1][m - j - 1];
                ans += min(cnt1, 4 - cnt1);
            }
        }
        if (n % 2 == 0 && m % 2 == 0) {
            return ans;
        } else if (n % 2 == 1 && m % 2 == 0) {
            int cnt11 = 0, cnt0110 = 0;
            for (int j = 0; j < m / 2; j++) {
                if (grid[n / 2][j] == grid[n / 2][m - j - 1]) {
                    if (grid[n / 2][j] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
            ans += cnt0110;
            if (cnt11 % 2 == 0 || cnt0110 > 0) {
                return ans;
            } else {
                return ans + 2;
            }
        } else if (n % 2 == 0 && m % 2 == 1) {
            int cnt11 = 0, cnt0110 = 0;
            for (int i = 0; i < n / 2; i++) {
                if (grid[i][m / 2] == grid[n - i - 1][m / 2]) {
                    if (grid[i][m / 2] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
            ans += cnt0110;
            if (cnt11 % 2 == 0 || cnt0110 > 0) {
                return ans;
            } else {
                return ans + 2;
            }
        } else {
            if (grid[n / 2][m / 2]) {
                ans++;
            }
            int cnt11 = 0, cnt0110 = 0;
            for (int j = 0; j < m / 2; j++) {
                if (grid[n / 2][j] == grid[n / 2][m - j - 1]) {
                    if (grid[n / 2][j] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
            for (int i = 0; i < n / 2; i++) {
                if (grid[i][m / 2] == grid[n - i - 1][m / 2]) {
                    if (grid[i][m / 2] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
            ans += cnt0110;
            if (cnt11 % 2 == 0 || cnt0110 > 0) {
                return ans;
            } else {
                return ans + 2;
            }
        }
    }
};

C++ 简化版

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int ans = 0;
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < m / 2; j++) {
                int cnt1 = grid[i][j] + grid[i][m - j - 1] + grid[n - i - 1][j] + grid[n - i - 1][m - j - 1];
                ans += min(cnt1, 4 - cnt1);
            }
        }
        if (n % 2 && m % 2) {
            ans += grid[n / 2][m / 2];
        }
        int cnt11 = 0, cnt0110 = 0;
        if (n % 2 == 1) {
            for (int j = 0; j < m / 2; j++) {
                if (grid[n / 2][j] == grid[n / 2][m - j - 1]) {
                    if (grid[n / 2][j] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
        }
        if (m % 2 == 1) {
            for (int i = 0; i < n / 2; i++) {
                if (grid[i][m / 2] == grid[n - i - 1][m / 2]) {
                    if (grid[i][m / 2] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
            
        }
        ans += cnt0110;
        if (cnt11 % 2 == 0 || cnt0110 > 0) {
            return ans;
        } else {
            return ans + 2;
        }
        return ans;
    }
};

Python

from typing import List

class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:
        ans = 0
        n, m = len(grid), len(grid[0])
        for i in range(n // 2):
            for j in range(m // 2):
                cnt1 = grid[i][j] + grid[i][m - j - 1] + grid[n - i - 1][j] + grid[n - i - 1][m - j - 1]
                ans += min(cnt1, 4 - cnt1)
        if n % 2 and m % 2:
            ans += grid[n // 2][m // 2]
        cnt11, cnt1001 = 0, 0
        if n % 2:
            for j in range(m // 2):
                if grid[n // 2][j] == grid[n // 2][m - j - 1]:
                    if grid[n // 2][j] == 1:
                        cnt11 += 1
                else:
                    cnt1001 += 1
        if m % 2:
            for i in range(n // 2):
                if grid[i][m // 2] == grid[n - i - 1][m // 2]:
                    if grid[i][m // 2] == 1:
                        cnt11 += 1
                else:
                    cnt1001 += 1
        ans += cnt1001
        if cnt11 % 2 and not cnt1001:
            ans += 2
        return ans

Java

class Solution {
    public int minFlips(int[][] grid) {
        int ans = 0;
        int n = grid.length, m = grid[0].length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < m / 2; j++) {
                int cnt1 = grid[i][j] + grid[i][m - j - 1] + grid[n - i - 1][j] + grid[n - i - 1][m - j - 1];
                ans += Math.min(cnt1, 4 - cnt1);
            }
        }
        if (n % 2 == 1 && m % 2 == 1) {
            ans += grid[n / 2][m / 2];
        }
        int cnt11 = 0, cnt0110 = 0;
        if (n % 2 == 1) {
            for (int j = 0; j < m / 2; j++) {
                if (grid[n / 2][j] == grid[n / 2][m - j - 1]) {
                    if (grid[n / 2][j] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
        }
        if (m % 2 == 1) {
            for (int i = 0; i < n / 2; i++) {
                if (grid[i][m / 2] == grid[n - i - 1][m / 2]) {
                    if (grid[i][m / 2] == 1) {
                        cnt11++;
                    }
                } else {
                    cnt0110++;
                }
            }
        }
        ans += cnt0110;
        if (cnt11 % 2 == 1 && cnt0110 == 0) {
            ans += 2;
        }
        return ans;
    }
}

Go

package main

func minFlips(grid [][]int) (ans int) {
    n, m := len(grid), len(grid[0])
    for i := 0; i < n / 2; i++ {
        for j := 0; j < m / 2; j++ {
            cnt1 := grid[i][j] + grid[i][m - j - 1] + grid[n - i - 1][j] + grid[n - i - 1][m - j - 1]
            ans += min(cnt1, 4 - cnt1)
        }
    }
    if n % 2 == 1 && m % 2 == 1 {
        ans += grid[n / 2][m / 2]
    }
    cnt11, cnt1001 := 0, 0
    if n % 2 == 1 {
        for j := 0; j < m / 2; j++ {
            if grid[n / 2][j] == grid[n / 2][m - j - 1] {
                if grid[n / 2][j] == 1 {
                    cnt11++
                }
            } else {
                cnt1001++
            }
        }
    }
    if m % 2 == 1 {
        for i := 0; i < n / 2; i++ {
            if grid[i][m / 2] == grid[n - i - 1][m / 2] {
                if (grid[i][m / 2] == 1) {
                    cnt11++
                }
            } else {
                cnt1001++
            }
        }
    }
    ans += cnt1001
    if cnt11 % 2 == 1 && cnt1001 == 0 {
        ans +=2
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143816332

原文地址：https://blog.csdn.net/Tisfy/article/details/143816332

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

上一篇：动态规划-完全背包问题——322.零钱兑换
下一篇：高效管理生产线：哪些项目管理工具最适合制造企业？

《生成式 AI》课程第3講 CODE TASK执行文章摘要的机器人
2.设计一个提示符，使语言模型能够对文章进行总结。1.我们希望你创建一个可以执行文章摘要的机器人。
阅读更多2024-11-17
《生成式 AI》课程第3講 CODE TASK 任务2:角色扮演的机器人
我们希望你设计一个机器人服务，你可以用LM玩角色扮演游戏。与LM进行多轮对话提示:告诉聊天机器人扮演任意角色。后续输入:与聊天机器人交互。
阅读更多2024-11-17
存在重复元素 II
判断数组中是否存在两个。
阅读更多2024-11-17
排列问题方法总结（递归+迭代）
这个代码主要就是讲的是逐步生成结果，然后它主要就是利用了一个递归的思想。首先就是先假设我求出来了前 n -1 个数的排列，然后我作为老板我只需要去排列第 n 个数。它的排法一共有三种，首先就是可以
阅读更多2024-11-17
教资考试题目
政治要强”、“情怀要深”、“视野要广”和（ BCD）不仅仅是对全国思政课教师的要求，也是广大教师强化师德修养、践行使命担当的行动指南。课程评价应将教师和学生在课程开发、实施以及教学过程中的全部情况都纳
阅读更多2024-11-17
【更新至2023】A股上市公司企业突破性创新、渐进性创新数据（2000-2023年）
参考C刊《财经问题研究》胡山（2022）老师的研究，用当年获得授权的发明专利数量加 1 后取自然对数来衡量企业突破性创新 ( Invention);用非发明专利 ( 包括实用新型专利和外观设计专利)
阅读更多2024-11-17
Stable Diffusion Hypernetwork Embedding
本节课程我们讲述了另外两种控制图像输出特征和风格的方法---embedding和hypernetwork，embedding在实践中会经常使用到，尤其在反向提示词中，我们会经常使用一些embeddin
阅读更多2024-11-17
深度学习在边缘检测中的应用及代码分析
边缘通常是指图像中像素灰度值发生急剧变化的地方，这些变化可以是由于物体与背景之间的灰度差异、物体不同表面的灰度差异等原因造成的。从数学角度来看，边缘可以看作是图像灰度函数的不连续点或其导数的极值点。
阅读更多2024-11-17
Vulnhub靶场案例渗透[10]- Momentum2
将文件下载,分析对应代码逻辑，发现请求中包含指定cookie键值对和secure参数就能上传php文件了，同时代码中提示实际cookie这个文件中指定字符串多一位大写字符串在末尾。目录下，经过上传一个
阅读更多2024-11-17
企业网络链路聚合、数据抓包、远程连接访问实验
随着信息技术的飞速发展和企业业务的不断扩大，企业网络面临着越来越多的挑战。其中，网络带宽、数据安全和远程访问等问题尤为突出。为了解决这些问题，我们进行了本次企业网络链路聚合、数据抓包和远程连接访问的实
阅读更多2024-11-17

LeetCode 3240.最少翻转次数使二进制矩阵回文 II：分类讨论

【LetMeFly】3240.最少翻转次数使二进制矩阵回文 II：分类讨论

解题方法：分类讨论

AC代码

C++ 复杂版

C++ 简化版

Python

Java

Go

相关文章