在矩阵上写出字母 Y 所需的最少操作次数

标签: 数组 哈希表 计数 矩阵

难度: Medium

给你一个下标从 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 <= 49
  • n == grid.length == grid[i].length
  • 0 <= grid[i][j] <= 2
  • n 为奇数。

Submission

运行时间: 43 ms

内存: 16.2 MB

class Solution:
    def minimumOperationsToWriteY(self, A: List[List[int]]) -> int:
        cnt1 = [0] * 3
        cnt2 = [0] * 3
        n = len(A)
        m = n // 2

        for i, row in enumerate(A[:m]):
            cnt1[row[i]] += 1
            cnt1[row[-1 - i]] += 1
            for j, x in enumerate(row):
                if j != i and j != n - 1 - i:
                    cnt2[x] += 1
        
        for row in A[m:]:
            cnt1[row[m]] += 1
            for j, x in enumerate(row):
                if j != m:
                    cnt2[x] += 1
        
        max_not_change = 0
        for i, c1 in enumerate(cnt1):
            for j, c2 in enumerate(cnt2):
                if i != j:
                    max_not_change = max(max_not_change, c1 + c2)
        return n * n - max_not_change

Explain

此题的解法是通过统计属于Y形的单元格和非Y形的单元格中0、1、2的出现次数，然后尝试所有可能的值组合来最小化变换次数。首先使用两个计数器cnt1和cnt2分别统计属于Y的单元格和不属于Y的单元格中0、1、2的出现次数。接着，对于每种可能的Y值（0、1、2）和非Y值（也是0、1、2），当Y值不等于非Y值时，计算不需要变化的单元格数量（即已经为目标值的单元格数量）。最后，从总单元格数中减去这个最大的不需要变化的单元格数量，得到最小的操作次数。

时间复杂度: O(n^2)

空间复杂度: O(1)

# Code with added comments

class Solution:
    def minimumOperationsToWriteY(self, A: List[List[int]]) -> int:
        cnt1 = [0] * 3  # Counters for values in parts belonging to Y
        cnt2 = [0] * 3  # Counters for values not in Y
        n = len(A)
        m = n // 2  # Center of the matrix

        # Count values for parts of Y and not Y in the top half of the matrix
        for i, row in enumerate(A[:m]):
            cnt1[row[i]] += 1  # Left diagonal part of Y
            cnt1[row[-1 - i]] += 1  # Right diagonal part of Y
            for j, x in enumerate(row):
                if j != i and j != n - 1 - i:
                    cnt2[x] += 1  # Non-Y cells
        
        # Count values for parts of Y and not Y in the bottom half of the matrix
        for row in A[m:]:
            cnt1[row[m]] += 1  # Center vertical line of Y
            for j, x in enumerate(row):
                if j != m:
                    cnt2[x] += 1  # Non-Y cells
        
        max_not_change = 0
        # Calculate the maximum number of cells that do not need to be changed
        for i, c1 in enumerate(cnt1):
            for j, c2 in enumerate(cnt2):
                if i != j:
                    max_not_change = max(max_not_change, c1 + c2)
        
        # The minimum number of changes needed is the total cells minus the maximum number of unchanged cells
        return n * n - max_not_change

Explore

在代码中，Y形部分的确定基于矩阵的对称性和中心线。具体逻辑如下：对于矩阵的上半部分（即索引从0到m-1的行），属于Y形的单元格包括左右两条对角线上的单元格。这通过判断索引关系i和n-1-i来实现，其中i是行的索引，n是矩阵的大小。在矩阵的下半部分（即索引从m到n-1的行），属于Y形的单元格仅包括中心竖线上的单元格，即列索引为m的单元格。不属于Y形的单元格则是除了上述Y形单元格以外的所有单元格。

尝试所有可能的Y值和非Y值组合是为了确保找到真正的最小操作次数。如果仅选择出现次数最多的值作为目标值，可能会忽略不同值间转换的逻辑关系，导致实际操作次数并非最小。例如，如果Y形区域内出现次数最多的是1，而非Y形区域内出现次数最多的也是1，按照简单的最多次数策略将两者都设置为1，这会忽略Y形与非Y形区域应有不同的数值要求。因此，通过遍历所有可能的值组合，确保Y形与非Y形区域的值不同，从而找到真正的最少改变次数。

这种处理是不正确的，因为中心单元格只应计算一次。在代码中，中心单元格出现在矩阵的上半部分的最后一行以及下半部分的第一行的中心位置。这个重复计算可能会导致对Y形区域内的某些值的计数不准确，从而影响最终的操作次数计算。正确的做法应该是确保中心单元格只在其中一个部分被计算，通常选择在下半部分计算一次即可。