1. 首页
  2. IT教程

Leetcode 1252. Cells with Odd Values in a Matrix

文章作者:Tyan
博客:noahsnail.com | CSDN | 简书

1. Description

Leetcode 1252. Cells with Odd Values in a Matrix

2. Solution

**解析:**Version 1,由于是统计奇数的个数,因此不需要每次加1,只需要奇数次设置值为1,偶数次设置值为0,最后统计矩阵的和即可,通过异或^1实现。Version 2非常巧妙,由于每一次操作都是一行或一列,因此用两个数组就可以模拟所有的行和列,最终矩阵的第(i,j)个元素的值为row[i]+col[j],对矩阵的每个值进行统计即可。Version 1需要修改一行或一列,现在只需要修改一个数值即可,大大减少了操作的数量,运行时间明显减少。

  • Version 1
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        matrix = [[0] * n for _ in range(m)]
        for row, col in indices:
            for i in range(n):
                matrix[row][i] = matrix[row][i] ^ 1
            for i in range(m):
                matrix[i][col] = matrix[i][col] ^ 1
        return sum([sum(row) for row in matrix])
  • Version 2
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        rows = [0] * m
        cols = [0] * n
        for i, j in indices:
            rows[i] ^= 1
            cols[j] ^= 1

        count = 0
        for i in range(m):
            for j in range(n):
                if rows[i] + cols[j] == 1:
                    count += 1
        return count

Reference

  1. https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/

原创文章,作者:夜风博客,如若转载,请注明出处:https://www.homedt.net/358790.html