Cracking the coding interview--Q19.2

February 20, 2013
作者:Hawstein
出处:http://hawstein.com/posts/19.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Design an algorithm to figure out if someone has won in a game of tic-tac-toe.

译文:

设计算法检查某人是否赢得了井字游戏。

解答

假设这个检查某人是否赢得了井字游戏的函数为HasWon,那么我们第一步要向面试官确认, 这个函数是只调用一次,还是要多次频繁调用。如果是多次调用, 我们可以通过预处理来得到一个非常快速的版本。

方法一:如果HasWon函数需要被频繁调用

对于井字游戏,每个格子可以是空,我的棋子和对方的棋子3种可能,总共有3^9 = 19683 种可能状态。我们可以把每一种状态转换成一个整数, 预处理时把这个状态下是否有人赢得了井字游戏保存起来,每次检索时就只需要O(1)时间。 比如每个格子上的3种状态为0(空),1(我方棋子),2(对方棋子),棋盘从左到右, 从上到下依次记为0到8,那么任何一个状态都可以写成一个3进制的数,再转成10进制即可。 比如,下面的状态:

1 2 2
2 1 1
2 0 1
可以写成:
122211201=1*3^8 + 2*3^7 +...+ 0*3^1 + 1*3^0

如果只需要返回是否有人赢,而不需要知道是我方还是对方。 那可以用一个二进制位来表示是否有人赢。比如上面的状态,1赢, 就可以把那个状态转换成的数对应的位置1。如果需要知道是谁赢, 可以用一个char数组来保存预处理结果。

方法二:如果HasWon函数只被调用一次或很少次

如果HasWon函数只被调用一次或很少次,那我们就没必要去预存结果了, 直接判断一下就好。只为一次调用去做预处理是不值得的。

代码如下,判断n*n的棋盘是否有人赢,即同一棋子连成一线:

#include <iostream>
using namespace std;

enum Check{
    ROW, COLUMN, DIAGONAL, REDIAGONAL
};

int CheckRowColumn(int board[], int n, Check check){
    int type = 0;
    for(int i=0; i<n; ++i){
        bool found = true;
        for(int j=0; j<n; ++j){
            int k = 0;
            if(check == ROW)
                k = i * n + j;
            else
                k = i + j * n;
            if(j == 0){
                type = board[k];
            }
            else if(board[k] != type){
                found = false;
                break; // 有一个不满足,检查下一行
            }
        }
        if(found) return type;
    }
    return 0;
}
int CheckDiagonal(int board[], int n, Check check){
    int type = 0;
    bool found = true;
    // 主对角
    for(int i=0; i<n; ++i){
        int k = 0;
        if(check == DIAGONAL)
            k = i + i * n;
        else
            k = i + (n-1-i) * n;
        if(i == 0){
            type = board[k];
        }
        else if(board[k] != type){
            found = false;
            break;
        }
    }
    if(found) return type;

    return 0;
}
int HasWon(int board[], int n){
    int type = 0;
    type = CheckRowColumn(board, n, ROW);
    if(type != 0) return type;
    type = CheckRowColumn(board, n, COLUMN);
    if(type != 0) return type;
    type = CheckDiagonal(board, n, DIAGONAL);
    if(type != 0) return type;
    type = CheckDiagonal(board, n, REDIAGONAL);
    if(type != 0) return type;

    return 0;
}
int main(){
    int n = 3; // 3*3
    int board[] = {
        2, 2, 1,
        2, 1, 1,
        1, 2, 0,
    };
    int type = HasWon(board, n);
    if(type != 0)
        cout<<type<<" won!"<<endl;
    else
        cout<<"nobody won!"<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview