leetcode->1008. 先序遍历构造二叉树

朴灿烈づ我的快乐病毒、 2022-03-10 07:57 120阅读 0赞

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

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

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

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

**示例 1：**

![domino.png][]

>     输入：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`

class Solution {
    public int minDominoRotations(int[] A, int[] B) {
            return Math.min(minDominoRotations2(B, A),minDominoRotations2(A, B));
        }
        public int minDominoRotations2(int[] A, int[] B) {
            // 造一个 2 维数组，
            int[][] count = new int[7][A.length];
            for (int i = 0; i < A.length; i++) {
                if (A[i] != B[i]) {
                    count[B[i]][i] = 2;
                }
                count[A[i]][i] = 1;
            }
            for (int i = 1; i < 7; i++) {
                int res = 0;
                int counB = 0;
                int min = -1;
                for (int j = 0; j < A.length; j++) {
                    if (count[i][j] == 1) {
                        res += count[i][j];
                    } else if (count[i][j] == 2) {
                        res++;
                        counB++;
                    }
                }
                if (res == A.length) {
                    return  Math.min(A.length - counB, counB);
                }
            }
            return -1;
        }
    }

[domino.png]: /images/20220310/ff5df83930f34b8eac87dcce522f2fa9.png