Medium
题目描述
给你一个大小为 n x n 的二维网格 grid，其中 n 是奇数，且 grid[r][c] 的值为 0、1 或 2。
如果一个单元格属于以下情况之一，我们就说它属于字母 Y：
- 从左上角单元格开始到网格中心单元格结束的对角线。
- 从右上角单元格开始到网格中心单元格结束的对角线。
- 从中心单元格开始到网格底部边界结束的垂直线。
当且仅当满足以下条件时，字母 Y 被写在网格上：
- 属于 Y 的所有单元格的值都相等。
- 不属于 Y 的所有单元格的值都相等。
- 属于 Y 的单元格的值与不属于 Y 的单元格的值不同。
返回在网格上写字母 Y 所需的最小操作数，其中一次操作可以将任意单元格的值更改为 0、1 或 2。
示例 1：
输入：grid = [[1,2,2],[1,1,0],[0,1,0]]
输出：3
解释：我们可以通过上图中突出显示的蓝色更改在网格上写 Y。操作后，所有属于 Y 的单元格（以粗体表示）都具有相同的值 1，而不属于 Y 的单元格都等于 0。
可以证明，在网格上写 Y 需要的最小操作数是 3。
示例 2：
输入：grid = [[0,1,0,1,0],[2,1,0,1,2],[2,2,2,0,1],[2,2,2,2,2],[2,1,2,2,2]]
输出：12
解释：我们可以通过上图中突出显示的蓝色更改在网格上写 Y。操作后，所有属于 Y 的单元格（以粗体表示）都具有相同的值 0，而不属于 Y 的单元格都等于 2。
可以证明，在网格上写 Y 需要的最小操作数是 12。
提示：
3 <= n <= 49n == grid.length == grid[i].length0 <= grid[i][j] <= 2n是奇数
解题思路
解题思路
这道题的核心是要识别哪些位置属于字母Y，然后统计不同数字的频次，最后计算最小操作数。
步骤分析：
识别Y形状的位置：
- 左上到中心的对角线：
(i, i)其中i从0到n/2 - 右上到中心的对角线：
(i, n-1-i)其中i从0到n/2 - 中心到底部的垂直线：
(i, n/2)其中i从n/2到n-1
- 左上到中心的对角线：
统计频次：
- 分别统计Y形状内和Y形状外各数字（0,1,2）的出现次数
- 用两个数组记录频次
计算最小操作数：
- 枚举Y形状内选择哪个数字（0,1,2），Y形状外选择哪个数字
- 要求两个选择的数字必须不同
- 对于每种组合，操作数 = Y内总数 - Y内该数字频次 + Y外总数 - Y外该数字频次
- 取所有组合中的最小值
时间复杂度：O(n²) 遍历网格一次 空间复杂度：O(1) 只用了固定大小的数组
代码实现
class Solution {
public:
int minimumOperationsToWriteY(vector<vector<int>>& grid) {
int n = grid.size();
int center = n / 2;
// 统计Y形状内和外的数字频次
vector<int> yCount(3, 0), nonYCount(3, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bool isY = false;
// 检查是否属于Y形状
if (i <= center && (j == i || j == n - 1 - i)) {
isY = true; // 两条对角线
} else if (i > center && j == center) {
isY = true; // 垂直线
}
if (isY) {
yCount[grid[i][j]]++;
} else {
nonYCount[grid[i][j]]++;
}
}
}
int yTotal = yCount[0] + yCount[1] + yCount[2];
int nonYTotal = nonYCount[0] + nonYCount[1] + nonYCount[2];
int minOps = INT_MAX;
// 枚举Y内外选择的数字组合
for (int yVal = 0; yVal < 3; yVal++) {
for (int nonYVal = 0; nonYVal < 3; nonYVal++) {
if (yVal != nonYVal) {
int ops = (yTotal - yCount[yVal]) + (nonYTotal - nonYCount[nonYVal]);
minOps = min(minOps, ops);
}
}
}
return minOps;
}
};
class Solution:
def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int:
n = len(grid)
center = n // 2
# 统计Y形状内和外的数字频次
y_count = [0, 0, 0]
non_y_count = [0, 0, 0]
for i in range(n):
for j in range(n):
is_y = False
# 检查是否属于Y形状
if i <= center and (j == i or j == n - 1 - i):
is_y = True # 两条对角线
elif i > center and j == center:
is_y = True # 垂直线
if is_y:
y_count[grid[i][j]] += 1
else:
non_y_count[grid[i][j]] += 1
y_total = sum(y_count)
non_y_total = sum(non_y_count)
min_ops = float('inf')
# 枚举Y内外选择的数字组合
for y_val in range(3):
for non_y_val in range(3):
if y_val != non_y_val:
ops = (y_total - y_count[y_val]) + (non_y_total - non_y_count[non_y_val])
min_ops = min(min_ops, ops)
return min_ops
public class Solution {
public int MinimumOperationsToWriteY(int[][] grid) {
int n = grid.Length;
int center = n / 2;
// 统计Y形状内和外的数字频次
int[] yCount = new int[3];
int[] nonYCount = new int[3];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bool isY = false;
// 检查是否属于Y形状
if (i <= center && (j == i || j == n - 1 - i)) {
isY = true; // 两条对角线
} else if (i > center && j == center) {
isY = true; // 垂直线
}
if (isY) {
yCount[grid[i][j]]++;
} else {
nonYCount[grid[i][j]]++;
}
}
}
int yTotal = yCount[0] + yCount[1] + yCount[2];
int nonYTotal = nonYCount[0] + nonYCount[1] + nonYCount[2];
int minOps = int.MaxValue;
// 枚举Y内外选择的数字组合
for (int yVal = 0; yVal < 3; yVal++) {
for (int nonYVal = 0; nonYVal < 3; nonYVal++) {
if (yVal != nonYVal) {
int ops = (yTotal - yCount[yVal]) + (nonYTotal - nonYCount[nonYVal]);
minOps = Math.Min(minOps, ops);
}
}
}
return minOps;
}
}
var minimumOperationsToWriteY = function(grid) {
const n = grid.length;
const center = Math.floor(n / 2);
const yCount = [0, 0, 0];
const nonYCount = [0, 0, 0];
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
let isY = false;
if (i <= center && i === j) isY = true;
else if (i <= center && i + j === n - 1) isY = true;
else if (i >= center && j === center) isY = true;
if (isY) {
yCount[grid[i][j]]++;
} else {
nonYCount[grid[i][j]]++;
}
}
}
const totalY = yCount[0] + yCount[1] + yCount[2];
const totalNonY = nonYCount[0] + nonYCount[1] + nonYCount[2];
let minOps = Infinity;
for (let yVal = 0; yVal <= 2; yVal++) {
for (let nonYVal = 0; nonYVal <= 2; nonYVal++) {
if (yVal !== nonYVal) {
const ops = (totalY - yCount[yVal]) + (totalNonY - nonYCount[nonYVal]);
minOps = Math.min(minOps, ops);
}
}
}
return minOps;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 需要遍历整个 n×n 的网格一次 |
| 空间复杂度 | O(1) | 只使用了固定大小的数组存储频次 |