😀 1252.奇数值单元格的数目

给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个二维索引数组 indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

对 indices[i] 所指向的每个位置，应同时执行下述增量操作：

1. ri 行上的所有单元格，加 1 。
2. ci 列上的所有单元格，加 1 。

给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。

思路

基本思想

看到题的第一想法就是直接模拟更新过程，更新完毕之后统计所有的奇数单元格即可，但是这种方法过于暴力，自己观察之后发现，一个位置要出现奇数值，综合来看，只能是当前位置所处的行列被更新的次数不相等，如果当前位置行列更新次数相等，相加起来一定是偶数，就不符合条件

所以我们可以统计所有的indices，如果当前的indices[i]让当前的行列更新次数变成偶数，那么奇数行和奇数列的数量就减小，如果当前的indices[i]让当前的行列更新次数变成奇数，那么奇数行和奇数列的数量就增大，遍历完所有的indices之后，就得到了奇数行和奇数列的个数

针对一个奇数行来说，当前列存在多少偶数列，就可以得到多少个奇数单元格，针对一个偶数行来说，当前列存在多少奇数列，就可以得到多少个奇数单元格，也就是奇数单元格的数量为： $$ res=(奇数行)(偶数列)+(偶数行)(奇数列) $$

核心就是当前位置要出现奇数单元格，需要行列更新次数不一样

执行流程

1. 定义两个数组，记录当前行列是不是更新了奇数次，便于统计奇数个数
2. 当前indices[i]更新过后，当前行列是不是更新了奇数次，直接在原有技术上取反即可
3. 如果当前是更新了奇数次，那么奇数个数+1,否则奇数个数-1
4. 统计完成之后按照上述公式得到结果

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    //暴力法：先执行，再统计
    // 能否边更新边统计:当前位置是奇数（行列累加数不相等即可）
    public int oddCells(int m, int n, int[][] indices) {
        //定义两个数组存储当前行被累加奇数次还是偶数次
        //初始状态下全都是flase
        boolean[] r=new boolean[m],c=new boolean[n];
        int oddRow=0,oddColumn=0;
        for(int i=0;i<indices.length;++i){
            //变成true说明当前行(列)被累加奇数次
            //在原有基础上进行取反
            oddRow+=(r[indices[i][0]]=!r[indices[i][0]])?1:-1;
            oddColumn+=(c[indices[i][1]]=!c[indices[i][1]])?1:-1;
        }
        //奇数行*偶数列+奇数列*偶数行
        return oddRow*(n-oddColumn)+oddColumn*(m-oddRow);
    }
}

总结

核心就是知道当前位置要出现奇数需要符合行列更新次数不一样的规律，更像是一个找规律的题目