861. Score after flipping the matrix

Address ：

Power button https://leetcode-cn.com/problems/score-after-flipping-matrix/

subject ：

There's a two-dimensional matrix  A The value of each of these elements is  0  or  1 .

Move means to select any row or column , And convert each value in the row or column ： Will all 0 All changed to 1, Will all 1 All changed to 0.

After making any number of moves , Explain each line of the matrix as a binary number , The score of the matrix is the sum of these numbers .

Return as high a score as possible .

Example ：

Input ：[[0,0,1,1],[1,0,1,0],[1,1,0,0]] Output ：39 explain ： Convert to [[1,1,1,1],[1,0,0,1],[1,1,1,1]] 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Tips ：

1 <= A.length <= 20 1 <= A[0].length <= 20 A[i][j]  yes  0 or  1

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/score-after-flipping-matrix
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

A binary representation , If you want a large number , Then try to be equal to 1

such as ：

So for a matrix expressing binary numbers like this

Each line is a binary number , The first goal is to set all the highest positions 1

The first stage ：

So we scan every line on the 0 Column , If the value is not 0, Just flip the rows

         first line ：

        

         The second line ：

        

         The third line is not 0, Do not do line transformation

The second stage ：

         We can't do row changes anymore , If you do it again, the highest level may change , At this stage, we deal with column transformation

        Starting column from 1 Column start , Compare this column 0 Number of elements ,1 Number of elements

        Only 1 When there are more elements , The sum of addition is bigger

        First column ： All is 1 No transformation

        Second column ：0：2 individual ,1：1 individual , Column transformation

                

        The third column ：0：2 individual ,1：1 individual , Column transformation

                 

The third stage ：

        After the first two stages , We all get the final matrix , The rest is to traverse the matrix rows

        Convert binary numbers to decimal numbers

        such as ：1 1 0 1

                1*2^3 + 1*2^2 + 0*2^1 + 1*2^0

Implementation part , You need to create two additional two-dimensional arrays

It is still illustrated by the original matrix ：

Row array	Elements 0 The number of	Elements 1 The number of
countRowArr	[0][0] = 3	[0][1] = 1
	[1][0] = 3	[1][1] = 1
	[2][0] = 2	[2][1] = 2

Column array	Elements 0 The number of	Elements 1 The number of
countColArr	[0][0] = 2	[0][1] = 1
	[1][0] = 2	[1][1] = 1
	[2][0] = 2	[2][1] = 1
	[3][0] = 2	[3][1] = 1

 

It needs to be judged again Row transformation or Column transformation when , To update the values of the above two two-dimensional arrays

Method 1 、 Dynamically update values

  A little bit more code , The main logic goes first ：

1. Create two two-dimensional arrays

2. Row transformation

3. Column transformation

4. The transformation is complete , Calculate the decimal value of binary

    int **countRowArr = createCountGrid(grid, row, col, "row");
    int **countColArr = createCountGrid(grid, row, col, "col");
   

    /* reverse */
    for(i=0; i<row; i++)
    {
        if(grid[i][0] == 0)
        {
            doReverse(grid, row, col, i, -1, countRowArr, countColArr, "row");
        }
    }


    for(i=1; i<col; i++)
    {
        if( needReverse(countColArr, i) )
            doReverse(grid, row, col, -1, i, countRowArr, countColArr, "col");
    }


    /* caculate */
    for(i=0; i<row; i++)
    {
        ret += cacul(grid[i], col);
    }

  The rest of the code is to implement the above functions , Here is the full code ：

int ** createCountGrid(int **grid, int row, int col, char *content)
{
    int i,j;

    if(strcmp(content, "row") == 0)
    {
        /* store numbers of 0 1 in each row */
        int **countRowArr = (int **)malloc(sizeof(int *) * row);
        for(i=0; i<row; i++)
        {
            countRowArr[i] = (int *)malloc(sizeof(int) * 2);
        }

        /* init countRowArr */
        for(i=0; i<row; i++)
        {
            int zero = 0, one = 0;
            for(j=0; j<col; j++)
            {
                if(grid[i][j] == 0)
                    zero++;
                else
                    one++;
            }
            countRowArr[i][0] = zero;
            countRowArr[i][1] = one;
        }

        return countRowArr;
    }
    else
    {
        /* store numbers of 0 1 in each col */
        int **countColArr = (int **)malloc(sizeof(int *) * col);
        for(i=0; i<col; i++)
        {
            countColArr[i] = (int *)malloc(sizeof(int) * 2);
        }

        /* init countColArr */
        for(j=0; j<col; j++)
        {
            int zero = 0, one = 0;
            for(i=0; i<row; i++)
            {
                if(grid[i][j] == 0)
                    zero++;
                else
                    one++;
            }
            countColArr[j][0] = zero;
            countColArr[j][1] = one;
        }

        return countColArr;
    }

    return NULL;
}

void freeCountGrid(int **grid, int row, int col, char *content)
{
    int i;
    int drow, dcol;

    if(strcmp(content, "row") == 0)
        drow = row;
    else
        drow = col;

    for(i=0; i<drow; i++)
    {
        free(grid[i]);
    }
    free(grid);
}

void dispGrid(int **grid, int row, int col, char *content)
{
    int i, j;
    int drow, dcol;

    if(strcmp(content, "row") == 0)
    {
        drow = row;
        dcol = 2;
    }
    else if(strcmp(content, "col") == 0)
    {
        drow = col;
        dcol = 2;
    }
    else
    {
        drow = row;
        dcol = col;
    }

    for(i=0; i<drow; i++)
    {
        for(j=0; j<dcol; j++)
        {
            printf("disp...%s, grid[%d][%d]=%d\n", content, i, j, grid[i][j]);
        }
    }
}

bool needReverse(int **countArr, int idx)
{
    if(countArr[idx][0] >= countArr[idx][1])
        return true;
    else
        return false;

    return false;
}

void doReverse(int **grid, int row, int col, int revRowIdx, int revColIdx, int **countRowArr, int **countColArr, char *content)
{
    int i;

    if(strcmp(content, "row") == 0) // reverse row
    {
        for(i=0; i<col; i++)
        {
            if(grid[revRowIdx][i] == 0)
            {
                grid[revRowIdx][i] = 1;
                countRowArr[revRowIdx][0] --;
                countRowArr[revRowIdx][1] ++;
                countColArr[i][0] --;
                countColArr[i][1] ++;    
            }
            else
            {
                grid[revRowIdx][i] = 0;
                countRowArr[revRowIdx][0] ++;
                countRowArr[revRowIdx][1] --;
                countColArr[i][0] ++;
                countColArr[i][1] --;
            }
        }
    }
    else
    {
        for(i=0; i<row; i++)
        {
            if(grid[i][revColIdx] == 0)
            {
                grid[i][revColIdx] = 1;

                countColArr[revColIdx][0] --;
                countColArr[revColIdx][1] ++;
                countRowArr[i][0] --;
                countRowArr[i][1] ++;
            }
            else
            {
                grid[i][revColIdx] = 0;

                countColArr[revColIdx][0] ++;
                countColArr[revColIdx][1] --;
                countRowArr[i][0] ++;
                countRowArr[i][1] --;
            }
        }
    }
}

int cacul(int *arr, int len)
{
    int num = 0;
    int k = 0;

    for(int i=len-1; i>=0; i--)
    {
        if(arr[k++] == 0)
            continue;

        int j = i;
        int tmp = 1;
        while(j)
        {
            tmp *= 2;
            j--;
        }
        num += tmp;
    }

    return num;
}

int matrixScore(int** grid, int gridSize, int* gridColSize){
    int i, j;
    int ret = 0;
    int row = gridSize;
    int col = gridColSize[0];

    int **countRowArr = createCountGrid(grid, row, col, "row");
    int **countColArr = createCountGrid(grid, row, col, "col");
    
    // dispGrid(grid, row, col, "all");
    // dispGrid(countRowArr, row, col, "row");
    // dispGrid(countColArr, row, col, "col");

    /* reverse */
    for(i=0; i<row; i++)
    {
        if(grid[i][0] == 0)
        {
            doReverse(grid, row, col, i, -1, countRowArr, countColArr, "row");
        }
    }

    // dispGrid(grid, row, col, "all");
    // dispGrid(countRowArr, row, col, "row");
    // dispGrid(countColArr, row, col, "col");

    for(i=1; i<col; i++)
    {
        if( needReverse(countColArr, i) )
            doReverse(grid, row, col, -1, i, countRowArr, countColArr, "col");
    }

    //dispGrid(grid, row, col, "all");
    // dispGrid(countRowArr, row, col, "row");
    // dispGrid(countColArr, row, col, "col");

    /* caculate */
    for(i=0; i<row; i++)
    {
        ret += cacul(grid[i], col);
    }

    /* free */
    freeCountGrid(countRowArr, row, col, "row");
    freeCountGrid(countColArr, row, col, "col");

    return ret;
}

 

See more brush notes