Medium
题目描述
给你一个 m x n 的二进制矩阵 grid。
如果一行或一列的值从前往后读和从后往前读是相同的，则认为该行或列是回文的。
你可以将 grid 中任意数量的格子从 0 翻转为 1，或从 1 翻转为 0。
返回使所有行和列都成为回文，且 grid 中 1 的总数能被 4 整除所需的最少翻转次数。
示例 1：
输入：grid = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
示例 2：
输入：grid = [[0,1],[0,1],[0,0]]
输出：2
示例 3：
输入：grid = [[1],[1]]
输出：2
提示：
m == grid.lengthn == grid[i].length1 <= m * n <= 2 * 10^50 <= grid[i][j] <= 1
解题思路
解题思路
这道题要求我们同时满足两个条件：
- 所有行和列都是回文的
- 网格中
1的总数能被4整除
核心观察：
要使矩阵既行回文又列回文，那么对于位置 (i,j)，它必须与以下三个位置的值相同：
(i, n-1-j)- 行回文对称位置(m-1-i, j)- 列回文对称位置(m-1-i, n-1-j)- 对角对称位置
这意味着这四个位置构成一个等价组，它们的值必须相同。
解题步骤：
处理四元素组： 遍历矩阵的前半部分，将每四个对称位置归为一组。对于每组，计算翻转成全
0或全1的最小代价，选择代价较小的方案。处理中心行/列： 如果行数或列数为奇数，需要特殊处理中心行/列。中心行/列上的对称位置对必须相同，且为了满足
1的总数被4整除，需要仔细计算。调整总数： 最后检查
1的总数是否被4整除，如果不是则需要额外翻转。
关键在于正确处理边界情况和中心元素，确保既满足回文要求又满足总数要求。
代码实现
class Solution {
public:
int minFlips(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int flips = 0;
int ones = 0;
// Handle 4-element groups (corners and symmetric positions)
for (int i = 0; i < (m + 1) / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
if (i == m - 1 - i && j == n - 1 - j) {
// Center element (only exists when both m and n are odd)
continue;
}
vector<int> positions;
positions.push_back(grid[i][j]);
if (j != n - 1 - j) positions.push_back(grid[i][n - 1 - j]);
if (i != m - 1 - i) positions.push_back(grid[m - 1 - i][j]);
if (i != m - 1 - i && j != n - 1 - j) positions.push_back(grid[m - 1 - i][n - 1 - j]);
int count1 = 0;
for (int val : positions) {
if (val == 1) count1++;
}
// Choose to make all 0s or all 1s, whichever costs less
int cost0 = count1;
int cost1 = positions.size() - count1;
if (cost0 <= cost1) {
flips += cost0;
} else {
flips += cost1;
ones += positions.size();
}
}
}
// Handle middle row if m is odd
if (m % 2 == 1) {
int mid_row = m / 2;
int pairs1 = 0, single_pairs = 0;
for (int j = 0; j < n / 2; j++) {
if (grid[mid_row][j] != grid[mid_row][n - 1 - j]) {
flips++;
single_pairs++;
} else if (grid[mid_row][j] == 1) {
pairs1++;
}
}
ones += pairs1 * 2;
}
// Handle middle column if n is odd
if (n % 2 == 1) {
int mid_col = n / 2;
int pairs1 = 0, single_pairs = 0;
for (int i = 0; i < m / 2; i++) {
if (grid[i][mid_col] != grid[m - 1 - i][mid_col]) {
flips++;
single_pairs++;
} else if (grid[i][mid_col] == 1) {
pairs1++;
}
}
ones += pairs1 * 2;
}
// Handle center element if both m and n are odd
if (m % 2 == 1 && n % 2 == 1) {
if (grid[m / 2][n / 2] == 1) {
flips++;
}
}
// Ensure total 1s is divisible by 4
if (ones % 4 != 0) {
flips += 2;
}
return flips;
}
};
class Solution:
def minFlips(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
flips = 0
ones = 0
# Handle 4-element groups (corners and symmetric positions)
for i in range((m + 1) // 2):
for j in range((n + 1) // 2):
if i == m - 1 - i and j == n - 1 - j:
# Center element (only exists when both m and n are odd)
continue
positions = []
positions.append(grid[i][j])
if j != n - 1 - j:
positions.append(grid[i][n - 1 - j])
if i != m - 1 - i:
positions.append(grid[m - 1 - i][j])
if i != m - 1 - i and j != n - 1 - j:
positions.append(grid[m - 1 - i][n - 1 - j])
count1 = sum(positions)
# Choose to make all 0s or all 1s, whichever costs less
cost0 = count1
cost1 = len(positions) - count1
if cost0 <= cost1:
flips += cost0
else:
flips += cost1
ones += len(positions)
# Handle middle row if m is odd
if m % 2 == 1:
mid_row = m // 2
pairs1 = 0
for j in range(n // 2):
if grid[mid_row][j] != grid[mid_row][n - 1 - j]:
flips += 1
elif grid[mid_row][j] == 1:
pairs1 += 1
ones += pairs1 * 2
# Handle middle column if n is odd
if n % 2 == 1:
mid_col = n // 2
pairs1 = 0
for i in range(m // 2):
if grid[i][mid_col] != grid[m - 1 - i][mid_col]:
flips += 1
elif grid[i][mid_col] == 1:
pairs1 += 1
ones += pairs1 * 2
# Handle center element if both m and n are odd
if m % 2 == 1 and n % 2 == 1:
if grid[m // 2][n // 2] == 1:
flips += 1
# Ensure total 1s is divisible by 4
if ones % 4 != 0:
flips += 2
return flips
public class Solution {
public int MinFlips(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int flips = 0;
int ones = 0;
// Handle 4-element groups (corners and symmetric positions)
for (int i = 0; i < (m + 1) / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
if (i == m - 1 - i && j == n - 1 - j) {
// Center element (only exists when both m and n are odd)
continue;
}
List<int> positions = new List<int>();
positions.Add(grid[i][j]);
if (j != n - 1 - j) positions.Add(grid[i][n - 1 - j]);
if (i != m - 1 - i) positions.Add(grid[m - 1 - i][j]);
if (i != m - 1 - i && j != n - 1 - j) positions.Add(grid[m - 1 - i][n - 1 - j]);
int count1 = 0;
foreach (int val in positions) {
if (val == 1) count1++;
}
// Choose to make all 0s or all 1s, whichever costs less
int cost0 = count1;
int cost1 = positions.Count - count1;
if (cost0 <= cost1) {
flips += cost0;
} else {
flips += cost1;
ones += positions.Count;
}
}
}
// Handle middle row if m is odd
if (m % 2 == 1) {
int midRow = m / 2;
int pairs1 = 0;
for (int j = 0; j < n / 2; j++) {
if (grid[midRow][j] != grid[midRow][n - 1 - j]) {
flips++;
} else if (grid[midRow][j] == 1) {
pairs1++;
}
}
ones += pairs1 * 2;
}
// Handle middle column if n is odd
if (n % 2 == 1) {
int midCol = n / 2;
int pairs1 = 0;
for (int i = 0; i < m / 2; i++) {
if (grid[i][midCol] != grid[m - 1 - i][midCol]) {
flips++;
} else if (grid[i][midCol] == 1) {
pairs1++;
}
}
ones += pairs1 * 2;
}
// Handle center element if both m and n are odd
if (m % 2 == 1 && n % 2 == 1) {
if (grid[m / 2][n / 2] == 1) {
flips++;
}
}
// Ensure total 1s is divisible by 4
if (ones % 4 != 0) {
flips += 2;
}
return flips;
}
}
var minFlips = function(grid) {
const m = grid.length;
const n = grid[0].length;
let flips = 0;
// Handle corner cases for odd dimensions
const midRow = Math.floor(m / 2);
const midCol = Math.floor(n / 2);
// Process symmetric pairs (excluding middle row/col if odd)
for (let i = 0; i < midRow; i++) {
for (let j = 0; j < midCol; j++) {
const cells = [
grid[i][j],
grid[i][n - 1 - j],
grid[m - 1 - i][j],
grid[m - 1 - i][n - 1 - j]
];
const ones = cells.reduce((sum, val) => sum + val, 0);
flips += Math.min(ones, 4 - ones);
}
}
let extraOnes = 0;
let pairs = 0;
// Handle middle row if m is odd
if (m % 2 === 1) {
for (let j = 0; j < midCol; j++) {
if (grid[midRow][j] !== grid[midRow][n - 1 - j]) {
flips++;
} else if (grid[midRow][j] === 1) {
pairs++;
}
}
}
// Handle middle column if n is odd
if (n % 2 === 1) {
for (let i = 0; i < midRow; i++) {
if (grid[i][midCol] !== grid[m - 1 - i][midCol]) {
flips++;
} else if (grid[i][midCol] === 1) {
pairs++;
}
}
}
// Handle center cell if both m and n are odd
if (m % 2 === 1 && n % 2 === 1) {
if (grid[midRow][midCol] === 1) {
flips++;
}
}
// If we have odd number of pair-ones, we need to flip one pair
if (pairs % 2 === 1) {
flips += 2;
}
return flips;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |