题目分析

遇到本题，我们先思考应该如何交换，能否先交换列，然后再交换行？交换列时有什么特征，交换行有什么特征？

模拟

我们尝试先交换列，然后再交换行。发现交换某两行时，并不会影响两行中，每一行元素的相对位置。如[A, B, C]与[D, E, F]交换，结果是[D, E, F]与[A, B, C]，不会影响每一行内部的相对位置。

最后的结果要求每一行与上一行相反，也可以得出每一行与上两行相等的逻辑。我们把每一行当作一个字符串，那么可以得出的结论是，能变为棋盘的结果，行组成的字符串只有两种。如果用二进制表示，那么第一行是X，第二行就是~~X，波浪线~~表示取反。

先交换行、再交换列也是一样的，这里就以先交换列，再交换行为例。

因为交换行不会影响每一行的内部顺序，所以在交换列就需要保证每一行的内部顺序。因为当第一行的内部顺序定了之后，整个棋盘就确定了，因此我们需要考虑010101…作为第一行需要移动列的次数firstRowMove0，表示第一行以0开头的移动次数，如果等于-1，说明不能以0开头。再考虑第一行以1开头的移动次数firstRowMove1。取交换列满足的最小次数colMove。

比如10101，此时第一行1的数量大于0的数量，因此在仅交换列的情况下，无法满足第一行以0开头。此时返回-1。

根据上面的分析，交换行时，不会影响行内的顺序，因此数组初始时，二进制表示的行就只有两个值，X和~~X。设原数组第一行的值为X，那么棋盘数组的第一行为X或者~~X。我们考虑以X作为第一行需要移动行的次数，然后再考虑以~X作为第一行需要移动行的次数。取交换行满足的最小次数rowMove。将两者相加就是最终的结果。

为什么是列交换的最小值+行的最小值等于结果的最小值呢？

如果列交换的最小值是0开头的，行交换的最小值是1开头的，那就不应该成立。为什么还可以这样求解呢？

因为列交换的最小值是0开头的X，行交换的最小值是1开头的~X，在交换行时。

考虑以~~X为第一行时，交换次数就已经+1了，因为第一行X需要和另一个~~X的行进行交换。

如果还能取得最小值，那么以~X为第一行就是变为棋盘的最小交换次数。

此时结果是先将列交换为X，然后再将行交换为以~X为数组的第一行。

算法的**时间复杂度为O(n^2)，空间复杂度为O(1)**。

class Solution {
    public int movesToChessboard(int[][] board) {
        int n = board.length;

        int rowMove0 = getFirstRowMoves(0, board[0]);
        int rowMove1 = getFirstRowMoves(1, board[0]);
        if (rowMove0 == -1 && rowMove1 == -1) {
            return -1;
        }
        int rowMove = rowMove0 == -1 || rowMove1 == -1 ? Math.max(rowMove0, rowMove1) : Math.min(rowMove0, rowMove1);

        int standard = getBit(board[0]);
        int colMove0 = getFirstColMoves(true, standard, board);
        int colMove1 = getFirstColMoves(false, standard, board);
        if (colMove0 == -1 && colMove1 == -1) {
            return -1;
        }
        int colMove = colMove0 == -1 || colMove1 == -1 ? Math.max(colMove0, colMove1) : Math.min(colMove0, colMove1);
        return rowMove + colMove;
    }

    private int getBit(int[] firstRow) {
        int standard = 0;
        int currentBit = 1;
        for (int x : firstRow) {
            if (x == 1) {
                standard += currentBit;
            }
            currentBit <<= 1;
        }
        return standard;
    }

    private int getFirstRowMoves(int flag, int[] firstRow) {
        int oneCnt = 0;
        int moves = 0;
        int current = flag;
        for (int x : firstRow) {
            if (x == 1) {
                oneCnt++;
            }
            if (x != current) {
                moves++;
            }
            current = 1 - current;
        }
        if (flag == 1 && (oneCnt * 2 == firstRow.length || oneCnt * 2 - 1 == firstRow.length)) {
            return moves / 2;
        }
        if (flag == 0 && (oneCnt * 2 == firstRow.length || oneCnt * 2 + 1 == firstRow.length)) {
            return moves / 2;
        }
        return -1;
    }

    private int getFirstColMoves(boolean flag, int standard, int[][] board) {
        int firstCnt = 0;
        int moves = 0;
        boolean current = flag;
        int reversedStandard = (~standard) & ((1 << board.length) - 1);
        for (int[] row :  board) {
            int bit = getBit(row);
            if (bit != standard && bit != reversedStandard) {
                return -1;
            }
            if (bit == standard) {
                firstCnt++;
            }
            if (current != (bit == standard)) {
                moves++;
            }
            current = !current;
        }
        if (flag && (firstCnt * 2 == board.length || firstCnt * 2 - 1 == board.length)) {
            return moves / 2;
        }
        if (!flag && (firstCnt * 2 == board.length || firstCnt * 2 + 1 == board.length)) {
            return moves / 2;
        }
        return -1;
    }
}

刷题总结

这个题目比较复杂，但是实现起来还是有一定难度的。希望小伙伴们能在提示下求解出本题。