Day 19 of leetcode

The number of odd cells

To give you one m x n Matrix , At the very beginning , The value in each cell is 0.

There is another two-dimensional index array  indices,indices[i] = [ri, ci] Point to a position in the matrix , among ri and ci Respectively represent the specified row and column （ from 0 Numbered starting ）.

Yes indices[i] Every position pointed , The following incremental operations should be performed at the same time ：

• ri All cells on the row , Add 1 .
• ci All cells on the column , Add 1 .

Here you are. m、n and indices . Please finish executing all  indices  After the specified incremental operation , Returns odd cells in a matrix Number of .

analysis ：

Because each operation will only increase the number of one row and one column 1, So you can use an array of rows rows And column array cols Record the number of times each row and column is increased . about indices Every pair of [ri, ci], take rows[ri] and cols[ci] The values of are increased respectively 1. After all operations are completed , We can calculate the position (x, y) The count of positions is rows[x]+cols[y]. ergodic matrix , You can get the number of all odd numbers .

class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] rows = new int[m];
        int[] cols = new int[n];
        for (int[] index : indices) {
            rows[index[0]]++;
            cols[index[1]]++;
        }
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (((rows[i] + cols[j]) & 1) != 0) {
                    res++;
                }
            }
        }
        return res;
    }
}

Do not add, subtract, multiply or divide

Write a function , Find the sum of two integers , It is required that... Should not be used in the function body “+”、“-”、“*”、“/” Four operation symbols .

analysis ：

Use bitwise operation .

class Solution {
    public int add(int a, int b) {
        while(b != 0) { //  When carry is  0  Jump out when 
            int c = (a & b) << 1;  // c =  carry 
            a ^= b; // a =  Non carry and 
            b = c; // b =  carry 
        }
        return a;
    }
}

Building a product array

Given an array A[0,1,…,n-1], Please build an array B[0,1,…,n-1], among  B[i] Is the value of an array A In addition to subscript i The product of other elements , namely  B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]. Division cannot be used .

analysis ：

Our solution is simple ergodic calculation .

class Solution {
    public int[] constructArr(int[] a) {
        int[] res = new int[a.length];
        for (int i = 0, cur = 1; i < a.length; i++) {
            res[i] = cur;   //  Multiply the number on the left first ( Not including myself )
            cur *= a[i];
        }
        for (int i = a.length - 1, cur = 1; i >= 0; i--) {
            res[i] *= cur;  //  Multiply by the number on the right ( Not including myself )
            cur *= a[i];
        }
        return res;
    }
}

Big guy's idea ：

According to the main diagonal of the table （ All for  1 ）, The table can be divided into   Upper triangle   and   Lower triangle   Two parts . Iteratively calculate the product of the lower triangle and the upper triangle respectively , that will do   Don't use division   You get results .

class Solution {
    public int[] constructArr(int[] a) {
        int len = a.length;
        if(len == 0) return new int[0];
        int[] b = new int[len];
        b[0] = 1;
        int tmp = 1;
        for(int i = 1; i < len; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }
        for(int i = len - 2; i >= 0; i--) {
            tmp *= a[i + 1];
            b[i] *= tmp;
        }
        return b;
    }
}