C++/Python 【哈希/贪心】K次翻转完成多米诺骨牌全相等

大大源码 • 2023年4月7日 pm11:08 • 未分类

行相等的最少多米诺旋转

题目[leetcode1007]

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

示例 1：

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

解题思路

运用哈希表方式的解法

这是我在看完题后的第一个想法，因为在题目中说明，多米诺骨牌的点数只有1-6，而要满足交换后数组A或者B中的所有元素均为同一点数，那说明该点数的个数要大于等于数组的长度，也就是该点数的卡牌能够填满A中的数组。

那必不可少的过程就是通过哈希表的形式统计 A、B数组中各个点数的个数，只有当点数的和大于等于数组长度时才有可能实现全相等的情况。

当然抓我说的重点——有可能，因为当数组A、B中的第i位置同为一个数时，则会为该点数多加了一次，所以出现问题，还是要多注意这个会出现的问题：以该点为相同牌转换时，在该点数A、B数组中的个数和足够填满，但存在那么一个j位置都不是该点，则不可能填满。

当然，用哈希表统计完A、B数组中的点个数后，还有一个好处——换在那边数组的问题就能清楚地了解了，当然是哪边的数组该点个数多，换到哪边啦！

（以下以要换到A数组说明）
之后分别以1-6的点数尝试填满，循环体进行，就是两种情况：
①、A、B数组均不等于该点数，不可能填满，不在往后统计！
②、数组A不是该点数，B是该点数，则交换一次。

实现代码如下：

int minDominoRotations1(vector<int>& A, vector<int>& B) {
        int lenA = A.size();
        int min_sum = 32762;
        int hashA[7] = { 0 };
        int hashB[7] = { 0 };
        for (int i = 0; i < lenA; ++i) { //分别统计A、B数组中1-6点数的个数
            ++hashA[A[i]];
            ++hashB[B[i]];
        }
        int i, j;
        for (i = 1; i <= 6; ++i) {
            if (hashA[i] + hashB[i] >= lenA) {
                int sum = 0;
                if (hashA[i] >= hashB[i]) { //该点数在数组A中较多
                    for (j = 0; j < lenA; ++j) {
                        if (A[j] != i && B[j] == i)
                            sum++;
                        else if (A[j] != i && B[j] != i)
                            break;
                    }
                    if (j >= lenA && min_sum > sum) { //
                        min_sum = sum;
                    }
                }
                else {
                    for (j = 0; j < lenA; ++j) {
                        if (A[j] == i && B[j] != i)
                            sum++;
                        else if (A[j] != i && B[j] != i)
                            break;
                    }
                    if (j >= lenA && min_sum > sum) { //遍历了所有数组得出的结果
                        min_sum = sum;
                    }
                }

            }
        }
        if (min_sum == 32762)
            return -1;
        return min_sum;
    }

AC：
在这里插入图片描述

运用贪心的思路进行解题

按贪心的思路，我并没有太多的思路，当然也忽略了最为重要的一点（前面哈希可有隐隐约约有提到，但这是我看完官方解题思路后才有的想法！），就是我只需以第0位置上A、B数组的点数为基准进行尝试填满就行。

因为这两个A[0]、B[0]都无法填满的话，将无法填满！

所以这缩减了很大的比较量。

实现代码如下：

int check(int x, vector<int>& A, vector<int>& B, int n) {
        int answer_a = 0, answer_b = 0;
        for (int i = 0; i < n; ++i) {
            if (A[i] != x && B[i] != x)return -1;
            else if (A[i] != x)++answer_a;
            else if (B[i] != x)++answer_b;
        }
        return answer_a > answer_b ? answer_b : answer_a;
    }

    int minDominoRotations(vector<int>& A, vector<int>& B) {
        int lens = A.size();
        int answer = check(A[0], A, B, lens);
        if (answer != -1 || A[0] == B[0])return answer;
        else return check(B[0], A, B, lens);
    }