関小君刷题记

题目大意：

行相等的最少多米诺旋转

在一排多米诺骨牌中，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. 1 <= A[i], B[i] <= 6
2. 2 <= A.length == B.length <= 20000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1007

解题思路分析：

本题虽然说得是多米诺骨牌，但实际上就是有两个长度相同的数组，要求我们通过多次交换两个数组相同位置的元素，达到一个数组内所有元素都相同的效果。首先，要想达到最终的效果，那么两个数组必须满足一个条件，即是那个相同元素的个数一定要大于等于数组的长度，再明确一点表达即是，对于任意的下标i，A[i]和B[i]至少有一个元素应该是那个共同元素，否则无论如何反转，该下标i处永远都不会出现那个相同元素。

解题时，我们可以定义三个长度为6的数组，第一个数组countUp来记录数组A中每种数字的个数，第二个数组countDown用于记录数组B中每种数字的个数。最后一个数组countAll的作用是判断哪一个数字是每个下标都出现过的数字，该数组同样记录每列出现的数字个数，如果当前下标A和B中的元素不一致，那么他们出现的次数分别加一，如果两个数字相同，我们只记录一次，因为相同index上的数字不论如何翻转都不会变到其他列上，最后实际有用的只有一个。

统计完之后，如果countAll中没有个数为n（A数组长度）的数字，那么说明我们无法将A和B任意一个数组变为全是相同数字的情况，此时返回-1。反之如果存在某个数字个数大于等于n，那么我们可以通过数组countUp以及countDown来查看该数字在数组A中的个数以及数组B中的个数。他们个数与n（A数组长度）差值的较小一方即是返回结果。（差值代表当前数组中不是相同数字的个数，也就是需要从另一个数组中翻转的次数）

实现代码：

public int minDominoRotations(int[] A, int[] B) {
    int[] countUp = new int[7];
    int[] countDown = new int[7];
    int[] countAll = new int[7];
    int commonNum=0;
    for(int i=0;i<A.length;i++){
        countAll[A[i]]++;
        if(A[i]!=B[i]) countAll[B[i]]++;
        countUp[A[i]]++;
        countDown[B[i]]++;
    }
    if(countAll[A[0]]==A.length) commonNum=A[0];
    if(countAll[B[0]]==A.length) commonNum=B[0];
    if(commonNum==0) return -1;
    return Math.min(A.length-countUp[commonNum],A.length-countDown[commonNum]);
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 31.05% of Java online submissions for Minimum Domino Rotations For Equal Row.

Memory Usage: 45.7 MB, less than 56.25% of Java online submissions for Minimum Domino Rotations For Equal Row.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1007-minimum-domino-rotations-for-equal-row-解题思路分析/