https://leetcode.com/problems/score-after-flipping-matrix/description/
本题需要知道一个数字规律，即pow(2,n) > sum(pow(2,0)+pow(2,1)+...+pow(2,n-1))。所以，为了获得最大值，要保证所有行的最高位是1，即需要优先进行行变换，把最高位变成1。接下来就是列变换，把0多于1的列做变换变成1多于0的列即可
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
https://buptwc.com/2018/07/02/Leetcode-861-Score-After-Flipping-Matrix/
- 一个二维矩阵A，我们对其进行两种操作，一种是将某一列中的0，1全部反转，一种是将某一行的0，1全部反转
- 进行若干次操作后按照每一行的数将其变为二进制数，使得所有行求和最大
- 如果我们单分析一行，如例子中第一行，0011，我们知道在四位二进制数中后三位的和为7，第一位就有8，所以可以断定在最优情况下，首位数字必要变成1，所有行同理（贪心）。
- 当第一位全为1后，根据贪心我们想使第二位尽量多1，此时只能改列（改行可能使首位数字变动），也就是对于第二列，如果1的数量比0少，那么我们就进行一次列反转，反之就不进行操作，之后每一列以此类推！
按照上述操作后我们观察示例中矩阵A中元素变换过程，首先先将首位全部变为1，然后：
1 1 0 0 — — — — — — — — > 1 1 0 0 — — — — — — — — > 1 1 1 0 — — — — — — — — > 1 1 1 1
1 0 1 0 — —第二列1多— — —> 1 0 1 0 — —第三列0多— — —> 1 0 0 0 — —第四列0多— — —> 1 0 0 1
1 1 0 0 — — — — — — — — > 1 1 0 0 — — — — — — — — > 1 1 1 0 — — — — — — — — > 1 1 1 1
1 1 0 0 — — — — — — — — > 1 1 0 0 — — — — — — — — > 1 1 1 0 — — — — — — — — > 1 1 1 1
1 0 1 0 — —第二列1多— — —> 1 0 1 0 — —第三列0多— — —> 1 0 0 0 — —第四列0多— — —> 1 0 0 1
1 1 0 0 — — — — — — — — > 1 1 0 0 — — — — — — — — > 1 1 1 0 — — — — — — — — > 1 1 1 1
思路：
- 先判断每行第一个元素是否为0，若为0则进行一次行变换
- 然后对每一列进行0，1数量的判断，若0多，则进行一次列变换，也就是将1，0的个数对调
def matrixScore(self, A): """ :type A: List[List[int]] :rtype: int """ m,n = len(A),len(A[0]) # 行变换 for i in range(m): if A[i][0] == 1: continue for j in range(n): A[i][j] = 1 - A[i][j] # 列变换 res = 0 for rows in zip(*A): # 始终使1的个数是更大的 cnt1 = max(rows.count(1), rows.count(0)) res += cnt1 * 2**(n-1) n -= 1 return reshttps://www.cnblogs.com/seyjs/p/9252453.html
本题需要知道一个数字规律，即pow(2,n) > sum(pow(2,0)+pow(2,1)+...+pow(2,n-1))。所以，为了获得最大值，要保证所有行的最高位是1，即需要优先进行行变换，把最高位变成1。接下来就是列变换，把0多于1的列做变换变成1多于0的列即可
Approach 2: Greedy
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.
public int matrixScore(int[][] A) {
int R = A.length, C = A[0].length;
int ans = 0;
for (int c = 0; c < C; ++c) {
int col = 0;
for (int r = 0; r < R; ++r)
col += A[r][c] ^ A[r][0];
ans += Math.max(col, R - col) * (1 << (C - 1 - c));
}
return ans;
}
https://www.codetd.com/article/2422679
题目解析：将各个数看作矩阵，将每个数按照数位来分，显然每个数的第一位是要保证都为1的（因为它比 A[i][1] + .. + A[i][m-1] 更大），分成两步——
- 先进行行翻转，让A[i][0] = 0，此时 A[i][j]==1 的条件为A[i][j] == A[i][0]；
- 后面的数位从列的角度来看，每列代表一个数位，要让每列有尽可能多的1，比较该列翻转与否中1的个数就可以获得较大值，相加即可。
int matrixScore(vector<vector<int>>& A) {
int n = A.size(), m = A[0].size();
int ans = (1 << (m - 1)) * n;
for (int i = 1; i < m; i++)
{
int num = 0;
for (int j = 0; j < n; j++)
num += (A[j][i] == A[j][0]);
ans += max(num, n - num) * (1 << (m - i - 1));
}
return ans;
}
Assume
A is M * N.A[i][0]is worth1 << (N - 1)points, more than the sum of (A[i][1] + .. + A[i][N-1]).
We need to toggle allA[i][0]to1, here I toggle all lines forA[i][0] = 0.A[i][j]is worth1 << (N - 1 - j)
For every col, I count the current number of1s.
After step 1,A[i][j]becomes1ifA[i][j] == A[i][0].
ifM - cur > cur, we can toggle this column to get more1s.max(M, M - cur)will be the maximum number of1s that we can get.
public int matrixScore(int[][] A) {
int M = A.length, N = A[0].length, res = (1 << (N - 1)) * M;
for (int j = 1; j < N; j++) {
int cur = 0;
for (int i = 0; i < M; i++) cur += A[i][j] == A[i][0] ? 1 : 0;
res += Math.max(cur, M - cur) * (1 << (N - j - 1));
}
return res;
}
Notice that a
1 in the th column from the right, contributes to the score.
Say we are finished toggling the rows in some configuration. Then for each column, (to maximize the score), we'll toggle the column if it would increase the number of
1s.
We can brute force over every possible way to toggle rows.
Algorithm
Say the matrix has
R rows and C columns.
For each
state, the transition trans = state ^ (state-1) represents the rows that must be toggled to get into the state of toggled rows represented by (the bits of) state.
We'll toggle them, and also maintain the correct column sums of the matrix on the side.
Afterwards, we'll calculate the score. If for example the last column has a column sum of
3, then the score is max(3, R-3), where R-3 represents the score we get from toggling the last column.
In general, the score is increased by
max(col_sum, R - col_sum) * (1 << (C-1-c)), where the factor (1 << (C-1-c)) is the power of 2 that each 1 contributes.
Note that this approach may not run in the time allotted.
- Time Complexity: , where is the number of rows and columns in the matrix.
- Space Complexity: in additional space complexity.
public int matrixScore(int[][] A) {
int R = A.length, C = A[0].length;
int[] colsums = new int[C];
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c)
colsums[c] += A[r][c];
int ans = 0;
for (int state = 0; state < (1 << R); ++state) {
// Toggle the rows so that after, 'state' represents
// the toggled rows.
if (state > 0) {
int trans = state ^ (state - 1);
for (int r = 0; r < R; ++r) {
if (((trans >> r) & 1) > 0) {
for (int c = 0; c < C; ++c) {
colsums[c] += A[r][c] == 1 ? -1 : 1;
A[r][c] ^= 1;
}
}
}
}
// Calculate the score with the rows toggled by 'state'
int score = 0;
for (int c = 0; c < C; ++c)
score += Math.max(colsums[c], R - colsums[c]) * (1 << (C - 1 - c));
ans = Math.max(ans, score);
}
return ans;
}
Optimize the total sum in two steps:
- Flip all rows that start with zero;
- Flip all columns where the number of zeros is larger than the number of ones;
In binary representation, the following holds true:
- 100 > 011
- 1000 > 0111
- 10000 > 01111
- etc.
That is, the first bit gives us more upside than all the rest bits combined. Thus, first and foremost, we flip all rows that have the largest bit equal to zero (step 1).
Afterwards, we try to maximize what's left. We no longer want to flip rows, as this would turn our largest and most valuable bits to zero. Instead, we go over each column and see if it makes sense to flip it. Whenever the number of zeros in a column is more than the number of ones, it makes sense to flip it. That's what we do in step 2.
Afterwards, we try to maximize what's left. We no longer want to flip rows, as this would turn our largest and most valuable bits to zero. Instead, we go over each column and see if it makes sense to flip it. Whenever the number of zeros in a column is more than the number of ones, it makes sense to flip it. That's what we do in step 2.
public int matrixScore(int[][] A) {
int N = A.length,
M = A[0].length;
// Optimize, step1: flip all rows starting with a zero
for (int i = 0; i < N; ++i) {
if (A[i][0] == 0)
flipRow(A, i);
}
// Optimize, step 2: flip all columns where the number of zeros is larger than the number of ones
for (int col = 1; col < M; ++col) {
int sumCol = 0;
for (int i = 0; i < N; ++i)
sumCol += A[i][col];
if (sumCol * 2 < N)
flipCol(A, col);
}
// Count final sum
int total = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
total += A[i][j] * (1 << (M-j-1));
return total;
}
void flipRow(int[][] a, int r) {
for (int i = 0; i < a[r].length; ++i)
a[r][i] = (a[r][i] ^ 1);
}
void flipCol(int[][] a, int c) {
for (int i = 0; i < a.length; ++i)
a[i][c] = (a[i][c] ^ 1);
}
The basic proof strategy of Greedy algorithm is that we're going to try to prove that the algorithm never makes a bad choice.
In our case, we flip rows starting with 0 for they are most significant digits. And then, we flip columns (excluding the first column) with more 0s than 1s. We never make a bad choice.
In our case, we flip rows starting with 0 for they are most significant digits. And then, we flip columns (excluding the first column) with more 0s than 1s. We never make a bad choice.
Let S be the solution output by the algorithm and O be the optimum solution. If S is different from O, then we can tweak O to get another solution O' that is different from O and strictly better than O.
O is promised to be optimum. The moment S differs from O, S is the optimum (since we never make a bad choice). They are in contradiction with each other.
O is promised to be optimum. The moment S differs from O, S is the optimum (since we never make a bad choice). They are in contradiction with each other.
Thus, our algorithm is turned out to be the optimum.
https://blog.ksgin.com/2018/07/07/Score-After-Flipping-Matrix/
- 每一行的第一个数字代表二进制的最高位，因此，首先需要翻转行，以使该位为
1。 - 每一列的
1的权重（即转换为二进制后的值）是一致的，因此为了使得和最大，我们需要翻转列，使得每一列的1的个数大于0的个数。
贪心算法，我们知道二进制串中越高位的占的比重越大，所以我们可以直接从高到底来判断是否进行 toggling 操作。
首先为行，行中每个数字的权重不一样，从高往低，所以在行中我们只需要对第一位进行判断（即数组第一个数字），当他为0的时候我们要将他变为1 就需要 toggling ，这样可以使这一行数字的二进制串最大。
列中每一列的权重一样，所以我们需要判断这一列中1的个数和0的个数，当0的个数大于1的个数时我们进行 toggling 操作。
