[LeetCode]Score After Flipping Matrix

这道题很容易想到贪婪的方法。因为每一行对应一个二进制数字，我们一定可以把依次每一行的most significant bit反转成1。接下来我们只需要判断是否需要反转每一列了，因为反转列的话，每个1代表的值是一样的，都是2^k，k为从右到左的index。所以我们只需要判断反转之后能不能得到比之前多的1即可，如果可以我们显然应该反转这一列。时间复杂度方面，假设输入矩阵为m x n，那么为O(m * n)，空间复杂度O(1)。代码如下：

	class Solution {
	public:
	int matrixScore(vector<vector<int>>& A) {
	int m = A.size(), n = m ? A[0].size() : 0, res = 0;
	for (int j = 0; j < n; ++j)
	{
	int col = 0;
	for (int i = 0; i < m; ++i)
	{
	//counts digits which are same as A[i][0]
	col += A[i][0] ^ A[i][j];
	}
	res += (1 << (n - 1 - j)) * max(col, m - col);
	}
	return res;
	}
	};

view raw Score After Flipping Matrix.cpp hosted with ❤ by GitHub