0861. Score After Flipping Matrix

题目信息

题号:

0861

难度:

Medium

主题:

二进制矩阵、行列翻转、最大得分

原题:

LeetCode 0861

重点:

每次可翻转整行或整列并重复任意次;最终每行按左侧为最高位的二进制数计值,目标最大化各行之和

题目重述

给定一个 m x n 二进制矩阵 grid。一次操作可以选择任意一整行或一整列,把其中所有 0 与 1 互换;可以执行任意次数,也可以不执行操作。

操作结束后,把每一行从左到右视为一个长度为 n 的二进制数,最左侧是最高位。矩阵得分等于所有行对应整数之和。请返回能够取得的最大得分。

m == grid.length,n == grid[i].length,1 <= m, n <= 20,矩阵元素只可能为 0 或 1。

自建示例

行列翻转共同提高得分:

输入:grid = [[0,1],[1,0]]
输出:6
解释:先翻转第一行得到 [[1,0],[1,0]],再翻转第二列得到 [[1,1],[1,1]];两行二进制值都为 3,总得分为 6。

单格矩阵已经取得最大值:

输入:grid = [[1]]
输出:1
解释:行列数都达到题目允许的最小值。唯一一行表示二进制数 1,已经是该单格矩阵的最大可能得分,无需翻转。