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(vectorint tops, vectorint 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 浙大CLeetCode刷题|贪心算法|#1007 、行相等的最少多米诺旋转1007. Minimum Domino Rotations For Equal RowLeetcode 1007. 行相等的最少多米诺旋转