欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java/861.(反转矩阵后的得分) Score After Flipping Matrix

程序员文章站 2024-02-28 12:15:22
...

先上题目

Java/861.(反转矩阵后的得分) Score After Flipping Matrix





给出了两种风格的代码,一是直接在类里面完成计算。二是定义功能函数,通过调用函数完成计算。思路在最后面。


代码部分一:

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.从低位(行数组尾部)开始计算数组行值。