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

Leetcode打卡：最少翻转次数使二进制矩阵回文II

article 2024/11/20 6:51:15

执行结果：通过

题目：3240 最少翻转次数使二进制矩阵回文II

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

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

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

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

示例 1：

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

输出：3

解释：

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

输出：2

解释：

示例 3：

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

输出：2

解释：

提示：

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

代码以及解题思路

代码：

int minFlips(int** grid, int gridSize, int* gridColSize) {
    
    int flips = 0;
    int m = gridSize, n = gridColSize[0];
    int midRow = m / 2, midCol = n / 2;
    for (int i = 0; i < midRow; i++) {
        for (int j = 0; j < midCol; j++) {
            int sum = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j];
            flips += fmin(sum, 4 - sum);
        }
    }
    if (m % 2 != 0 && n % 2 != 0) {
        flips += grid[midRow][midCol];
    }
    int midFlips = 0, ones = 0;
    if (m % 2 != 0) {
        for (int j1 = 0, j2 = n - 1; j1 < j2; j1++, j2--) {
            if (grid[midRow][j1] != grid[midRow][j2]) {
                midFlips++;
            } else {
                ones += grid[midRow][j1] * 2;
            }
        }
    }
    if (n % 2 != 0) {
        for (int i1 = 0, i2 = m - 1; i1 < i2; i1++, i2--) {
            if (grid[i1][midCol] != grid[i2][midCol]) {
                midFlips++;
            } else {
                ones += grid[i1][midCol] * 2;
            }
        }
    }
    if (midFlips == 0 && ones % 4 != 0) {
        midFlips += 2;
    }
    flips += midFlips;
    return flips;
}

解题思路：

初始化变量：
- flips 用于记录总的翻转次数。
- m 和 n 分别表示网格的行数和列数。
- midRow 和 midCol 分别表示网格中间行的索引和中间列的索引（如果网格的行数或列数是奇数，则midRow或midCol指向中间那一行或列）。
处理四个象限：
- 遍历网格的左上象限（不包括中间行和中间列），对于每个元素，计算它及其三个对称位置（右下、左下、右上）的元素之和sum。
- 如果sum为0或4，说明这四个元素已经相同，无需翻转。
- 如果sum为1或3，说明这四个元素中有三个相同，一个不同，可以通过翻转不同的那个元素使其与其余三个相同，此时翻转次数加1。
- 如果sum为2，说明这四个元素中有两个0和两个1，选择翻转其中两个元素使其全部变为0或全部变为1，此时翻转次数加2（但代码中通过fmin(sum, 4 - sum)优化为加1，因为无论翻转哪两个元素，最终效果相同，只需一次“操作”的考虑，这里“操作”可以是翻转两个或翻转零个，但结果都是使四个元素相同）。
处理中心元素：
- 如果网格的行数和列数都是奇数，那么中心元素无法通过对称位置来翻转，所以直接将其翻转（如果它是0则翻转为1，如果它是1则翻转为0），翻转次数加1。
处理中间行和中间列：
- 如果网格的行数是奇数，遍历中间行的元素，检查每一对对称的元素（例如最左边的和最右边的），如果它们不同，则需要进行一次翻转来使它们相同，记录翻转次数midFlips，如果相同，则记录这对元素为1的数量ones（乘以2是因为每次翻转都涉及两个元素）。
- 如果网格的列数是奇数，处理同上，但遍历的是中间列的元素。
- 最后，如果中间行和中间列都没有需要翻转的对（midFlips为0），但是ones的数量不是4的倍数（意味着无法通过一次翻转使所有元素相同），则需要额外的两次翻转（因为需要改变两个元素的状态来匹配其他元素），此时midFlips加2。
返回结果：
- 将所有计算得到的翻转次数相加，得到最终结果flips，并返回。