客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ We have a two dimensional matrix A move consists of choosing any row or column, and toggling each value in that row or column: changing all 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:
有一个二维矩阵 移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。 返回尽可能高的分数。 示例： 输入：[[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 提示：
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 }
|
请发表评论