翻转矩阵后的得分 图解题解

这道题到底在问什么

输入

grid=[[0,0,1,1],[1,0,1,0],[1,1,0,0]]

输出

39

输入

最优翻法后

输出

1111 + 1001 + 1111 = 15 + 9 + 15 = 39

最优解：一步一步想明白

1. 3记牢这把尺子:首列必须全 1(最高位优先),其余每列让 1 尽量多——1 少于 0 才翻、相等不动,最终 1 不少于 0。下面每一帧都在套它。
2. 4原矩阵 3 行 4 列,每格非 0 即 1这是原始矩阵,绿色格是 1、蓝色格是 0。我们先处理行、再处理列。先想清楚:每行的最左边是最高位,一个高位的 1 抵得上后面好几位,所以最该先抢的就是首列。
3. 5只要某行首位是 0,就翻整行,把最高位抢成 1紫色这一列是首列,也就是每行的最高位。我们一行一行检查它的首位:是 1 就不动,是 0 就把整行翻过来。先从第 0 行开始。
4. 6第 0 行 = [0, 0, 1, 1],首位是 0轮到第 0 行,内容是 [0, 0, 1, 1]。它的首位是 0。首位是 0,最高位还没抢到手,这一整行得翻一次。
5. 7第 0 行现在 = [1, 1, 0, 0],首位 = 1整行翻过来(红色闪一下),第 0 行变成 [1, 1, 0, 0],首位现在是 1,最高位拿下了。
6. 8第 1 行 = [1, 0, 1, 0],首位是 1轮到第 1 行,内容是 [1, 0, 1, 0]。它的首位是 1。首位已经是 1,最高位到手,这一行不用动。
7. 9第 1 行现在 = [1, 0, 1, 0],首位 = 1第 1 行原样保留,首位本来就是 1,白翻还会把它弄丢,不动它。
8. 10第 2 行 = [1, 1, 0, 0],首位是 1轮到第 2 行,内容是 [1, 1, 0, 0]。它的首位是 1。首位已经是 1,最高位到手,这一行不用动。
9. 11第 2 行现在 = [1, 1, 0, 0],首位 = 1第 2 行原样保留,首位本来就是 1,白翻还会把它弄丢,不动它。
10. 12三行处理完,首列三个格全部为 1第一步收工。看紫色的首列,现在三个格全是 1,每一行的最高位都抢到了手。矩阵变成 [1,1,0,0]、[1,0,1,0]、[1,1,0,0]。接下来处理其余各列,让低位也尽量多挣分。
11. 13某列 1 少于 0,就翻整列让 1 变多(相等不翻)第二步换个方向,逐列看。每一列数一数有几个 1,如果 1 的个数少于 0,就把整列翻过来;相等就不翻,目标是让每列 1 不少于 0。注意首列已经全是 1 了,翻它只会变差,所以从第 1 列起真正可能动手。
12. 14第 0 列 = [1, 1, 1],1 有 3 个、0 有 0 个看第 0 列(紫色),从上到下是 [1, 1, 1]。数一下:1 有 3 个,0 有 0 个。这是首列,刚抢成全 1,自然不用翻。
13. 15第 0 列现在 = [1, 1, 1],1 有 3 个第 0 列保持不动,1 本来就有 3 个、不少于 0,翻了反而变少。
14. 16第 1 列 = [1, 0, 1],1 有 2 个、0 有 1 个看第 1 列(紫色),从上到下是 [1, 0, 1]。数一下:1 有 2 个,0 有 1 个。1 不少于 0,保持不动。
15. 17第 1 列现在 = [1, 0, 1],1 有 2 个第 1 列保持不动,1 本来就有 2 个、不少于 0,翻了反而变少。
16. 18第 2 列 = [0, 1, 0],1 有 1 个、0 有 2 个看第 2 列(紫色),从上到下是 [0, 1, 0]。数一下:1 有 1 个,0 有 2 个。1 少于 0,这一列翻过来更划算。
17. 19第 2 列现在 = [1, 0, 1],1 有 2 个整列翻过来(红色闪一下),第 2 列变成 [1, 0, 1],现在 1 有 2 个,1 不少于 0 了。
18. 20第 3 列 = [0, 0, 0],1 有 0 个、0 有 3 个看第 3 列(紫色),从上到下是 [0, 0, 0]。数一下:1 有 0 个,0 有 3 个。1 少于 0,这一列翻过来更划算。
19. 21第 3 列现在 = [1, 1, 1],1 有 3 个整列翻过来(红色闪一下),第 3 列变成 [1, 1, 1],现在 1 有 3 个,1 不少于 0 了。
20. 22四列都处理完,矩阵 = [1, 1, 1, 1] / [1, 0, 0, 1] / [1, 1, 1, 1]第二步收工,矩阵不再翻动了。现在每一行是 [1111]、[1001]、[1111]。最后一步,把每一行当成二进制数算出来,再加到一起。
21. 23第 0 行 1111 的十进制值是 15把第 0 行(紫色)按二进制读:1111,换成十进制就是 15。累计得分加上它,现在是 15。
22. 24第 1 行 1001 的十进制值是 9把第 1 行(紫色)按二进制读:1001,换成十进制就是 9。累计得分加上它,现在是 24。
23. 25第 2 行 1111 的十进制值是 15把第 2 行(紫色)按二进制读:1111,换成十进制就是 15。累计得分加上它,现在是 39。
24. 26三行求和 15 + 9 + 15 = 39三行加起来:15 加 9 加 15,等于 39。这就是最大得分。先翻行保最高位、再翻列让每列 1 不少于 0,这套贪心一定最优。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] ^= 1
        ans = 0
        for j in range(n):
            cnt = sum(grid[i][j] for i in range(m))
            ans += max(cnt, m - cnt) * (1 << (n - j - 1))
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] ^= 1;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                cnt += grid[i][j];
            }
            ans += max(cnt, m - cnt) * (1 << (n - j - 1));
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] ^= 1;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                cnt += grid[i][j];
            }
            ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
        }
        return ans;
    }
}

复杂度

面试官可能追问