[LeetCode] 1007. 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.

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.

行相等的最少多米诺旋转。

题意是在一排多米诺骨牌中，A[i] 和 B[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字）。我们可以旋转第 i 张多米诺，使得 A[i] 和 B[i] 的值交换。返回能使 A 中所有值或者 B 中所有值都相同的最小旋转次数。如果无法做到，返回 -1。

思路是贪心。因为要找的是反转几次能让A或B里面的六张牌一样，所以target目标牌一定在A[0]或B[0]中间。写一个helper函数，假定A[0]或B[0]是那个target，然后遍历A和B，如果在遍历的时候，target在B找到了则count++（因为需要转动）。在这个过程中但凡有target在两排都没找到，则返回Integer.MAX_VALUE，表示input无效。这个helper函数需要在这四种情况下跑，以得到需要转动的最小次数count。

假定target是A[0]，target是从B翻到A

假定target是A[0]，target是从A翻到B

假定target是B[0]，target是从A翻到B

假定target是B[0]，target是从B翻到A

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int minDominoRotations(int[] A, int[] B) {
 3         int resA = Math.min(helper(A[0], A, B), helper(A[0], B, A));
 4         int resB = Math.min(helper(B[0], A, B), helper(B[0], B, A));
 5         int res = Math.min(resA, resB);
 6         return res == Integer.MAX_VALUE ? -1 : res;
 7     }
 8 
 9     private int helper(int target, int[] A, int[] B) {
10         int count = 0;
11         for (int i = 0; i < A.length; i++) {
12             if (A[i] != target) {
13                 if (B[i] == target) {
14                     count++;
15                 } else {
16                     return Integer.MAX_VALUE;
17                 }
18             }
19         }
20         return count;
21     }
22 }

JavaScript实现

 1 /**
 2  * @param {number[]} A
 3  * @param {number[]} B
 4  * @return {number}
 5  */
 6 var minDominoRotations = function (A, B) {
 7     let resA = Math.min(helper(A[0], A, B), helper(A[0], B, A));
 8     let resB = Math.min(helper(B[0], A, B), helper(B[0], B, A));
 9     let res = Math.min(resA, resB);
10     return res == Number.MAX_VALUE ? -1 : res;
11 };
12 
13 var helper = function (target, A, B) {
14     let count = 0;
15     for (let i = 0; i < A.length; i++) {
16         if (A[i] != target) {
17             if (B[i] == target) {
18                 count++;
19             } else {
20                 return Number.MAX_VALUE;
21             }
22         }
23     }
24     return count;
25 }

LeetCode 题目总结