当前位置：首页 > news >正文

LeetCode 1007. 行相等的最少多米诺旋转题解

news 来源：原创 2025/7/14 6:58:53

示例

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

对于本题，我的做题思路是先观察后面分支思考，先说说我的观察，通过题目的示例观察，只有当一个数字的总数等于或超过tops.length后才有可能做到交换出一个所有值都同为一个数的数组，通过该规律，我们可以找到我们需要统计的数值mid，然后通过条件判断，如果两个数组中遍历到相同下标时都没出现mid那就直接return false，但我们最后需要的结果是最少交换几次即可，那我们在遍历的时候便可以统计出来，但是当tops和bottoms数组中同时出现mid时就不必要交换了，直接在后面减掉即可。

class Solution {public int minDominoRotations(int[] tops, int[] bottoms) {HashMap<Integer,Integer> maptop = new HashMap<>();HashMap<Integer,Integer> mapbo = new HashMap<>();int n = tops.length;int num = 0;int mid = 0;for(int i=0;i<n;i++){maptop.put(tops[i],maptop.getOrDefault(tops[i],0)+1);mapbo.put(bottoms[i],mapbo.getOrDefault(bottoms[i],0)+1);if(maptop.getOrDefault(tops[i],0)>=(n+1)/2) mid = tops[i];if(mapbo.getOrDefault(bottoms[i],0)>=(n+1)/2) mid = bottoms[i];}if(maptop.getOrDefault(mid,0)+mapbo.getOrDefault(mid,0) < n) return -1;for(int i=0;i<n;i++){if(tops[i]!=mid&&bottoms[i]!=mid) return -1; if(tops[i]==mid&&bottoms[i]==mid) num++;}return Math.min(maptop.get(mid)-num,mapbo.get(mid)-num);}
}

画个图来更好的说明我的思路

说的可能还是不太详细，因为有一些得规避一下，所以代码最后成型如此，比如有长度为7的数组，
那么（int）7/2 = 3，3+3=6<7不可以成立一个值相同的数组，所以要（int）(7+1)/2=4才行，这就是我们需要的mid值，然后后面一遍遍历找出同一个下标下的所有情况。

我们来看下题解又是怎么解决的

class Solution {public int minDominoRotations(int[] tops, int[] bottoms) {int ans = Math.min(minRot(tops, bottoms, tops[0]), minRot(tops, bottoms, bottoms[0]));return ans == Integer.MAX_VALUE ? -1 : ans;}private int minRot(int[] tops, int[] bottoms, int target) {int toTop = 0;int toBottom = 0;for (int i = 0; i < tops.length; i++) {int x = tops[i];int y = bottoms[i];if (x != target && y != target) {return Integer.MAX_VALUE;}if (x != target) {toTop++; // 把 y 旋转到上半} else if (y != target) {toBottom++; // 把 x 旋转到下半}}return Math.min(toTop, toBottom);}
}

以上是灵神的代码，看了下来忽然让我意识到了一点，就是，如果需要一个数组的值全变为同一个数的话，那就一定会是tops[0]或者bottoms[0]

然后后面的步骤都会和我差不多，确定了target后就开始遍历找到最小的反转次数。说是脑筋急转弯也不为过。

相关文章：