A:
就是看矩阵,找出 规律,首先行变换,把每行的首字母都变成1.
然后列变换,让每一列都是1比0 多。
Intuition
Notice that a 1
in the th column from the right, contributes to the score.
Since , maximizing the left-most digit is more important than any other digit. Thus, the rows should be toggled such that the left-most column is either all 0
or all 1
(so that after toggling the left-most column [if necessary], the left column is all 1
.)
Algorithm
If we toggle rows by the first column (A[r][c] ^= A[r][0]
), then the first column will be all 0
.
Afterwards, the base score is max(col, R - col)
where col
is the column sum; and (1 << (C-1-c))
is the power of 2 that each 1
in that column contributes to the score.
class Solution { public: int matrixScore(vector<vector<int>>& A) { int m = A.size(); if(m==0) return 0; int n = A[0].size(); //first make first item of every row be positive for(int i =0;i<m;i++){ if(A[i][0] == 1) continue; for(int j = 0;j<n;j++) A[i][j] = 1 - A[i][j]; } // now check every column, if more zero than one, then flip for(int j = 1; j <n; j++){ int count1 =0; for(int i = 0;i<m;i++) count1 += A[i][j]; if(count1 < m - count1){ // flip for(int i = 0;i<m;i++) A[i][j] = 1- A[i][j]; } } int res = 0; for(int i = 0;i<m;i++) res += getValue(A[i]); return res; } private: int getValue(vector<int> & row){ int res = 0; for(auto v : row) res = res * 2 + v; return res; } };
------------------上面的思路时清晰的, 然和人, 之beat 了 9.82%的。
优化一下: 在过程中就算结果
class Solution { public: int matrixScore(vector<vector<int>>& A) { int m = A.size(); if(m==0) return 0; int n = A[0].size(); //first make first item of every row be positive for(int i =0;i<m;i++){ if(A[i][0] == 1) continue; for(int j = 1;j<n;j++) A[i][j] = 1 - A[i][j]; } int res = m; // now check every column, if more zero than one, then flip for(int j = 1; j <n; j++){ int count1 =0; for(int i = 0;i<m;i++) count1 += A[i][j]; res = res * 2 + max(count1, m - count1); } return res; } };
继续优化: 直接不修改,反而在column 检查的时候, 和行首字母对比
class Solution { public: int matrixScore(vector<vector<int>>& A) { int m = A.size(), n = A[0].size(); int res = m; for(int j = 1; j <n; j++){ int count1 =0; for(int i = 0;i<m;i++) count1 += (A[i][j] ^ A[i][0]); res = (res << 1) + max(count1, m - count1); } return res; } };
No comments:
Post a Comment