Java/861.(反转矩阵后的得分) Score After Flipping Matrix
程序员文章站
2024-02-28 12:15:22
...
先上题目
给出了两种风格的代码,一是直接在类里面完成计算。二是定义功能函数,通过调用函数完成计算。思路在最后面。
代码部分一:
class Solution {
public int matrixScore(int[][] A) {
int i,j,zeroCount,oneCount,index,count,result=0;
for(i=0;i<A.length;i++){
if(A[i][0]==0){ //先判断后循环取反
for(j=0;j<A[0].length;j++){ //若在此写“if(A[i][0]==0){ ”,当第一个为0时,到了第二个(后面)的数,A[i][0]已经被改为0,后面都无效
if(A[i][j]==0){
A[i][j]=1;
}else{
A[i][j]=0;
}
}
}
}
for(j=0;j<A[0].length;j++){
zeroCount=0;
oneCount=0;
for(i=0;i<A.length;i++){
switch(A[i][j]){
case 0:
zeroCount++;
break;
case 1:
oneCount++;
break;
default:break;
}
}
if(zeroCount>oneCount){
i=0;
while(i<A.length){
if(A[i][j]==0){
A[i][j]=1;
}else{
A[i][j]=0;
}
i++;
}
}
}
for(i=0;i<A.length;i++){
count=0;
j=A[0].length-1;
while(j>=0){
index=0;
while(index<count){
A[i][j]=A[i][j]*2;
index++;
}
result=result+A[i][j];
count++;
j--;
}
}
return result;
}
}
代码部分二:
class Solution {
public int matrixScore(int[][] A) {
this.moveLine(A);
this.moveColumn(A);
return this.countResult(A);
}
public int countResult(int[][] A){
int i,j,index,count,result=0;
for(i=0;i<A.length;i++){
count=0;
j=A[0].length-1;
while(j>=0){
index=0;
while(index<count){
A[i][j]=A[i][j]*2;
index++;
}
result=result+A[i][j];
count++;
j--;
}
}
return result;
}
public void moveColumn(int[][] A){ //返回所有行二进制数之和
int i,j,zeroCount,oneCount;
for(j=0;j<A[0].length;j++){
zeroCount=0;
oneCount=0;
for(i=0;i<A.length;i++){
switch(A[i][j]){
case 0:
zeroCount++;
break;
case 1:
oneCount++;
break;
default:break;
}
}
if(zeroCount>oneCount){ //在矩阵中进列行移动
i=0;
while(i<A.length){
if(A[i][j]==0){
A[i][j]=1;
}else{
A[i][j]=0;
}
i++;
}
}
}
}
public void moveLine(int[][] A){ //在矩阵中进行行移动
int i,j;
for(i=0;i<A.length;i++){
if(A[i][0]==0){
for(j=0;j<A[0].length;j++){
if(A[i][j]==0){
A[i][j]=1;
}else{
A[i][j]=0;
}
}
}
}
}
}
思路:题意都没有问题,要注意的是行和列任意次移动,达到最大值。即以求出最优解为目标(可重复移动)。按二进制数来解释,注意数组[0-n]对应二进制“高位-低位”。
首先对行移动求最优解:二进制数,高位的有效值“1”大于后面所有位数之和,举个例子:10000=16 01010=10 00111=7。所以我们需要判断A[i][0](每行首元素)是否为“1”,将为“0”的进行移动操作,本行即达到最优。重复每行即为所有行最优
再对列移动求最优解:本题为矩阵,所以同一列的数字在二进制解释中位于相同的位置(2^n),当一列中"1"的数量最大时,结果值最大。即为列最优解,同理求出所有列最优解。
最后计算矩阵的总和,注意从低位(数组尾部开始计算)。
1.若行最高位(数组行首元素)不为“1”,移动行。
2.若列“0”数量多于“1”,移动列。
3.从低位(行数组尾部)开始计算数组行值。