YunheWang0813
3/5/2020 - 6:30 AM

1007. Minimum Domino Rotations For Equal Row

// 核心思想:对于A[0]和B[0],分别找两列有没有相同元素,且记录A->B交换与B->A交换的次数,当条件满足且到达array最后的min交换值
// 如果有答案,那么就可以直接return,因为不可能有两个min不同的答案,所以没有必要比较
class Solution {
public:
    int minDominoRotations(vector<int>& A, vector<int>& B) {
        int n = A.size();
        // Test for A[0]
        int a_swap = 0, b_swap = 0;
        for (int i = 0; i < n && (A[i] == A[0] || B[i] == A[0]); i++) {
            if (A[i] != A[0]) a_swap++;
            if (B[i] != A[0]) b_swap++;
            if (i == n - 1) return min(a_swap, b_swap);
        }
        // Test for B[0]
        a_swap = 0, b_swap = 0;
        for (int i = 0; i < n && (A[i] == B[0] || B[i] == B[0]); i++) {
            if (A[i] != B[0]) a_swap++;
            if (B[i] != B[0]) b_swap++;
            if (i == n - 1) return min(a_swap, b_swap);
        }
        // Impossible
        return -1;
    }
};