1007. Minimum Domino Rotations For Equal Row (M)

Minimum Domino Rotations For Equal Row (M)

题目

In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the ith 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.

Constraints:

2 <= A.length == B.length <= 2 * 10^4
1 <= A[i], B[i] <= 6

题意

给出若干个瓷砖的正反两面，判断能否通过翻转某些瓷砖来使所有瓷砖显示的数字相同，并求最小的翻转次数。

思路

可以从值域[1-6]入手，对于每一个数字，判断它是否出现在每一个瓷砖上，如果不是说明该情况不满足；如果是，计算最小翻转次数。

代码实现

Java

class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int ans = -1;
        for (int i = 1; i <= 6; i++) {
            boolean valid = true;
            int[] count = new int[2];
            for (int j = 0; j < A.length; j++) {
                if (A[j] != i && B[j] != i) {
                    valid = false;
                    break;
                }
                count[0] += A[j] == i ? 1 : 0;
                count[1] += B[j] == i ? 1 : 0;
            }
            if (valid) {
                int tmp = A.length - Math.max(count[0], count[1]);
                ans = ans == -1 ? tmp : Math.min(ans, tmp);
            }
        }
        return ans;
    }
}