行相等的最少多米诺旋转
难度:
标签:
题目描述
在一排多米诺骨牌中，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 * 104bottoms.length == tops.length1 <= tops[i], bottoms[i] <= 6
代码结果
运行时间: 57 ms, 内存: 16.8 MB
/*
题目思路：
1. 找出可能的目标值，即所有牌的上半部分或下半部分的值。
2. 使用Java Stream计算需要的旋转次数。
3. 返回最小的旋转次数，如果无法实现返回-1。
*/
import java.util.stream.IntStream;
public class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
int rotations = check(tops[0], tops, bottoms);
if (rotations != -1 || tops[0] == bottoms[0]) return rotations;
else return check(bottoms[0], tops, bottoms);
}
private int check(int target, int[] tops, int[] bottoms) {
long countA = IntStream.range(0, tops.length).filter(i -> tops[i] != target && bottoms[i] == target).count();
long countB = IntStream.range(0, tops.length).filter(i -> tops[i] == target && bottoms[i] != target).count();
if (IntStream.range(0, tops.length).anyMatch(i -> tops[i] != target && bottoms[i] != target)) return -1;
return (int) Math.min(countA, countB);
}
}
解释
方法:
这道题的思路是尝试使得所有多米诺骨牌的上半部分或下半部分的数字都变成相同的。因为每个多米诺骨牌的数字范围是1到6，所以我们只需要尝试这6种可能的数字。对于每一种数字，我们遍历整个多米诺骨牌数组，如果当前多米诺的上半部分不等于这个数字，就检查其下半部分是否等于这个数字，如果是，就将旋转次数加1；同理，如果下半部分不等于这个数字，就检查上半部分并相应增加旋转次数。如果遍历完整个数组后没有中断（即没有遇到无法通过旋转使某个多米诺的两部分之一等于目标数字的情况），就更新最小旋转次数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在检查每个多米诺骨牌的上下部分时，碰到一个无法旋转的情况就立即中断循环？
▷🦆
在尝试1到6这6个数字时，是否可能存在对于某个数字无法通过旋转达到目标但对其他数字可以达到目标的情况？
▷🦆
题解中旋转次数的更新逻辑是什么意思？为什么是在内层循环结束后，使用`min(a, b)`来更新最小旋转次数？
▷🦆
在实际应用中，如何处理当`tops`和`bottoms`数组长度不相等的情况？
▷