1007.行相等的最少多米诺旋转
解题思路：
-
判断能否将 A 或 B 中全部元素变成 A[0]；
-
若能，返回旋转次数少的那个，不用再检查 B[0]；
- • 如果 A[0] == B[0]，再检查 B[0] 没有意义；
- • 如果 A[0] != B[0]，仅当骨牌中只有 A[0]、B[0] 两个数字才能将 A 中或 B 中全部元素变成 B[0]，此时最小旋转次数将和 A[0] 一样；
-
若不能，并且A[0] != B[0]，再判断能否将 A 中或 B 中全部元素变成 B[0]；
复杂度：
-
时间复杂度：O(n)，检查是否可以将 tops 或 bottoms 中所有元素变成 tops[0] 或 Bbottoms[0]，最坏情况可能需要浏览完所有多米诺骨牌；
-
空间复杂度：O(1)，使用常数级的变量空间；
代码实现：
function minDominoRotations(tops: number[], bottoms: number[]): number {
let len: number = tops.length;
// 求 tops 或 bottoms 全部变成 tops[0]，最少需要多少次旋转 Ï
let rotations: number = check(tops[0], tops, bottoms, len);
// 如果 tops[0]==bottoms[0], 那么不⽤继续检查 bottoms[0]
// 如果 tops[0]!=bottoms[0], 且可以将 tops 或 bottoms 中的元素全部变成 tops[0]，那么也不用再检查 bottoms[0]
if (rotations != -1 || tops[0] == bottoms[0]) {
return rotations;
} else {
// 如果 tops[0] 不满⾜并且 tops[0]!=bottoms[0]
// 求解 tops 或 bottoms 全部变成 bottoms[0]，最少需要多少次旋转
return check(bottoms[0], tops, bottoms, len);
}
};
// 检查将 tops 或者 bottoms 中元素全部变成 x 需要多少次旋转
var check = function (x: number, tops: Array<number>, bottoms: Array<number>, len: number): number {
// rotationsTops 存储将 tops 中元素变成 x 需要多少次旋转
// rotationsBottoms 存储将 bottoms 中元素变成 x 需要多少次旋转
let rotationsTops = 0,
rotationsBottoms = 0;
// 遍历骨牌判断是否能完成任务（在 tops 中完成或者在 bottoms 中完成）
for (let i = 0; i < len; i++) {
if (tops[i] != x && bottoms[i] != x) {
// 如果当前多米诺骨牌上没有数字 x，那么不可能完成任务
return -1;
} else if (tops[i] != x) {
// 如果当前多米诺骨牌上 tops[i] 不是 x，那么 rotationsTops 需要 +1 (旋转一次)
rotationsTops++;
} else if (bottoms[i] != x) {
// 如果当前多米诺骨牌上 bottoms[i] 不是 x，那么 rotationsBottoms 需要+1 (旋转一次)
rotationsBottoms++;
}
}
// 返回最小旋转次数
return Math.min(rotationsTops, rotationsBottoms);
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
正则表达式👉 初识正则表达式
上一篇
评论
