友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1007. 行相等的最少多米诺旋转
在一排多米诺骨牌中，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
思路分析
统计每个数字的下标，然后逐个检查每个数字的下标集合是否能完整覆盖原始数字的全部下标。
看题解，只需要判断是否可以都变成 tops[0] 或者 bottoms[0]（要旋转成一样的数字，那么，要么是 tops[0]，要么是 bottoms[0]（要么上面调转到下面，要么下面调转到上面，两个里面，必有其一。）），这个思路更简单高效！
-
一刷
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-01 07:20:11
*/
public int minDominoRotations(int[] tops, int[] bottoms) {
int length = tops.length;
List<Integer>[] topMap = new ArrayList[7];
for (int i = 1; i < topMap.length; i++) {
topMap[i] = new ArrayList<>();
}
List<Integer>[] bottomMap = new ArrayList[7];
for (int i = 1; i < bottomMap.length; i++) {
bottomMap[i] = new ArrayList<>();
}
for (int i = 0; i < length; i++) {
int top = tops[i];
topMap[top].add(i);
int bottom = bottoms[i];
bottomMap[bottom].add(i);
}
int result = Integer.MAX_VALUE;
for (int i = 1; i < topMap.length; i++) {
List<Integer> topIdx = topMap[i];
List<Integer> bottomIdx = bottomMap[i];
// 总数量
if (topIdx.size() + bottomIdx.size() < length) {
continue;
}
Set<Integer> set = new HashSet<>(topIdx);
set.addAll(bottomIdx);
// 去除重复后的数量
if (set.size()<length) {
continue;
}
boolean ok = true;
for (int j = 0; j < length; j++) {
if (!set.contains(j)) {
ok = false;
break;
}
}
if (ok) {
result = Math.min(result,
Math.min(length - topIdx.size(), length - bottomIdx.size()));
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}
参考资料
-
1007. 行相等的最少多米诺旋转 - 都变成 tops[0] 或者 bottoms[0] — 要旋转成一样的数字，那么，要么是
tops[0]，要么是bottoms[0]（要么上面调转到下面，要么下面调转到上面，两个里面，必有其一。）