LeetCode 1007 Minimum Domino Rotations For Equal Row

思路

只存在三种情况:相同的数是A[0]/B[0]/null。然后分别将A[0],B[0]作为target,同时遍历A和B数组。如果位置i的A和B的值与A[0],B[0]都不等,那么说明不可能完成该任务;否则相应的rotationA++或者rotationB++。最后取一个最小值(贪心)返回即可。

复杂度

时间复杂度O(n)
空间复杂度O(1)

代码

class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int rotation = getRotationTime(A, B, A[0]);
        if (rotation != -1 || A[0] == B[0]) {
            //A[0] == B[0]说明没有必要再进行后面的getRotationTime了
            return rotation;
        }
        return getRotationTime(A, B, B[0]);
    }
    
    private int getRotationTime(int[] A, int[] B, int target) {
        int rotationA = 0, rotationB = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != target && B[i] != target) {
                return -1;
            } else if (A[i] != target) {
                rotationA++;
            } else if (B[i] != target) {
                rotationB++;
            }
        }
        
        return Math.min(rotationA, rotationB);
    }
}
上一篇:Codeforces Round #588 (Div. 2) C. Anadi and Domino


下一篇:domino配置多个邮件域名