★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10504894.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
We may rotate the i-th domino, so that A[i] and B[i] swap values.
Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same.
If it cannot be done, return -1.
Example 1:
Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
Output: 2
Explanation:
The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
Example 2:
Input: A = [3,5,1,2,3], B = [3,6,3,3,4]
Output: -1
Explanation:
In this case, it is not possible to rotate the dominoes to make one row of values equal.
Note:
1 <= A[i], B[i] <= 62 <= A.length == B.length <= 20000
在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）
我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。
返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。
如果无法做到，返回 -1.
示例 1：
输入：A = [2,1,2,4,2,2], B = [5,2,6,2,3,2] 输出：2 解释： 图一表示：在我们旋转之前， A 和 B 给出的多米诺牌。 如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。
示例 2：
输入：A = [3,5,1,2,3], B = [3,6,3,3,4] 输出：-1 解释： 在这种情况下，不可能旋转多米诺牌使一行的值相等。
提示：
1 <= A[i], B[i] <= 62 <= A.length == B.length <= 20000
Runtime: 512 ms
Memory Usage: 19.2 MB
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 var n:Int = A.count 4 var best:Int = Int.max 5 for same in 1...6 6 { 7 var a_cost:Int = 0 8 var b_cost:Int = 0 9 10 for i in 0..<n 11 { 12 if A[i] != same && B[i] != same 13 { 14 a_cost = Int.max 15 b_cost = Int.max 16 break; 17 } 18 if A[i] != same 19 { 20 a_cost += 1 21 } 22 if B[i] != same 23 { 24 b_cost += 1 25 } 26 } 27 best = min(best, min(a_cost, b_cost)) 28 } 29 return best < Int.max / 2 ? best : -1 30 } 31 }
512ms
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 var candidate = A.count + 1 4 var candidateNum = 0 5 for num in 1 ... 6 { 6 var count = 0 7 var i = 0 8 var aCount = 0 9 var bCount = 0 10 while i < A.count { 11 if A[i] != num && B[i] != num { 12 break 13 } 14 15 if A[i] != num { 16 aCount += 1 17 } else if B[i] != num { 18 bCount += 1 19 } 20 i += 1 21 } 22 23 if i == A.count { 24 if aCount < candidate { 25 candidate = aCount 26 candidateNum = num 27 } 28 if bCount < candidate { 29 candidate = bCount 30 candidateNum = num 31 } 32 33 } 34 } 35 if candidateNum == 0 { 36 return -1 37 } 38 return candidate 39 } 40 }
520ms
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 guard A.count == B.count else { return -1 } 4 var candidate_a = A[0] 5 var candidate_b = B[0] 6 var result_A = 0 7 var result_B = 0 8 for i in 1..<A.count { 9 if candidate_a != -1 { 10 if A[i] != candidate_a, B[i] != candidate_a { 11 result_A = Array(A[0..<i]).filter({$0 == candidate_a}).count 12 result_B = Array(B[0..<i]).filter({$0 == candidate_a}).count 13 candidate_a = -1 14 } 15 } 16 if candidate_b != -1 { 17 if A[i] != candidate_b, B[i] != candidate_b { 18 19 result_A = Array(A[0..<i]).filter({$0 == candidate_b}).count 20 result_B = Array(B[0..<i]).filter({$0 == candidate_b}).count 21 candidate_b = -1 22 } 23 } 24 if candidate_a == -1, candidate_b == -1 { 25 return -1 26 } 27 if candidate_a == -1, candidate_b != -1{ 28 if A[i] != candidate_b { 29 result_A += 1 30 } 31 if B[i] != candidate_b { 32 result_B += 1 33 } 34 } else if candidate_b == -1, candidate_a != -1{ 35 if A[i] != candidate_a { 36 result_A += 1 37 } 38 if B[i] != candidate_a { 39 result_B += 1 40 } 41 42 } else { 43 if A[i] != candidate_a{ 44 result_A += 1 45 } 46 if B[i] != candidate_b{ 47 result_B += 1 48 } 49 } 50 } 51 return min(result_A, result_B) 52 } 53 }
536ms
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 var arA: [Int] = [0,0,0,0,0,0,0] 4 var arB: [Int] = [0,0,0,0,0,0,0] 5 var ab = 0 6 for i in (0..<A.count) { 7 arA[A[i]] += 1 8 arB[B[i]] += 1 9 } 10 var freq = -1 11 for i in (1..<7) { 12 if arA[i] + arB[i] >= A.count { 13 freq = i 14 if arA[i] >= arB[i] { ab = 0 } else { ab = 1} 15 } 16 } 17 if freq == -1 { return -1 } 18 print(freq, ab) 19 var res = 0 20 21 for i in (0..<A.count) { 22 if A[i] == freq && B[i] == freq { continue } 23 if A[i] != freq && B[i] != freq { return -1 } 24 if ab == 0 && A[i] != freq { res += 1 } 25 if ab != 0 && B[i] != freq { res += 1 } 26 } 27 28 return res 29 } 30 }
568ms
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 let len = A.count 4 var mapA = [Int: Int](), mapB = [Int: Int]() 5 var mapSame = [Int: Int]() 6 7 var diffCount = 0 8 for i in 0..<len { 9 if A[i] != B[i] { 10 mapA[A[i], default: 0] += 1 11 mapB[B[i], default: 0] += 1 12 diffCount += 1 13 } else { 14 mapSame[A[i], default: 0] += 1 15 } 16 } 17 18 var result = -1 19 for i in 1...6 where mapA[i, default: 0] + mapB[i, default: 0] == diffCount && diffCount + mapSame[i, default: 0] == len { 20 let swapCount = min(mapA[i, default: 0], mapB[i, default: 0]) 21 if result == -1 { 22 result = swapCount 23 } else { 24 result = min(result, swapCount) 25 } 26 } 27 return result 28 } 29 }
576ms
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 var countA = [Int](repeating: 0, count: 7) 4 var countB = [Int](repeating: 0, count: 7) 5 for i in A.indices { 6 countA[A[i]] += 1 7 countB[B[i]] += 1 8 } 9 10 var ans = Int.max 11 for i in 1...6 { 12 if countA[i] + countB[i] >= A.count { 13 for j in A.indices { 14 if A[j] != i && B[j] != i { 15 break 16 } 17 if j == A.count - 1 { 18 let curmin = min(A.count - countB[i], A.count - countA[i]) 19 ans = min(ans, curmin) 20 } 21 } 22 } 23 } 24 return ans == Int.max ? -1 : ans 25 } 26 }
620ms
1 class Solution { 2 func mask(_ a : Int, _ b : Int ) -> Int { 3 return (1 << a) | (1 << b) 4 } 5 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 6 guard A.count > 0 && A.count == B.count else { 7 return -1 8 } 9 var totalMask = 255 10 11 for (a,b) in zip(A, B) { 12 totalMask = totalMask & mask(a, b) 13 } 14 15 guard totalMask != 0 else { 16 return -1 17 } 18 19 var target = B[0] 20 if totalMask & (1 << A[0]) != 0 { 21 target = A[0] 22 } 23 24 var aCount = 0 25 var bCount = 0 26 27 for (a,b) in zip(A, B) { 28 if a == target { 29 aCount += 1 30 } 31 if b == target { 32 bCount += 1 33 } 34 } 35 36 return A.count - max(aCount, bCount) 37 } 38 }
676ms
1 class Solution { 2 3 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 4 let maxA = A.mostRepeatingElement() 5 let maxB = B.mostRepeatingElement() 6 var traversalArray = A 7 var referenceArray = B 8 var needle = maxB.element 9 var swapsExpected = referenceArray.count - maxB.count 10 if maxA.count > maxB.count { 11 traversalArray = B 12 referenceArray = A 13 needle = maxA.element 14 swapsExpected = referenceArray.count - maxA.count 15 } 16 var numberOfSwaps = 0 17 for (index, element) in traversalArray.enumerated() { 18 guard element == needle, referenceArray[index] != needle else { continue } 19 numberOfSwaps += 1 20 } 21 return numberOfSwaps < swapsExpected ? -1 : numberOfSwaps 22 } 23 } 24 25 extension Array where Element == Int { 26 27 func mostRepeatingElement() -> (element: Element, count: Int) { 28 var table: [Element : Int] = [:] 29 forEach { element in 30 if let existingElement = table[element] { 31 table[element] = existingElement + 1 32 } else { 33 table[element] = 1 34 } 35 } 36 var maxCount = 0 37 var maxElement = -1 38 table.keys.forEach { key in 39 let count = table[key] ?? 0 40 if count > maxCount { 41 maxCount = count 42 maxElement = key 43 } 44 } 45 return (element: maxElement, count: maxCount) 46 } 47 }
760ms
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 guard !A.isEmpty && !B.isEmpty else { 4 return 0 5 } 6 7 var set = Set([A[0], B[0]]) 8 9 for i in 1..<A.count { 10 set.formIntersection([A[i], B[i]]) 11 } 12 13 guard set.count > 0 else { return -1 } 14 15 var m = Int.max 16 17 for common in set { 18 let aCount = A.filter { common != $0 }.count 19 let bCount = B.filter { common != $0 }.count 20 m = min(min(aCount, bCount), m) 21 } 22 23 return m 24 } 25 }
796ms
1 class Solution { 2 func minDominoRotations(_ A: [Int], _ B: [Int]) -> Int { 3 var common: Set = [1, 2, 3, 4, 5, 6] 4 for (tile1, tile2) in zip(A, B) { 5 common = common.intersection(Set([tile1, tile2])) 6 if common.count == 0 { 7 return -1 8 } 9 } 10 11 var m: Int = -1 12 for tile in common { 13 m = max(A.filter({$0 == tile}).count, B.filter({$0 == tile}).count, m) 14 } 15 m = A.count - m 16 return m 17 } 18 }
请发表评论