翻转矩阵后的得分

2020-12-07

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。

返回尽可能高的分数。

 

示例：

输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：
转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
 

提示：

1 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j] 是 0 或 1
通过次数17,495提交次数21,642

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/score-after-flipping-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

贪心算法

要想所有的数字的和最大，那么每一个数字都应该是最大数字，为了使二进制数字最大，二进制的最高位应该是1（不含符号位），所以在处理时应将每一行的最高位置为1（先对行处理），对后面的每一列，统计每个列中1的数量是否大于列值的1/2，如果不大于列值的1/2就对该列取反

class Solution {
    public int matrixScore(int[][] A) {
        if (A.length == 0 || A[0].length == 0) {
            return 0;
        }

        //先把最高位置为1
        for (int i = 0; i < A.length; i++) {
            if (A[i][0] == 0) {
                for (int j = 0; j < A[i].length; j++) {
                    A[i][j] = 1 - A[i][j];//对值取反
                }
            }
        }

        //对于每一列，统计1的数量，如果1的数量小于1/2，那么反转这一列

        for (int j = 0; j < A[0].length; j++) {
            int sum = 0;
            for (int i = 0; i < A.length; i++) {
                sum += A[i][j];
            }
            if (A.length - sum > sum) {
                for (int i = 0; i < A.length; i++) {
                    A[i][j] = 1 - A[i][j];//对值取反
                }
            }


        }
        int sum = 0;
        for (int i = 0; i < A.length; i++) {
            StringBuilder bd = new StringBuilder();//先转换成字符串再使用API将字符串将二进制字符转化成十进制数字
            for (int j = 0; j < A[i].length; j++) {
                bd.append(A[i][j]);
            }
            sum += Integer.valueOf(bd.toString(), 2);
        }
        return sum;
    }
}



class Solution {
    public int matrixScore(int[][] A) {

        int yLen = A.length;
        int xLen = A[0].length;

        if (yLen == 0 || xLen == 0) {
            return 0;
        }

        //先把最高位置为1
        for (int i = 0; i < yLen; i++) {
            if (A[i][0] == 0) {
                for (int j = 0; j < xLen; j++) {
                    A[i][j] = 1 - A[i][j];
                }
            }
        }

        //对于每一列，统计1的数量，如果1的数量小于1/2，那么反转这一列

        for (int j = 0; j < xLen; j++) {
            int sum = 0;
            for (int i = 0; i < yLen; i++) {
                sum += A[i][j];
            }
            if (yLen - sum > sum) {
                for (int i = 0; i < yLen; i++) {
                    A[i][j] = 1 - A[i][j];
                }
            }


        }
        int sum = 0;
        for (int i = 0; i < yLen; i++) {
            for (int j = 0; j < xLen; j++) {
                sum +=A[i][j]* Math.pow(2 * A[i][j], xLen - 1 - j);
            }
        }
        return sum;
    }
}


class Solution {
    public int matrixScore(int[][] A) {
        int m = A.length, n = A[0].length;
        int ret = m * (1 << (n - 1));

        for (int j = 1; j < n; j++) {
            int nOnes = 0;
            for (int i = 0; i < m; i++) {
                if (A[i][0] == 1) {
                    nOnes += A[i][j];
                } else {
                    nOnes += (1 - A[i][j]); // 如果这一行进行了行反转，则该元素的实际取值为 1 - A[i][j]
                }
            }
            int k = Math.max(nOnes, m - nOnes);
            ret += k * (1 << (n - j - 1));
        }
        return ret;
    }
}

参考文献

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/score-after-flipping-matrix/solution/fan-zhuan-ju-zhen-hou-de-de-fen-by-leetc-cxma/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。