[Swift]LeetCode1072.按列翻转得到最大值等行数|FlipColumnsForMaximumNumberofEqualR ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/ ）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10962559.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column. Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.

Example 1:

Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

Note:

1 <= matrix.length <= 300
1 <= matrix[i].length <= 300
All matrix[i].length's are equal
matrix[i][j] is 0 or 1

给定由若干 0 和 1 组成的矩阵 matrix，从中选出任意数量的列并翻转其上的每个单元格。翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。

返回经过一些翻转后，行上所有值都相等的最大行数。

示例 1：

输入：[[0,1],[1,1]]
输出：1
解释：不进行翻转，有 1 行所有值都相等。

示例 2：

输入：[[0,1],[1,0]]
输出：2
解释：翻转第一列的值之后，这两行都由相等的值组成。

示例 3：

输入：[[0,0,0],[0,0,1],[1,1,0]]
输出：2
解释：翻转前两列的值之后，后两行由相等的值组成。

提示：

1 <= matrix.length <= 300
1 <= matrix[i].length <= 300
所有 matrix[i].length 都相等
matrix[i][j] 为 0 或 1

Runtime: 1508 ms

Memory Usage: 21.3 MB

 1 class Solution {
 2     func maxEqualRowsAfterFlips(_ matrix: [[Int]]) -> Int {
 3         var map:[String:Int] = [String:Int]()
 4         for x in matrix
 5         {
 6             var s:String = String()
 7             let flag:Int = x[0]
 8             for i in 0..<x.count
 9             {
10                 if x[i] == flag
11                 {
12                     s.append("1")
13                 }
14                 else
15                 {
16                     s.append("0")
17                 }
18             }
19             map[s,default:0] += 1
20         }
21         var result:Int = 0
22         for val in map.values
23         {
24             result = max(result,val)
25         }
26         return result
27     }
28 }

1600ms

 1 class Solution {
 2     func maxEqualRowsAfterFlips(_ matrix: [[Int]]) -> Int {
 3         var patternCountMap = [Int:Int]()
 4         let mask = 1 << matrix[0].count - 1
 5         return matrix.reduce(0) {
 6             let pattern = $1.reduce(0) { $0 << 1 | $1 } & mask
 7             if patternCountMap[pattern] != nil {
 8                 patternCountMap[pattern]! += 1
 9                 patternCountMap[mask - pattern]! += 1
10             } else {
11                 patternCountMap[pattern] = 1
12                 patternCountMap[mask - pattern] = 1
13             }
14             return max($0, patternCountMap[pattern]!)
15         }
16     }
17 }