[leetcode]Score After Flipping Matrix

题目要求:
We have a two dimensional matrix A where each value is 0 or 1.

A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

Example 1:

Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

这里的核心是怎么切换保证能得到最大的值?
我本来想着利用计数排序的思路,先令最后的列满足最大全为1,然后是倒数第二列,但有个问题就是,如果原本此列都是1的话,就要出现错误,因为要排除此错误还要家条件判断,程序会很复杂,明显不是正确解。
因此看了解决方案,是利用贪婪算法的路子。
利用行切换,保证0列全为1,然后后面全部使用列切换,对后面每列,0多就切换,保证数值局部最大,如果1多直接加。
其中还有一个点就是对于构建类似二进制转为十进制方法,因为在java,执行二进制操作会自动转为十进制显示,所以就利用位移操作来实现二进制指定位的填充。

class Solution {
    public int matrixScore(int[][] A) {
        int n = A.length;
        int m = A[0].length;
        int res=n*(1<<m-1);
//得到最高位填充指定位置得到的二进制数字
        for(int j=1;j<m;j++){
            int cur=0;
            for(int i=0;i<n;i++) cur+=A[i][j]==A[i][0]?1:0;
            res+=Math.max(cur,n-cur)*(1<<m-1-j);
//同样利用位移实现指定二进制位的填充
        }
        return res;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • pyspark.sql模块 模块上下文 Spark SQL和DataFrames的重要类: pyspark.sql...
    mpro阅读 9,537评论 0 13
  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,483评论 0 10
  • 我喜欢风,那是自由的感觉,无拘无束,谁都不能让其停留半步。所以我喜欢这谁都管不了的感觉,这大概就是自由了吧?我没有...
    石凹叙年阅读 390评论 0 1
  • 0211-玲儿-涵涵妈[萱花椿树]学习力7期20171019-D9:古诗,复习前6首,最初2首孩子基本都能背下来了...
    玲儿_6848阅读 206评论 0 0
  • 早上急匆匆的拎着包进班时,已经有好多孩子在班里早读了,他们声音洪亮,站姿挺拔;有值日的学生默默的干着自己的活,每个...
    小核桃麻麻阅读 187评论 0 1