leetcode(三)

leedcode—problem861

rank:medium

1.问题

给定一个二维的矩阵(矩阵的数全由1和0组成),任意反转矩阵的每一行和每一列(0反转成1,1反转成0),求出最大矩阵分数,矩阵分数的求法是矩阵每一行代表二进制数,首位是最高位,根据二进制求出十进制,计算出每一行的十进制后,将所有十进制相加,返回结果,详细描述如图所示

2.解决方案

 1 class Solution:
 2     def matrixScore(self, A):
 3         """
 4         :type A: List[List[int]]
 5         :rtype: int
 6         """
 7         height = len(A)
 8         width = len(A[0])
 9         
10         def toggle_row(A, row):
11             for j in range(width):
12                 if A[row][j]:
13                     A[row][j] = 0
14                 else:
15                     A[row][j] = 1
16             return A
17         
18         def toggle_column(A, column):
19             for i in range(height):
20                 if A[i][column]:
21                     A[i][column] = 0
22                 else:
23                     A[i][column] = 1
24             return A
25         
26         def count_column_one(A, column):
27             num = 0
28             for i in range(height):
29                 if A[i][column] == 1:
30                     num += 1
31             return num
32                     
33         for i in range(height):
34             if A[i][0] == 0:
35                 A = toggle_row(A, i)
36         
37         for j in range(width-1):
38             num = count_column_one(A, j+1)
39             if num < height/2:
40                 A = toggle_column(A,j+1)
41         from functools import reduce
42         result = 0 
43         for i in range(height):
44             result += reduce(lambda x,y: x*2+y, A[i])
45         return result

具体思路:首先我们要知道怎么能求出最大矩阵分数,一个二进制数,它的值大小,最高位是贡献最大(1/2值),比后面低位加起来贡献还大,所以要使这个二进制数尽可能大,最高位必须为1,也就是矩阵所有的行的第一位需置1,所以这里有一个toggle_row函数,用来反转行让首位置1。然后再是列反转,列反转的条件是在当前列,数字1的个数小于矩阵行数的1/2,则说明0的个数较多,反转列(使用toggle_column)将增大结果,依次循环第二列到最后一列即可。最后利用reduce函数求出每一行的结果并进行求和即可。

参考

1.https://leetcode.com/contest/weekly-contest-91/problems/score-after-flipping-matrix/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏余林丰

9.动态规划(2)——子集和问题

注:因为对“子集和问题”的学习不够深入,所以本文在讲解动态规划递推公式中可能存在叙述不清,或者错误的地方,如有发现望能不吝赐教。   子集和问题可描述如下:给定...

40880
来自专栏郭耀华‘s Blog

TensorFlow 常用函数汇总

83220
来自专栏数据结构与算法

单调栈小结

18010
来自专栏崔庆才的专栏

Attention原理及TensorFlow AttentionWrapper源码解析

3.4K40
来自专栏数据结构与算法

P1378 油滴扩展

题目描述 在一个长方形框子里,最多有N(0≤N≤6)个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必...

29180
来自专栏AI派

Numpy 修炼之道 (7)—— 形状操作

无论是ravel、reshape、T,它们都不会更改原有的数组形状,都是返回一个新的数组。

30230
来自专栏Bingo的深度学习杂货店

最小方差划分

给一个数组,求一个k值,使得前k个数的方差 + 后面n-k个数的方差最小 解题思路: 如果不考虑方差的概念,这题可以简化为 “给一个数组,求一个k值,使得前k个...

58330
来自专栏偏前端工程师的驿站

代数几何:点,线,抛物线,圆,球,弧度和角度

一, 笛卡尔坐标系                         ? 笛卡尔坐标系是数学中的坐标系,而计算机中则采用屏幕坐标系统. ? 而三维坐标系则没有一个...

27180
来自专栏magicsoar

动态规划(dynamic programming)

动态规划的基本思想 动态规划的基本思想在于发现和定义问题中的子问题,这里子问题可也以叫做状态;以及一个子问题到下一个子问题之间 是如何转化的 也就是状态转移方程...

35450
来自专栏数据结构与算法

27:单词翻转

27:单词翻转 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个句子(一行),将句子中的每一个单词翻转后输出。 输入只有一行,为一个...

43770

扫码关注云+社区

领取腾讯云代金券