2025-03-18：最少翻转次数使二进制矩阵回文Ⅱ。用go语言，给定一个大小为 m x n 的二进制矩阵 grid。如果矩阵中

福大大架构师每日一题

发布于 2025-03-18 18:48:37

3600

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-03-17：最少翻转次数使二进制矩阵回文Ⅰ。用go语言，给定一个大小为 m x n 的二进制矩阵 grid。如果矩阵中的某一行或某一列从前往后读和从后往前读是一样的，那么我们称这一行或这一列是回文的。

你可以翻转矩阵中的任意一个格子的值，即将 0 变为 1，或将 1 变为 0。

请返回使得矩阵所有行或所有列成为回文所需的最少翻转次数。

m == grid.length。

n == grid[i].length。

1 <= m * n <= 200000。 0 <= grid[i][j] <= 1。

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

输出：2。

解释：

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

题目来自leetcode3239。

大体步骤如下：

1.计算行回文所需翻转次数：

• 遍历每一行：对每一行进行对称位置的比较。
• 对称位置比较：对于每个元素在位置 j1，其对称位置为 j2 = n-1-j1。若两者不同，则需要翻转其中一个，因此每对不同的位置贡献一次翻转次数。
• 累计行总次数：所有行的不匹配对总数即为将所有行变为回文的最小翻转次数。

2.计算列回文所需翻转次数：

• 遍历每一列：对每一列进行上下对称位置的比较。
• 对称位置比较：对于每个元素在行 i1，其对称位置为 i2 = m-1-i1。若两者不同，同样需要一次翻转。
• 累计列总次数：所有列的不匹配对总数即为将所有列变为回文的最小翻转次数。

3.选择最优解：比较行处理和列处理的总次数，取较小值作为最终结果。

复杂度分析

• 时间复杂度：O(m × n)。需要遍历所有行的对称位置（O(m × n/2)）和所有列的对称位置（O(n × m/2)），总体为线性时间复杂度。
• 额外空间复杂度：O(1)。仅使用固定数量的变量存储中间结果，无需额外空间。

Go完整代码如下：

package main

import (
    "fmt"
)

func minFlips(grid [][]int)int {
    rowCnt, colCnt := 0, 0
    m, n := len(grid), len(grid[0])
    for i := 0; i < m; i++ {
        for j1 := 0; j1 < n / 2; j1++ {
            j2 := n - 1 - j1
            if grid[i][j1] != grid[i][j2] {
                rowCnt++
            }
        }
    }
    for j := 0; j < n; j++ {
        for i1 := 0; i1 < m / 2; i1++ {
            i2 := m - 1 - i1
            if grid[i1][j] != grid[i2][j] {
                colCnt++
            }
        }
    }
    return min(colCnt, rowCnt)
}


func main() {
    grid := [][]int{{1,0,0},{0,0,0},{0,0,1}}
    result := minFlips(grid)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defminFlips(grid):
    m = len(grid)
    if m == 0:
        return0
    n = len(grid[0])
    row_cnt = 0
    for i inrange(m):
        for j1 inrange(n // 2):
            j2 = n - 1 - j1
            if grid[i][j1] != grid[i][j2]:
                row_cnt += 1
    col_cnt = 0
    for j inrange(n):
        for i1 inrange(m // 2):
            i2 = m - 1 - i1
            if grid[i1][j] != grid[i2][j]:
                col_cnt += 1
    returnmin(row_cnt, col_cnt)

# 测试用例
grid = [
    [1, 0, 0],
    [0, 0, 0],
    [0, 0, 1]
]
print(minFlips(grid))  # 输出: 2