LeetCode 题解工作台
在矩阵上写出字母 Y 所需的最少操作次数
给你一个下标从 0 开始、大小为 n x n 的矩阵 grid ，其中 n 为奇数，且 grid[r][c] 的值为 0 、 1 或 2 。 如果一个单元格属于以下三条线中的任一一条，我们就认为它是字母 Y 的一部分： 从左上角单元格开始到矩阵中心单元格结束的对角线。 从右上角单元格开始到矩阵中心单…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用两个长度为 的数组 `cnt1` 和 `cnt2` 分别记录属于 `Y` 的单元格和不属于 `Y` 的单元格的值的个数。然后我们枚举 `i` 和 `j`，分别表示属于 `Y` 的单元格和不属于 `Y` 的单元格的值，计算出最少操作次数。 时间复杂度 ，其中 是矩阵的大小。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始、大小为 n x n 的矩阵 grid ，其中 n 为奇数，且 grid[r][c] 的值为 0 、1 或 2 。
如果一个单元格属于以下三条线中的任一一条，我们就认为它是字母 Y 的一部分：
- 从左上角单元格开始到矩阵中心单元格结束的对角线。
- 从右上角单元格开始到矩阵中心单元格结束的对角线。
- 从中心单元格开始到矩阵底部边界结束的垂直线。
当且仅当满足以下全部条件时，可以判定矩阵上写有字母 Y ：
- 属于 Y 的所有单元格的值相等。
- 不属于 Y 的所有单元格的值相等。
- 属于 Y 的单元格的值与不属于Y的单元格的值不同。
每次操作你可以将任意单元格的值改变为 0 、1 或 2 。返回在矩阵上写出字母 Y 所需的 最少 操作次数。
示例 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为奇数。
解题思路
方法一：计数
我们用两个长度为 的数组 cnt1 和 cnt2 分别记录属于 Y 的单元格和不属于 Y 的单元格的值的个数。然后我们枚举 i 和 j，分别表示属于 Y 的单元格和不属于 Y 的单元格的值，计算出最少操作次数。
时间复杂度 ，其中 是矩阵的大小。空间复杂度 。
class Solution:
def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int:
n = len(grid)
cnt1 = Counter()
cnt2 = Counter()
for i, row in enumerate(grid):
for j, x in enumerate(row):
a = i == j and i <= n // 2
b = i + j == n - 1 and i <= n // 2
c = j == n // 2 and i >= n // 2
if a or b or c:
cnt1[x] += 1
else:
cnt2[x] += 1
return min(
n * n - cnt1[i] - cnt2[j] for i in range(3) for j in range(3) if i != j
)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to identify the Y-shaped region efficiently.
- question_mark
Assess how well the candidate uses hash tables for counting occurrences and minimizing operations.
- question_mark
Evaluate the candidate's approach to calculating the number of operations needed and how they minimize changes.
常见陷阱
外企场景- error
Overlooking the Y shape's exact structure, leading to incorrect cell selection.
- error
Choosing a value that isn't the most frequent within the Y shape, resulting in unnecessary changes.
- error
Misunderstanding the problem's constraints, such as the odd grid size or incorrect range of values.
进阶变体
外企场景- arrow_right_alt
The grid size could vary, but the problem will always involve scanning the grid and identifying the Y shape.
- arrow_right_alt
The problem could be extended to allow for different target shapes, requiring an adaptation of the Y-shape identification process.
- arrow_right_alt
The grid values could be extended beyond 0, 1, and 2, requiring an updated method for value counting and selection.