[Swift]LeetCode861. 翻转矩阵后的得分 | Score After Flipping Matrix

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）

➤GitHub地址：https://github.com/strengthen/LeetCode

➤原文地址： https://www.cnblogs.com/strengthen/p/10595500.html

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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

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

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

We have a two dimensional matrix A where each value is 0 or 1.

A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

Example 1:

Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation:
Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39 

Note:

1. 1 <= A.length <= 20
2. 1 <= A[0].length <= 20
3. A[i][j] is 0 or 1.

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。

返回尽可能高的分数。

示例：

输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：
转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39 

提示：

1. 1 <= A.length <= 20
2. 1 <= A[0].length <= 20
3. A[i][j] 是 0 或 1

Runtime: 12 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func matrixScore(_ A: [[Int]]) -> Int {
 3         var temp1 = A
 4         //先将第一咧都转为1
 5         for i in 0..<temp1.count {
 6             let arr = temp1[i]
 7             if arr[0] == 0{
 8                 temp1[i] = arr.map({ 1 - $0 })
 9             }
10         }
11         //让之后的每列尽可能多的1 0的个数+1的个数 = 固定
12         var res = 0
13         for i in 0..<temp1[0].count{
14             var s = 0
15             for j in 0..<temp1.count{
16                 if temp1[j][i] == 1{
17                     s += 1
18                 }
19             }
20             s = s > (temp1.count-s) ? s : temp1.count-s
21             var more = 1 << (temp1[0].count-i-1)
22             more = more * s
23             res += more
24         }
25         return res
26     }
27 }

Runtime: 12 ms

Memory Usage: 18.7 MB

 1 class Solution {
 2     func matrixScore(_ A: [[Int]]) -> Int {
 3         var M:Int = A.count
 4         var N:Int = A[0].count
 5         var res:Int = (1 << (N - 1)) * M
 6         for j in 1..<N
 7         {
 8             var cur:Int = 0
 9             for i in 0..<M
10             {
11                 cur += A[i][j] == A[i][0] ? 1 : 0
12             }
13             res += max(cur, M - cur) * (1 << (N - j - 1))
14         }
15         return res
16     }
17 }

12ms

 1 class Solution {
 2     func matrixScore(_ Z: [[Int]]) -> Int {
 3         var A = Z
 4         var sum = 0
 5         let M = A.count
 6         let N = A[0].count
 7         // Flip row if first item is 0
 8         for (i, a) in A.enumerated() {
 9             if a[0] == 0 {
10                 A[i] = a.map { x in
11                     return 1 - x
12                 }
13             }
14         }
15         // Flip column to get more 1s then 0s
16         for j in 1..<N {
17             var oneCount = 0
18             for i in 0..<M {
19                 if A[i][j] == 1 {
20                     oneCount += 1
21                 }
22             }
23             if oneCount < M - oneCount {
24                 for i in 0..<M {
25                     A[i][j] = 1 - A[i][j]
26                 }
27             }
28         }
29         for a in A {
30             sum += arrayToNum(a)
31         }
32         return sum
33     }
34     
35     private func arrayToNum(_ A: [Int]) -> Int {
36         var sum = 0
37         for a in A {
38             sum = (sum << 1) + a
39         }
40         return sum
41     }
42 }

16ms

 1 class Solution {
 2     func matrixScore(_ Arr: [[Int]]) -> Int {
 3         var A = Arr
 4         for i in 0..<A.count {
 5             let row = A[i]
 6             if row[0] == 0 {
 7                 A = flipMatrix(A, row: i)
 8             }
 9         }
10 
11         for i in 0..<A[0].count {
12             let col = get(col: i, for: A)
13             let total = col.reduce(0) { $0 + $1 }
14             if total * 2 < col.count {
15                 A = flipMatrix(A, col: i)
16             }
17         }
18         
19         return A.reduce(0) { lastValue, row in
20             lastValue + computeScore(row)
21         }
22     }
23     
24     private func computeScore(_ A: [Int]) -> Int {
25         var val = 0
26         for i in A  {
27             val *= 2
28             val += i
29         }
30         return val
31     }
32     
33     private func flipMatrix(_ A: [[Int]], col: Int) -> [[Int]] {
34         var newA = [[Int]]()
35         for row in A {
36             var newRow = row
37             newRow[col] = newRow[col] == 0 ? 1 : 0
38             newA.append(newRow)
39         }
40         
41         return newA
42     }
43     
44     private func flipMatrix(_ Arr: [[Int]], row: Int) -> [[Int]] {
45         var A = Arr
46         var copiedRow = A[row]
47         copiedRow = copiedRow.map({ $0 == 0 ? 1 : 0})
48         A[row] = copiedRow
49         return A
50     }
51     
52     private func get(col: Int, for A: [[Int]]) -> [Int] {
53         return A.map({ $0[col] })
54     }
55 }

20ms

 1 class Solution {
 2     func matrixScore(_ A: [[Int]]) -> Int {
 3         var matrix = A
 4         for i in 0..<matrix.count {
 5             let row = matrix[i]
 6             if row.first == 0 {
 7                 matrix[i] = row.map({ $0 == 0 ? 1 : 0})
 8             }
 9         }
10 
11         for j in 0..<matrix[0].count {
12             var sum = 0
13             for i in 0..<matrix.count where matrix[i][j] == 1 {
14                 sum += 1
15             }
16             if sum <= matrix.count / 2 {
17                 for i in 0..<matrix.count {
18                     matrix[i][j] = matrix[i][j] == 0 ? 1 : 0
19                 }
20             }
21         }
22 
23         var result = 0
24         for row in matrix {
25             var v = 0
26             for i in 0..<row.count {
27                  v |= row[i] << (row.count-1-i)
28             }
29             result += v
30         }
31 
32         return result
33     }
34 }

20ms

 1 class Solution {
 2     typealias IntArray = [Int]
 3     func flip(HorizontalOf Matrix:inout [IntArray] , at level : Int){
 4         for position in 0 ..<  Matrix[level].count {
 5             Matrix[level][position] ^= 1
 6         }
 7     }
 8     func flip(VerticalOf Matrix:inout [IntArray] , at position : Int){
 9         for level in 0 ..<  Matrix.count {
10             Matrix[level][position] ^= 1
11         }
12     }
13     //按照思路的解法,耗时很长
14     func matrixScore(_ A: [IntArray]) -> Int {
15         if A.count <= 1 {
16             return A.count
17         }
18 
19         var A = A
20 
21         //使最高位都变成1
22         for vIdx in 0..<A.count {
23             if A[vIdx][0] == 0 {
24                 //翻转水平列
25                 flip(HorizontalOf: &A, at: vIdx)
26             }
27         }
28 
29         var count = 0
30         //根据每竖的0的个数判断是否需要翻转竖列
31         for hIdx in 1..<A[0].count {
32             count = 0
33             for vIdx in 0..<A.count {
34                 if A[vIdx][hIdx] == 0 {
35                     count += 1
36                 }
37             }
38             if count > A.count/2 {
39                 flip(VerticalOf: &A, at: hIdx)
40             }
41         }
42 
43         var result : Int = 0
44         var carry :Int = 1
45         //计算对应的十进制值
46         for vIdx in (0..<A[0].count).reversed(){
47             for hIdx in 0..<A.count {
48                 result += A[hIdx][vIdx] * carry
49             }
50             carry *= 2
51         }
52         return result
53     }
54 }

24ms

 1 class Solution {
 2     func matrixScore(_ A: [[Int]]) -> Int {
 3     var arr = A
 4     
 5     // 先将第一列转成1
 6     for i in 0..<arr.count {
 7         if arr[i][0] == 0 {
 8             arr[i] = arr[i].map{ $0 == 0 ? 1 : 0 }
 9         }
10     }
11     
12     for j in 0..<arr[0].count {
13         // 统计一列中为1的数量
14         var sum = 0
15         for i in 0..<arr.count where arr[i][j] == 1 {
16             sum += 1
17         }
18         
19         // 如果一列为1的数量少于一半，则该列反转
20         if sum <= (arr.count/2) {
21             for i in 0..<arr.count {
22                 arr[i][j] = arr[i][j] == 0 ? 1 : 0
23             }
24         }
25     }
26     
27     // 计算
28     var sum = 0
29     for i in 0..<arr.count {
30         let str = arr[i].map({ String($0) }).reduce("", +)
31         sum += Int(str, radix: 2) ?? 0
32     }
33     
34     return sum
35    }
36 }