当前位置：首页 > news >正文

力扣1007：多米诺旋转最少次数解法

news 2026/7/6 8:14:02

LeetCode 1007. 行相等的最少多米诺旋转要求：给定两个长度相等的数组tops和bottoms，分别代表一排多米诺骨牌的顶部和底部数字。一次旋转可以将一个多米诺骨牌的顶部数字翻到底部，或者底部翻到顶部。目标是找到最少的旋转次数，使得所有多米诺骨牌的顶部数字全部相同，或者所有底部数字全部相同。如果无法达成，则返回-1。

核心思路是，最终能使一行相等的数字target只能是tops[0]或bottoms[0]中的一个（因为必须包含第一个骨牌的某个面）。因此，只需检查这两个候选数字，并分别计算使顶部全为target或底部全为target所需的最小旋转次数，取最小值即可。

算法步骤

1.定义辅助函数check(target)，计算使顶部或底部全变为target所需的最小旋转次数。
2. 分别以tops[0]和bottoms[0]作为候选target进行检查。
3. 对于每个target：
* 初始化rotations_top和rotations_bottom为0，分别表示使顶部全为target和使底部全为target所需的旋转次数。
* 遍历每个骨牌i：
* 如果tops[i]和bottoms[i]都不等于target，则该target不可能使任何一行相等，返回INT_MAX表示失败。
* 如果tops[i] != target，则要使顶部全为target，必须旋转此骨牌，rotations_top++。
* 如果bottoms[i] != target，则要使底部全为target，必须旋转此骨牌，rotations_bottom++。
* 返回min(rotations_top, rotations_bottom)，即对于此target的最小旋转次数。
4. 对两个候选target得到的结果取最小值。如果结果仍为INT_MAX，则返回-1，否则返回该最小值。

C++ 代码实现

#include <vector> #include <algorithm> #include <climits> using namespace std; class Solution { public: int minDominoRotations(vector<int>& tops, vector<int>& bottoms) { int n = tops.size(); // 辅助函数：计算使一行全为 target 的最小旋转次数 auto check = [&](int target) -> int { int rotations_top = 0; // 使顶部全为 target 的旋转次数 int rotations_bottom = 0; // 使底部全为 target 的旋转次数 for (int i = 0; i < n; ++i) { // 如果当前骨牌的两个面都不等于 target，则不可能 if (tops[i] != target && bottoms[i] != target) { return INT_MAX; } // 如果顶部不是 target，则需要旋转一次才能使顶部是 target if (tops[i] != target) { rotations_top++; } // 如果底部不是 target，则需要旋转一次才能使底部是 target if (bottoms[i] != target) { rotations_bottom++; } } // 返回两种方案中旋转次数较少的 return min(rotations_top, rotations_bottom); }; // 候选目标只能是第一个骨牌的顶部或底部数字 int ans = min(check(tops[0]), check(bottoms[0])); return ans == INT_MAX ? -1 : ans; } };

复杂度分析

维度	结果	说明
时间复杂度	O(N)	遍历数组两次（检查两个候选数字），每次 O(N)。
空间复杂度	O(1)	只使用了常数个额外变量。

关键点解析

候选数字的有限性：由于必须翻转整个行，且第一个骨牌必然参与，所以最终统一的数字只能是tops[0]或bottoms[0]。这是将问题简化为两次线性检查的关键。
贪心检查：在检查一个候选数字target时，对于每个骨牌，只要其中一个面等于target即可，无需选择旋转哪个面。我们分别统计使顶部全为 target和使底部全为 target所需的旋转次数，最后取最小值。这是因为对于每个骨牌，如果tops[i] == target且bottoms[i] == target，则无论最终目标是统一顶部还是底部，这个骨牌都不需要旋转。
无法完成的条件：如果在检查某个target时，遇到一个骨牌的两个面都不等于target，则该target不可能完成任务。