3239. Minimum Number of Flips to Make Binary Grid Palindromic I

Problem

You are given an m x n binary matrix grid.

A row or column is considered palindromic if its values read the same forward and backward.

You can flip any number of cells in grid from 0 to 1, or from 1 to 0.

Return the minimum number of cells that need to be flipped to make either all rows palindromic or all columns palindromic.

https://leetcode.cn/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-i/

Example 1:

Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 2
Explanation:

Flipping the highlighted cells makes all the rows palindromic.

Example 2:

Input: grid = [[0,1],[0,1],[0,0]]
Output: 1
Explanation:

Flipping the highlighted cell makes all the columns palindromic.

Example 3:

Input: grid = [[1],[0]]
Output: 0
Explanation:
All rows are already palindromic.

Constraints:

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

Test Cases

1
2

class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import pytest

from solution import Solution


@pytest.mark.parametrize('grid, expected', [
    ([[1,0,0],[0,0,0],[0,0,1]], 2),
    ([[0,1],[0,1],[0,0]], 1),
    ([[1],[0]], 0),
])
class Test:
    def test_solution(self, grid, expected):
        sol = Solution()
        assert sol.minFlips(grid) == expected

Thoughts

对于一行，从两头往中间逐个比对，不一致的格子对数，就是需要翻转的数量（一对两个格子中翻转任意一个）。

行与行彼此独立，各行需要翻转的数量累加起来就是最终所有行都是回文所需的翻转总数。

同理求出所有列所需要的翻转总数。二者取最小。

时间复杂度 O(m * n)，空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

from typing import List


class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        flip_count_row = 0
        for row in grid:
            for j in range(n >> 1):
                if row[j] != row[-j - 1]:
                    flip_count_row += 1

        flip_count_col = 0
        for j in range(n):
            for i in range(m >> 1):
                if grid[i][j] != grid[-i - 1][j]:
                    flip_count_col += 1

        return min(flip_count_row, flip_count_col)

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章