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不可能完成任务 。
参考来源
- LeetCode 1007. 行相等的最少多米诺旋转 C++描述
- 1007 素数对猜想 题目解析、代码、素数的判断 PTAbasic 浙大C++
- LeetCode刷题|贪心算法|#1007 、行相等的最少多米诺旋转
- 1007. Minimum Domino Rotations For Equal Row
- Leetcode 1007. 行相等的最少多米诺旋转
