井字减少运行时间O（N）

Question

在这个great book，我们要求设计一个算法，计算出，如果有人在井字棋的游戏赢得。 以下溶液中给出，在此之后，笔者说：

注意，运行时可与加成 行和列计数阵列（和两个总和为对角线）

的减少到O（N）

我很努力，但我无法找出这句话的含义。这些数组和总和是如何添加的？谢谢 ！

enum Piece { Empty, Red, Blue }; 
enum Check { Row, Column, Diagonal, ReverseDiagonal } 

Piece getIthColor(Piece[][] board, int index, int var, Check check) { 
    if (check == Check.Row) return board[index][var]; 
    else if (check == Check.Column) return board[var][index]; 
    else if (check == Check.Diagonal) return board[var][var]; 
    else if (check == Check.ReverseDiagonal)  
    return board[board.length - 1 - var][var];  

    return Piece.Empty; 
} 

Piece getWinner(Piece[][] board, int fixed_index, Check check) {  
    Piece color = getIthColor(board, fixed_index, 0, check); 
    if (color == Piece.Empty) return Piece.Empty; 
    for (int var = 1; var < board.length; var++) { 
    if (color != getIthColor(board, fixed_index, var, check)) { 
     return Piece.Empty; 
    } 
    } 
    return color; 
} 

Piece hasWon(Piece[][] board) { 
    int N = board.length; 
    Piece winner = Piece.Empty; 

    // Check rows and columns 
    for (int i = 0; i < N; i++) { 

    winner = getWinner(board, i, Check.Row); 
    if (winner != Piece.Empty) { 
     return winner; 
    }  

    winner = getWinner(board, i, Check.Column);  
    if (winner != Piece.Empty) { 
     return winner; 
    } 

    }  

    winner = getWinner(board, -1, Check.Diagonal); 
    if (winner != Piece.Empty) { 
    return winner; 
    }  

    // Check diagonal  
    winner = getWinner(board, -1, Check.ReverseDiagonal); 
    if (winner != Piece.Empty) { 
    return winner; 
    } 

    return Piece.Empty; 
} 

Answer 1

每当一个新的片被放置在板，则增加1的适当的行，列和（可能）对角线计数器您可能已为玩家独立的计数器，或使用+ 1/-1 。

现在，当您检查板，你只需要检查任何该计数器是否等于N，它可以在O(N)（2N + 2个计数器）来完成。

Answer 2

什么他们大概的意思是，当你把块，更新的金额为每个阵列的部分贡献。也就是相应的行和列。如果它在对角线上，那么你也更新它。

在更新方面，你会增加1，如果是红色，再减去1，如果它是蓝色的。如果你的计数从0开始，那么如果数值达到-3或3，你就有一个胜利者。