当前位置:网站首页>861. Score after flipping the matrix
861. Score after flipping the matrix
2022-07-06 07:38:00 【mrbone9】
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;
}
边栏推荐
- 烧录场景下的源代码防泄密方案分享
- 杰理之BLE【篇】
- xpath中的position()函数使用
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- 杰理之普通透传测试---做数传搭配 APP 通信【篇】
- 成为优秀的TS体操高手 之 TS 类型体操前置知识储备
- If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
- word中如何删除某符号前面或后面所有的文字
- 数字IC设计笔试题汇总(一)
- Typescript interface and the use of generics
猜你喜欢
Comparison of usage scenarios and implementations of extensions, equal, and like in TS type Gymnastics
leecode-C語言實現-15. 三數之和------思路待改進版
opencv学习笔记八--答题卡识别
Ble of Jerry [chapter]
数字IC设计笔试题汇总(一)
How MySQL merges data
JMeter performance test steps practical tutorial
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
Opencv learning notes 8 -- answer sheet recognition
Simulation of Teman green interferometer based on MATLAB
随机推荐
Set picture annotation in markdown
js对象获取属性的方法(.和[]方式)
解决方案:智慧工地智能巡检方案视频监控系统
word怎么只删除英语保留汉语或删除汉语保留英文
Ble of Jerry [chapter]
leecode-C语言实现-15. 三数之和------思路待改进版
Cf1036c class numbers solution
[MySQL learning notes 29] trigger
Typescript indexable type
Jerry's ad series MIDI function description [chapter]
Simulation of Michelson interferometer based on MATLAB
Relevant introduction of clip image
word中把帶有某個符號的行全部選中,更改為標題
杰理之开发板上电开机,就可以手机打开 NRF 的 APP【篇】
Luogu p1836 number page solution
Generator Foundation
CF1036C Classy Numbers 题解
Scala language learning-08-abstract classes
Rust language - receive command line parameter instances
Luogu p4127 [ahoi2009] similar distribution problem solution