漳浦网站开发,做招聘的网站,信阳网站设计,移动网站建站系统下载LeetCode 1007 行相等的最少多米诺旋转 原题英文#xff1a;Minimum Domino Rotations For Equal Row 难度#xff1a;中等 | 标签#xff1a;数组、贪心 1 题目重述
给定两行长度相同的多米诺骨牌#xff1a;
tops[i] 表示第 i 张骨牌上面的数字#xff1b;bottoms[…LeetCode 1007 行相等的最少多米诺旋转 原题英文Minimum Domino Rotations For Equal Row 难度中等 | 标签数组、贪心 1 题目重述
给定两行长度相同的多米诺骨牌
tops[i] 表示第 i 张骨牌上面的数字bottoms[i] 表示第 i 张骨牌下面的数字。
你可以任选一些骨牌把它们翻转即交换这一张牌的上下数字。 请返回 最少需要翻转多少次才能让 上面一行全部相等 或 下面一行全部相等。 如果无论怎么翻也做不到返回 -1。 2 解题思路 2.1 关键观察 候选数字只有 2 个 假设最终能让某一行全部等于 x那么 x 必定出现在第一张牌的上面或下面。 因此我们只需要检验 tops[0] 和 bottoms[0] 这两个数字即可。 一次扫描即可统计旋转次数 对于候选数 x我们同时统计 rotateTop ——让 上排 都变成 x 需要翻多少次rotateBottom ——让 下排 都变成 x 需要翻多少次。 遍历时若发现某张牌两面都不是 x说明 x 不可能完成统一直接失败即可。 答案 这两个候选数字的最小可行翻转数 若两个候选都失败则返回 -1。
2.2 时间复杂度
我们只扫描两遍数组时间 O(n)空间 O(1)。 3 常见坑点
坑说明把整条数组与数字比较bottoms b 永远为 False正确写法应为 bottoms[i] b忘记处理 0 次翻转if tmp: 会把 tmp 0 的有效解过滤掉应直接比较最小值发现失败仍更新答案一旦遇到两面都不是候选数应立即 return 而不是继续用临时统计结果更新全局答案 4 AC 代码Python 3
from typing import Listclass Solution:def minDominoRotations(self, tops: List[int], bottoms: List[int]) - int:def check(x: int) - int: 返回让某一行全变成 x 的最小翻转数若不可行返回 inf rot_top rot_bot 0for t, b in zip(tops, bottoms):if t ! x and b ! x: # 这张牌两面都不是 x不可行return float(inf)if t ! x: # 让上排 x 需翻一次rot_top 1if b ! x: # 让下排 x 需翻一次rot_bot 1return min(rot_top, rot_bot)cand {tops[0], bottoms[0]} # 只需检验这两个数ans min(check(c) for c in cand)return -1 if ans float(inf) else ans5 个人踩坑记录 原始尝试WA 78/84 elif bottomsb: # 我把整个列表跟数字比了Bug 1比较对象写错导致第二个候选数统计永远失效。Bug 2遇到失败只把 tmp 置零然后 break后面依旧用它去更新答案错误写入了 res。Bug 3if tmp: 把 0 次翻转的情况漏掉。
修改这三处后一次 AC。 6 总结
看到“让整行相等”这类题第一步先想 “候选值能否极度缩小”本题直接锁定两种数字。写多分支判断时务必小心 索引 vs 整体这是数组题最易犯的错。当循环里一旦出现 判定失败条件应及时 return不要让无效结果继续污染后续逻辑。 感谢阅读祝早日 AK LeetCode! By 迪小莫学AI
