3239.最少翻转次数使二进制矩阵回文 I

【LetMeFly】3239.最少翻转次数使二进制矩阵回文 I：遍历（行和列两种情况分别讨论）

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

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

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

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

请你返回 最少 翻转次数，使得矩阵 要么 所有行是 回文的 ，要么所有列是 回文的 。

 

示例 1：

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

输出：2

解释：

将高亮的格子翻转，得到所有行都是回文的。

示例 2：

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

输出：1

解释：

将高亮的格子翻转，得到所有列都是回文的。

示例 3：

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

输出：0

解释：

所有行已经是回文的。

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m * n <= 2 * 105
• 0 <= grid[i][j] <= 1

解题方法：行列分别计算

如何判断某一行成为回文行至少要翻转几次？

从这一行第一个元素遍历到中间的元素，如果与之相对的那个“回文元素”和这个元素不同，则需要进行一次翻转。

这样就能求出所有行全部成为回文行至少要翻转几次。

同理就能求出所有列全部成为回文列至少要翻转几次。

二者中的最小值即为所求。

• 时间复杂度$O(nm)$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
private:
    int forLine(vector<vector<int>>& grid) {
        int ans = 0;
        int n = grid.size(), m = grid[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m / 2; j++) {
                ans += grid[i][j] != grid[i][m - j - 1];
            }
        }
        return ans;
    }

    int forCol(vector<vector<int>>& grid) {
        int ans = 0;
        int n = grid.size(), m = grid[0].size();
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n / 2; i++) {
                ans += grid[i][j] != grid[n - i - 1][j];
            }
        }
        return ans;
    }
public:
    int minFlips(vector<vector<int>>& grid) {
        return min(forLine(grid), forCol(grid));
    }
};

Python

from typing import List

class Solution:
    def forLine(self, grid: List[List[int]]) -> int:
        ans = 0
        n, m = len(grid), len(grid[0])
        for i in range(n):
            for j in range(m // 2):
                ans += grid[i][j] != grid[i][m - j - 1]
        return ans

    def forCol(self, grid: List[List[int]]) -> int:
        ans = 0
        n, m = len(grid), len(grid[0])
        for j in range(m):
            for i in range(n // 2):
                ans += grid[i][j] != grid[n - i - 1][j]
        return ans

    def minFlips(self, grid: List[List[int]]) -> int:
        return min(self.forLine(grid), self.forCol(grid))

Java

class Solution {
    private int forLine(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m / 2; j++) {
                if (grid[i][j] != grid[i][m - j - 1]) {
                    ans++;
                }
            }
        }
        return ans;
    }

    private int forCol(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n / 2; i++) {
                if (grid[i][j] != grid[n - i - 1][j]) {
                    ans++;
                }
            }
        }
        return ans;
    }

    public int minFlips(int[][] grid) {
        return Math.min(forLine(grid), forCol(grid));
    }
}

Go

package main

func forLine(grid [][]int) (ans int) {
    n, m := len(grid), len(grid[0])
    for i := 0; i < n; i++ {
        for j := 0; j < m / 2; j++ {
            if grid[i][j] != grid[i][m - j - 1] {
                ans++
            }
        }
    }
    return
}

func forCol(grid [][]int) (ans int) {
    n, m := len(grid), len(grid[0])
    for j := 0; j < m; j++ {
        for i := 0; i < n / 2; i++ {
            if grid[i][j] != grid[n - i - 1][j] {
                ans++
            }
        }
    }
    return
}

func minFlips(grid [][]int) int {
    return min(forLine(grid), forCol(grid))
}

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

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

为什么我这次题解写地这么慢，因为我在并行处理行政工作。