在一排多米諾骨牌中,A[i] 和 B[i] 分別代表第 i 個多米諾骨牌的上半部分和下半部分。(一個多米諾是兩個從 1 到 6 的數字同列平鋪形成的 —— 該平鋪的每一半上都有一個數字。)
我們可以旋轉第 i 張多米諾,使得 A[i] 和 B[i] 的值交換。
返回能使 A 中所有值或者 B 中所有值都相同的最小旋轉次數。
如果無法做到,返回 -1.
輸入:A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
輸出:2
解釋:
圖一表示:在我們旋轉之前, A 和 B 給出的多米諾牌。
如果我們旋轉第二個和第四個多米諾骨牌,我們可以使上面一行中的每個值都等于 2,如圖二所示。
代碼
class Solution {public int minDominoRotations(int[] A, int[] B) {int cnt=Integer.MAX_VALUE;Set<Integer> set=new HashSet<>();for(int i=0;i<A.length;i++)//先查找A數組的最少翻轉次數{if(set.contains(A[i])) continue;//已經搜索過了boolean flag=false;int f=0;for(int j=0;j< A.length;j++)//檢查是否能完成翻轉得到結果{if(A[i]==A[j]) continue;if(A[i]!=B[j]){flag=true;break;}if(A[i]==B[j]) f++; }if(!flag) cnt= Math.min(f,cnt);set.add(A[i]);//記憶化} set.clear();int[] temp=A;A=B;B=temp; for(int i=0;i<A.length;i++)//再查找B數組的最少翻轉次數{if(set.contains(A[i])) continue;boolean flag=false;int f=0;for(int j=0;j< A.length;j++){if(A[i]==A[j]) continue;if(A[i]!=B[j]){flag=true;break;}if(A[i]==B[j]) f++;}if(!flag) cnt= Math.min(f,cnt);set.add(A[i]);}return cnt==Integer.MAX_VALUE?-1:cnt;}
}