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讲 数组与广义表

LOC(a00)表示第一个元素的存储位置,即基地址,LOC(aij)表示aij的存储位置。 授人以鱼不如授人以渔,告诉你记住公式,就像送你一条鱼,不如交给你捕...

1202
来自专栏AI派

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

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

2933
来自专栏郭耀华‘s Blog

TensorFlow 常用函数汇总

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

洛谷P1887 乘积最大3

题目描述 请你找出M个和为N的正整数,他们的乘积要尽可能的大。 输出字典序最小的一种方案。 输入输出格式 输入格式: 一行,两个正整数N,M 输出格式: M个...

3418
来自专栏崔庆才的专栏

Attention原理及TensorFlow AttentionWrapper源码解析

2.4K4
来自专栏magicsoar

动态规划(dynamic programming)

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

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

Q221 Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square contai...

3745
来自专栏个人分享

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减序列的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2...

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

16:最长单词2

16:最长单词2 总时间限制: 1000ms 内存限制: 65536kB描述 一个以'.'结尾的简单英文句子,单词之间用空格分隔,没有缩写形式和其它特殊形式...

3725
来自专栏Python小屋

Python标准库random用法精要

random标准库主要提供了伪随机数生成函数和相关的类,同时也提供了SystemRandom类(也可以直接使用os.urandom()函数)来支持生成加密级别要...

2936

扫码关注云+社区