[leetcode] 1007. Minimum Domino Rotations For Equal Row

[leetcode] 1007. Minimum Domino Rotations For Equal Row

Description

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: 2Explanation: 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: -1Explanation: 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和B两个数组的众数，然后遍历A和B找到A变成相同数组的需要的次数cnt1，B变成相同数组所需要的次数cnt2，最后返回最小的次数就行了，如果都没有就只能返回-1了哈，比较笨，思路可以借鉴一下哈，如果有想法，可以跟我讨论一下优化的空间。

代码

class Solution: def minDominoRotations(self, A: List[int], B: List[int]) -> int: counter_A=collections.Counter(A) counter_B=collections.Counter(B) k1,v1=counter_A.most_common(1)[0] k2,v2=counter_B.most_common(1)[0] n=len(A) flag_A=True flag_B=True cnt1=0 cnt2=0 for i in range(n): if(A[i]!=k1 and B[i]!=k1): flag_A=False elif(A[i]!=k1 and B[i]==k1): cnt1+=1 if(B[i]!=k2 and A[i]!=k2): flag_B=False elif(B[i]!=k2 and A[i]==k2): cnt2+=1 if(flag_A and flag_B): return min(cnt1,cnt2) elif(flag_A): return cnt1 elif(flag_B): return cnt2 else: return -1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。