Massive Algorithms: LeetCode 1007 - Minimum Domino Rotations For Equal Row

LeetCode 1007 - Minimum Domino Rotations For Equal Row

https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/

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] <= 6
2 <= A.length == B.length <= 20000

https://www.acwing.com/solution/LeetCode/content/1145/

http://www.noteanddata.com/leetcode-1007-Minimum-Domino-Rotations-For-Equal-Row-java-solution-note-2.html

有两行骰子，每行个数一样多
然后定义一个换位操作，就是在某一个index，把两行骰子在这个index上的位置互换
问，最少经过多少次操作以后，可以让两行骰子里面的某一行的值都是一样的

无论怎么换位置，如果最后可以让某一行的数字完全一样，每个位置上只有两个可能，这个数要么是A的，要么是B的。那么，对第0个数字来说，要么是A[0], 要么是B[0]。
那么，不管在那一行，后面的数字要么和A[0]相同，要么和B[0]相同，否则就不能达到效果。
所以，
–遍历数组一次，如果可以在A或者B里面在每个位置上都找到和A[0]相同的元素，那么就可以把某一行全部变成A[0]
–再遍历数组一次，如果可以在A或者B里面在每个位置上都找到和B[0]相同的元素，那么就可以把某一行全部变成B[0]

然后，在两次遍历的时候都分别计数，看看有几个一样的，那么n-count就是需要换的个数。

public int minDominoRotations(int[] A, int[] B) {
    int n = A.length;
    for(int i = 0, a = 0, b = 0; i < n && (A[i] == A[0] || B[i] == A[0]); ++i) {
        if(A[i] == A[0]) a++;
        if(B[i] == A[0]) b++;
        if(i == n-1) return Math.min(n-a, n-b);
    }
    for(int i = 0, a = 0, b = 0; i < n && (A[i] == B[0] || B[i] == B[0]); ++i) {
        if(A[i] == B[0]) a++;
        if(B[i] == B[0]) b++;
        if(i == n-1) return Math.min(n-a, n-b);
    }
    return -1;
}

X. https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/discuss/252266/C%2B%2B-check-A0-and-B0

We are as good as our very first domino :) So, we just need to check for A[0] (top) and B[0] (bot).

If we find a domino that does not have top or bot, then we exclude that number from consideration. We count how many times a number appear in the top or bottom of each domino and use these numbers to detect the minimum number of flips

int minDominoRotations(vector<int>& A, vector<int>& B) {
  auto top = A[0], bot = B[0], top1 = 0, bot1 = 0, top2 = 0, bot2 = 0;
  for (auto i = 0; i < A.size(); ++i) {
    if (A[i] != top && B[i] != top) top = 0;
    if (A[i] != bot && B[i] != bot) bot = 0;
    top1 += A[i] == top;
    bot1 += B[i] == top;
    top2 += A[i] == bot;
    bot2 += B[i] == bot;
  }
  return top || bot ? min(A.size() - max(top1, bot1), A.size() - max(top2, bot2)) : -1;
}

X. https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/discuss/252633/Java-one-pass-counting-O(A-%2B-B)

Count the frequency of each number in A and B, respectively;
Count the frequency of A[i] if A[i] == B[i];
If countA[i] + countB[i] - same[i] == A.length, we find a solution; otherwise, return -1;
min(countA[i], countB[i]) - same[i] is the answer.

    public int minDominoRotations(int[] A, int[] B) {
        int[] countA = new int[7]; // countA[i] records the occurrence of i in A.
        int[] countB = new int[7]; // countB[i] records the occurrence of i in B.
        int[] same = new int[7]; // same[k] records the occurrence of k, where k == A[i] == B[i].
        for (int i = 0; i < A.length; ++i) {
            ++countA[A[i]];
            ++countB[B[i]];
            if (A[i] == B[i]) { ++same[A[i]]; }
        }
        for (int i = 1; i < 7; ++i) {
            if (countA[i] + countB[i] - same[i] >= A.length) {
                return Math.min(countA[i], countB[i]) - same[i];
            }
        }
        return -1;
    }

https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/discuss/252242/JavaPython-Find-Intersection-of-Dominos

Solution 1:

Check all possibilities.

    def minDominoRotations(self, A, B):
        for x in range(1, 7):
            if all(x == a or x == b for a, b in zip(A, B)):
                return min(len(A) - A.count(x), len(B) - B.count(x))
        return -1

Solution 2

Try A[0] or B[0]

    public int minDominoRotations(int[] A, int[] B) {
        int n = A.length;
        for (int i = 0, a = 0, b = 0; i < n && (A[i] == A[0] || B[i] == A[0]); ++i) {
            if (A[i] != A[0]) a++;
            if (B[i] != A[0]) b++;
            if (i == n - 1) return Math.min(a, b);
        }
        for (int i = 0, a = 0, b = 0; i < n && (A[i] == B[0] || B[i] == B[0]); ++i) {
            if (A[i] != B[0]) a++;
            if (B[i] != B[0]) b++;
            if (i == n - 1) return Math.min(a, b);
        }
        return -1;
    }

Solution 3

Find intersection set s of {A[i], B[i]}
s.size = 0, no possible result.
s.size = 1, one and only one result.
s.size = 2, it means all dominos are [a,b] or [b,a], try either one.
s.size > 2, impossible.

    public int minDominoRotations(int[] A, int[] B) {
        HashSet<Integer> s = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5, 6));
        int[] countA = new int[7], countB = new int[7];
        for (int i = 0; i < A.length; ++i) {
            s.retainAll(new HashSet<>(Arrays.asList(A[i], B[i])));
            countA[A[i]]++;
            countB[B[i]]++;
        }
        for (int i : s) return Math.min(A.length - countA[i], B.length - countB[i]);
        return -1;
    }

X.
因为

1 <= A[i], B[i] <= 6，所以如果能使得A或者B中所有元素的值一样，那么就只有12种情况，即A中元素或者B中元素全为1/2/3/4/5/6，依次判断这6种情况即可，如假设变换后A中元素全为1，从头遍历A与B，如果A[i] != 1 并且B[i] != 1表示无法使得A中元素全为1，继续判断2

的情况；否则如果A[i] != 1 并且B[i] = 1,那么交换的次数加1；同理可求得B中元素也全为1的交换次数。遍历完这6种情况后，如果无法满足则返回-1，可以的话返回交换的最小值
https://zxi.mytechroad.com/blog/algorithms/array/1007-minimum-domino-rotations-for-equal-row/

  int minDominoRotations(vector<int>& A, vector<int>& B) {

    int ans = INT_MAX;

    for (int r = 1; r <= 6; ++r) {

      bool flag = true;

      int count_a = 0;

      int count_b = 0;

      for (int i = 0; i < A.size(); ++i) {

        if (A[i] != r && B[i] != r) {

          flag = false; 

          break;

}

        else if (A[i] == r && B[i] == r) continue;

        else if (A[i] == r) {

          ++count_a;

        } else if (B[i] == r) {

          ++count_b;

}

}

      if (flag) ans = min(ans, min(count_a, count_b));

}

    return ans == INT_MAX ? -1 : ans;

}

int minDominoRotations(vector<int>& A, vector<int>& B) {
vector<int> nums;
int min=0;
for(int i = 1; i <= 6; i++)
{
int changeA=0,changeB=0;
for(int j = 0; j < A.size(); j++)
{
if(A[j] != i && B[j] !=i)
{break;}
if(A[j] == i && B[j] !=i)
changeB++;
if(A[j] != i && B[j] ==i)
changeA++;
if(j == A.size()-1)
{
nums.push_back(i);
min = changeA<changeB?changeA:changeB;
}
}
}
if(nums.empty()) return -1;
return min;
}

X. https://blog.csdn.net/fuxuemingzhu/article/details/88379160
我们需要对这个题做分析：先把A,B两面的数字做一个统计，如果出现最多的点数<牌的个数，那么无论如何都无法翻转成功。如果出现最多的点数=牌的个数，那么这个时候需要保证每一个牌的都有且只有一面的点数是这个最多的点数。如果出现最多的点数>牌的个数，那么需要保证每个牌都至少有一面是这个数字，此时两面都是这个数字的话，就不用翻转。

所以：

如果两面相等都等于出现最多的数字target，不用翻转。

我们需要使用两个数字分别表示向该面翻转的次数。如果只有一面等于target，就把向另一面翻转的次数+1.

在任何时候，只要这个牌的正反面有一面不是出现最多的数字，那么一定返回-1.

我们最终只需要返回两个方向翻转的次数的最小值即可。

下面做一下讨论：为什么只用统计出现最多的数字就行，为什么出现次数第二多的次数一定没有机会？

1.如果出现最多的数字的次数<长度，无论第一第二都不行。
2.如果出现最多的次数=长度，这个时候第二多次数如果等于N，那么两者效果一样，如果第二多次数如果小于N，那么不可能。
3.如果出现最多的次数>N，这个时候一定会出现某些牌的正反面都是该最多的数字。此时第二多的数字没有机会。

总之，只需要判断出现最多的数字即可。

def minDominoRotations(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
N = len(A)
count = collections.Counter(A + B)
if count.most_common(1)[0][1] < N:
return -1
target = count.most_common(1)[0][0]
a_swap = 0
b_swap = 0
for i in range(N):
if A[i] == B[i]:
if A[i] == target:
continue
else:
return -1
elif A[i] == target:
b_swap += 1
elif B[i] == target:
a_swap += 1
else:
return -1
return min(a_swap, b_swap)

LeetCode 1007 - Minimum Domino Rotations For Equal Row

Solution 1:

Solution 2

Solution 3

Labels

Popular Posts