LeetCode 题解工作台
行相等的最少多米诺旋转
在一排多米诺骨牌中， tops[i] 和 bottoms[i] 分别代表第 i 个多米诺骨牌的上半部分和下半部分。（一个多米诺是两个从 1 到 6 的数字同列平铺形成的 —— 该平铺的每一半上都有一个数字。） 我们可以旋转第 i 张多米诺，使得 tops[i] 和 bottoms[i] 的值交换。 …
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
根据题目描述，我们知道，要使得 中所有值或者 中所有值都相同，那么这个值必须是 或者 中的一个。 因此，我们设计一个函数 ，表示将所有的值都变成 的最小旋转次数，那么答案就是 $\min\{f(\textit{tops}[0]), f(\textit{bottoms}[0])\}$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
在一排多米诺骨牌中，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 解释： 在这种情况下，不可能旋转多米诺牌使一行的值相等。
提示：
2 <= tops.length <= 2 * 104bottoms.length == tops.length1 <= tops[i], bottoms[i] <= 6
解题思路
方法一：贪心
根据题目描述，我们知道，要使得 中所有值或者 中所有值都相同，那么这个值必须是 或者 中的一个。
因此，我们设计一个函数 ，表示将所有的值都变成 的最小旋转次数，那么答案就是 。
函数 的计算方法如下：
我们用两个变量 和 统计 和 中等于 的个数，用 减去它们的最大值，就是将所有值都变成 的最小旋转次数。注意，如果 和 中没有等于 的值，那么 的值就是一个很大的数，我们用 表示这个数。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int:
def f(x: int) -> int:
cnt1 = cnt2 = 0
for a, b in zip(tops, bottoms):
if x not in (a, b):
return inf
cnt1 += a == x
cnt2 += b == x
return len(tops) - max(cnt1, cnt2)
ans = min(f(tops[0]), f(bottoms[0]))
return -1 if ans == inf else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to identify potential targets and manage rotations efficiently.
- question_mark
Evaluate how well the candidate handles edge cases like impossible configurations.
- question_mark
Check for the candidate’s understanding of how greedy strategies and invariant validation apply to array problems.
常见陷阱
外企场景- error
Failing to handle edge cases where no solution exists and returning -1 when necessary.
- error
Overlooking the need for efficient iteration, which can lead to unnecessary time complexity increases.
- error
Assuming the problem can always be solved when the rows are of equal length, without considering that values may not align.
进阶变体
外企场景- arrow_right_alt
Instead of focusing on rotations, the problem could be modified to look for the minimum swaps needed.
- arrow_right_alt
Consider a variant where the allowed operation is limited to one row (either tops or bottoms), reducing the problem's complexity.
- arrow_right_alt
Introduce additional constraints, such as larger numbers in the arrays, requiring more careful space or time complexity optimizations.