1007-行相等的最少多米诺旋转

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

在一排多米诺骨牌中，tops[i] 和 bottoms[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6
的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。）

我们可以旋转第 i 张多米诺，使得 tops[i] 和 bottoms[i] 的值交换。

返回能使 tops 中所有值或者 bottoms 中所有值都相同的最小旋转次数。

如果无法做到，返回 -1.

示例 1：

**输入：** tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
**输出：** 2
**解释：** 
图一表示：在我们旋转之前， tops 和 bottoms 给出的多米诺牌。 
如果我们旋转第二个和第四个多米诺骨牌，我们可以使上面一行中的每个值都等于 2，如图二所示。

示例 2：

**输入：** tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]
**输出：** -1
**解释：** 在这种情况下，不可能旋转多米诺牌使一行的值相等。

提示：

  • 2 <= tops.length <= 2 * 104
  • bottoms.length == tops.length
  • 1 <= tops[i], bottoms[i] <= 6

方法一：贪心

分析

我们随便选其中的一个多米诺骨牌，它的标号为 i，上半部分的数字为 A[i]，下半部分的数字为 B[i]。

bla{:width=500}
{:align=center}

此时可能会有三种情况：

  1. 以数字 A[i] 作为基准，将 A 或 B 中的所有值都变为 A[i]。例如，下图中，我们选择了第 0 个多米诺骨牌，这样可以将 A 中的所有值都变为 2。

bla{:width=500}
{:align=center}

  1. 以数字 B[i] 作为基准，将 A 或 B 中的所有值都变为 B[i]。例如，下图中，我们选择了第 1 个多米诺骨牌，这样可以将 B 中的所有值都变为 2。

bla{:width=500}
{:align=center}

  1. 无论选择 A[i] 还是 B[i] 都没有办法将 A 或 B 中的所有值变为都相同。例如，下图中，我们选择了最后一个多米诺骨牌，无论是它的上半部分 5 还是下半部分 4，都无法满足条件。

bla{:width=500}
{:align=center}

如果要满足第 1 种或是第 2 种情况，就必须存在一块多米诺骨牌，它的上半部分或者下半部分的数字 x 在所有其它的多米诺骨牌中都出现过。若该条件满足，则说明所有多米诺骨牌中都出现了数字 x。因此，我们只要选择任意一块多米诺骨牌，判断它的上半部分或下半部分的数字是否可以作为 x 即可。

算法

  • 选择第一块多米诺骨牌，它包含两个数字 A[0] 和 B[0]；

  • 检查其余的多米诺骨牌中是否出现过 A[0]。如果都出现过，则求出最少的翻转次数，其为将 A[0] 全部翻到 A 和全部翻到 B 中的较少的次数。

  • 检查其余的多米诺骨牌中是否出现过 B[0]。如果都出现过，则求出最少的翻转次数，其为将 B[0] 全部翻到 A 和全部翻到 B 中的较少的次数。

  • 如果上述两次检查都失败，则返回 -1。

[sol1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:        
    def minDominoRotations(self, A: List[int], B: List[int]) -> int:
        def check(x):
            """
            Return min number of swaps 
            if one could make all elements in A or B equal to x.
            Else return -1.
            """
            # how many rotations should be done
            # to have all elements in A equal to x
            # and to have all elements in B equal to x
            rotations_a = rotations_b = 0
            for i in range(n):
                # rotations coudn't be done
                if A[i] != x and B[i] != x:
                    return -1
                # A[i] != x and B[i] == x
                elif A[i] != x:
                    rotations_a += 1
                # A[i] == x and B[i] != x    
                elif B[i] != x:
                    rotations_b += 1
            # min number of rotations to have all
            # elements equal to x in A or B
            return min(rotations_a, rotations_b)
    
        n = len(A)
        rotations = check(A[0]) 
        # If one could make all elements in A or B equal to A[0]
        if rotations != -1 or A[0] == B[0]:
            return rotations 
        # If one could make all elements in A or B equal to B[0]
        else:
            return check(B[0])
[sol1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    /*
    Return min number of rotations 
    if one could make all elements in A or B equal to x.
    Else return -1.
    */
    public int check(int x, int[] A, int[] B, int n) {
        // how many rotations should be done
        // to have all elements in A equal to x
        // and to have all elements in B equal to x
        int rotations_a = 0, rotations_b = 0;
        for (int i = 0; i < n; i++) {
            // rotations coudn't be done
            if (A[i] != x && B[i] != x) return -1;
            // A[i] != x and B[i] == x
            else if (A[i] != x) rotations_a++;
            // A[i] == x and B[i] != x    
            else if (B[i] != x) rotations_b++;
        }
        // min number of rotations to have all
        // elements equal to x in A or B
        return Math.min(rotations_a, rotations_b);
    }

    public int minDominoRotations(int[] A, int[] B) {
        int n = A.length;
        int rotations = check(A[0], B, A, n);
        // If one could make all elements in A or B equal to A[0]
        if (rotations != -1 || A[0] == B[0]) return rotations;
        // If one could make all elements in A or B equal to B[0]
        else return check(B[0], B, A, n);
    }
}
[sol1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public:
    /*
    Return min number of rotations 
    if one could make all elements in A or B equal to x.
    Else return -1.
    */
    int check(int x, vector<int>& A, vector<int>& B, int n) {
        // how many rotations should be done
        // to have all elements in A equal to x
        // and to have all elements in B equal to x
        int rotations_a = 0, rotations_b = 0;
        for (int i = 0; i < n; i++) {
            // rotations coudn't be done
            if (A[i] != x && B[i] != x) return -1;
            // A[i] != x and B[i] == x
            else if (A[i] != x) rotations_a++;
            // A[i] == x and B[i] != x    
            else if (B[i] != x) rotations_b++;
        }
        // min number of rotations to have all
        // elements equal to x in A or B
        return min(rotations_a, rotations_b);
    }

    int minDominoRotations(vector<int>& A, vector<int>& B) {
        int n = A.size();
        int rotations = check(A[0], B, A, n);
        // If one could make all elements in A or B equal to A[0]
        if (rotations != -1 || A[0] == B[0]) return rotations;
        // If one could make all elements in A or B equal to B[0]
        else return check(B[0], B, A, n);
    }
};

复杂度分析

  • 时间复杂度：O(N)。我们只会遍历所有的数组最多两次。

  • 空间复杂度：O(1)。

 Comments
On this page
1007-行相等的最少多米诺旋转