首页 > 其他 > 详细

[贪心] leetcode 861 Score After Flipping Matrix

时间:2019-07-30 23:45:29      阅读:97      评论:0      收藏:0      [点我收藏+]

problem:https://leetcode.com/problems/score-after-flipping-matrix/

         一道贪心题,按照正常人的思路(而不是计算机的思路)去翻转就行了。说起来第一次看的时候有点懵逼,可能我更加习惯计算机的思维方式?

         (1) 只在第一列翻转行,通过行翻转把第一列的所有数字变为1.

         (2) 之后的几列只翻转列,并且仅在0的个数大于一半的时候进行翻转。

class Solution {
public:
    vector<int> zeros;
    int matrixScore(vector<vector<int>>& A) {
        int m = A.size();
        int n = A[0].size();
        
        int h = m / 2;
        for(int j = 0;j < n;j++)
        {
            int zeros = 0;
            for(int i = 0;i < m;i++)
            {
                if(A[i][j] == 0)
                    zeros++;
            }
            // flip col
            if(zeros > h)
            {
                for(int i = 0;i < m;i++)
                {
                    A[i][j] = !A[i][j];
                }
            }
            
            // flip row
            if(j == 0)
            {
                for(int i = 0;i < m;i++)
                {
                    if(A[i][j] == 0)
                    {
                        for(int k = 0;k < n;k++)
                        {
                            A[i][k] = !A[i][k];
                        }
                    }
                }
            }
        }
        
        int res = 0;
        for(int i = 0;i < m;i++)
        {
            for(int j = 0;j < n;j++)
            {
                if(A[i][j] == 1)
                    res += (1 << (n - j - 1));
            }
        }
        return res;
    }
};

 

[贪心] leetcode 861 Score After Flipping Matrix

原文:https://www.cnblogs.com/fish1996/p/11273181.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!