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

题目链接

1007. 行相等的最少多米诺旋转 - 力扣（LeetCode）

题目描述

在一排多米诺骨牌中，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 解释： 在这种情况下，不可能旋转多米诺牌使一行的值相等。

解题思路

1. 问题描述：
   • 给定两排长度相同的多米诺骨牌（tops和bottoms数组）。
   • 每次旋转可以将一个骨牌的上下数字交换。
   • 目标是通过最少次数的旋转，使得某一排的所有数字相同。
   • 如果无法实现，返回-1。
2. 关键观察：
   • 最终统一的数字只能是tops[0]或bottoms[0]中的一个（因为第一个骨牌必须参与统一）。
   • 对于候选数字target（tops[0]或bottoms[0]），需要检查所有骨牌是否至少有一个数字等于target。
   • 对于每个骨牌：
     • 如果上半不等于target，则需要将下半旋转到上半（toTop++）。
     • 如果下半不等于target，则需要将上半旋转到下半（toBottom++）。
     • 如果都不等于target，则直接失败。
3. 算法选择：
   • 尝试两种候选数字：tops[0]和bottoms[0]。
   • 对于每种候选数字，统计需要旋转到上半或下半的次数，取较小值。
   • 如果两种候选都失败，返回-1。

题解代码

classSolution{publicintminDominoRotations(int[]tops,int[]bottoms){// 尝试让所有骨牌上半或下半都变成tops[0]或bottoms[0]所需的最小旋转次数intans=Math.min(minRot(tops,bottoms,tops[0]),// 尝试让所有上半变成tops[0]minRot(tops,bottoms,bottoms[0])// 尝试让所有上半变成bottoms[0]);// 如果两种尝试都失败，返回-1returnans==Integer.MAX_VALUE?-1:ans;}privateintminRot(int[]tops,int[]bottoms,inttarget){inttoTop=0;// 需要旋转到上半的次数inttoBottom=0;// 需要旋转到下半的次数for(inti=0;i<tops.length;i++){intx=tops[i];inty=bottoms[i];// 如果当前骨牌的两个数字都不等于target，无法完成if(x!=target&&y!=target){returnInteger.MAX_VALUE;}// 如果上半不等于target，需要旋转下半到上半if(x!=target){toTop++;}// 如果下半不等于target，需要旋转上半到下半elseif(y!=target){toBottom++;}// 如果x和y都等于target，不需要旋转}// 返回两种旋转方式中的较小值returnMath.min(toTop,toBottom);}}

复杂度分析

1. 时间复杂度：
   • 遍历数组两次（分别尝试tops[0]和bottoms[0]），每次遍历长度为n。
   • 总时间复杂度：O(n)。
2. 空间复杂度：
   • 仅使用常数空间（几个变量）。
   • 总空间复杂度：O(1)。