Google

Loading...LeetCode

# O(n), O(1)
# 可以倒着想, 设想有两个已经完成rotate的多米诺list:
# A: [1,2,3,4,5]
# B: [9,9,9,9,9]
# 观察可知, 要想能达到题目要求, 相等的那个数要么是数组A的第一个数A[0], 要么是数组B[0]的第一个数B[0]
# 我们可以随便还原一下rotate之前的A和B:
# A: [1,9,3,9,5]
# B: [9,2,9,4,5]
# 其中rotate的次数, 就是A和B中与B[0]不相等的值得个数取最小.
# 也就是 x = min(diff(A,B[0]), diff(B,B[0]))
# 同理, 我们还需要查一下A[0]
# y = min(diff(A,A[0]), diff(B,A[0]))
# 而x和y如果只有一个是-1, 则说明rotate之后的list, 只有一个是全部相等的, 所以我们返回
# 不是-1的那一个.
# 如果x和y都不是-1, 说明rotate之后的两个list内部的值都相等, 我们返回min(x,y)
# 如果都是-1, 则返回-1

# 1
class Solution:        
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        def check(x):
            rotations_a = rotations_b = 0
            for i in range(n):
                if A[i] != x and B[i] != x:
                    return -1
                elif A[i] != x:
                    rotations_a += 1
                elif B[i] != x:
                    rotations_b += 1
            return min(rotations_a, rotations_b)
    
        n = len(A)
        rotations_a = check(A[0]) 
        rotations_b = check(B[0])
        if rotations_a == rotations_b == -1:
            return -1
        elif rotations_a != -1 and rotations_b != -1:
            return min(rotations_a, rotations_b)
        else:
            return rotations_a if rotations_a!=-1 else rotations_b
# 2
class Solution:        
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        def check(x):
            rotations_a = rotations_b = 0
            for i in range(n):
                if A[i] != x and B[i] != x:
                    return -1
                elif A[i] != x:
                    rotations_a += 1
                elif B[i] != x:
                    rotations_b += 1
            return min(rotations_a, rotations_b)
    
        n = len(A)
        rotations = check(A[0]) 
        if rotations != -1 or A[0] == B[0]:
            return rotations 
        else:
            return check(B[0])