public class Solution
{
public int MinDominoRotations(int[] A, int[] B)
{
var na = A.Length;
var nb = B.Length;
if (na != nb)
{
return -;
}
var dic1 = new Dictionary<int, List<int>>();
var dic2 = new Dictionary<int, List<int>>();
for (var i = ; i <= ; i++)
{
dic1.Add(i, new List<int>());
dic2.Add(i, new List<int>());
} for (var i = ; i < na; i++)
{
var a = A[i];
dic1[a].Add(i); var b = B[i];
dic2[b].Add(i);
} var minchanges = na;
var find = false;
for (var i = ; i <= ; i++)
{
var top = dic1[i];
var bottom = dic2[i];
var temp = top.Union(bottom).Distinct();
if (temp.Count() == na)
{
minchanges = Math.Min(minchanges, na - Math.Max(top.Count(), bottom.Count()));
find = true;
}
}
return find ? minchanges : -;
}
}
思路,分别记录上部和下部的每一个点数出现的索引,然后对以此判断每一个点数的并集,是否包含了全部的索引。
这样的点数,就是可以满足在同一侧全是一样的点数。
下面就要找最小的移动次数,发现最小的移动次数是保持这个点数出现的次数多的一面不动,而把这个点数出现在另一面的牌进行翻转。
如代码所示:34行,求并集。37行,进行最小次数判断。