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