当前位置：首页 > article >正文

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

article 2024/11/17 14:24:34

【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 * 10⁵
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))
}