设计一个算法，判断玩家是否赢了井字游戏

基于要查找的次数来决定是否要预处理。预处理方式按照3进制来做。

另外，检查是否赢了要判断横行，纵列，正反对角线

解法：

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

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

对于井字游戏，每个格子可以是空，我的棋子和对方的棋子3种可能，总共有39 = 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

这时，需要一个19683 大的数组来存放每一个计算出的整数表示哪一方赢了，或者出现平局。

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

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

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

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

从上到下，从左到右，两条对角线

[java] view plain copy

1. package Moderate;  
2.   
3. /** 
4.  * Design an algorithm to figure out if someone has won in a game of tic-tac-toe. 
5.  
6. 译文： 
7.  
8. 设计算法检查某人是否赢得了井字游戏。  
9.  * 
10.  */  
11. public class S17_2 {  
12.   
13.     // 方法一：如果HasWon函数需要被频繁调用  
14.     public static int convertBoardToInt(char[][] board) {  
15.         int factor = 1;  
16.         int sum = 0;  
17.         for (int i = 0; i < board.length; i++) {  
18.                 for (int j = 0; j < board[i].length; j++) {  
19.                         int v = 0;  
20.                         switch(board[i][j]){  
21.                             case 'x':  
22.                                 v = 1;  
23.                                 break;  
24.                             case 'o':  
25.                                 v = 2;  
26.                                 break;  
27.                             default:  
28.                                 v = 0;  
29.                         }  
30.                           
31.                         sum += v * factor;  
32.                         factor *= 3;  
33.                 }  
34.         }  
35.         return sum;  
36.     }  
37.       
38.       
39.     // 方法二：如果HasWon函数只被调用一次或很少次  
40.     public static char hasWon(char[][] board){  
41.         int type = 0;  
42.         int N = board.length;  
43.           
44.         int i, j;  
45.           
46.         // 对每一行都检查  
47.         for(i=0; i<N; i++){  
48.             if(board[i][0] != ' '){  
49.                 for(j=1; j<N; j++){  
50.                     if(board[i][j] != board[i][j-1]){  
51.                         break;  
52.                     }  
53.                 }  
54.                 if(j == N){  
55.                     return board[i][0];  
56.                 }  
57.             }  
58.         }  
59.           
60.           
61.         // 对每一列都检查  
62.         for(j=0; j<N; j++){  
63.             if(board[0][j] != ' '){  
64.                 for(i=1; i<N; i++){  
65.                     if(board[i][j] != board[i-1][j]){  
66.                         break;  
67.                     }  
68.                 }  
69.                 if(i == N){  
70.                     return board[0][j];  
71.                 }  
72.             }  
73.         }  
74.           
75.         // 正对角线检查（左上到右下）  
76.         if(board[0][0] != ' '){  
77.             for(i=1; i<N; i++){  
78.                 if(board[i][i] != board[i-1][i-1]){  
79.                     break;  
80.                 }  
81.             }  
82.             if(i == N){  
83.                 return board[0][0];  
84.             }  
85.         }  
86.           
87.         // 逆对角线检查（左下到右上）  
88.         if(board[N-1][0] != ' '){  
89.             for(i=1; i<N; i++){  
90.                 if(board[N-i-1][i] != board[N-i][i-1]){  
91.                     break;  
92.                 }  
93.             }  
94.             if(i == N){  
95.                 return board[N-1][0];  
96.             }  
97.         }  
98.           
99.         return ' ';  
100.     }  
101.   
102.   
103.   
104.     public static void main(String[] args) {  
105.             char[][] board = {  
106.                             {'x', 'x', 'o'},  
107.                             {' ', 'x', ' '},  
108.                             {' ', ' ', 'x'}};  
109.               
110.             int v = convertBoardToInt(board);  
111.             System.out.println(v);  
112.               
113.             char result = hasWon(board);  
114.             if(result == ' '){  
115.                 System.out.println("No one won!");  
116.             }else{  
117.                 System.out.println(result + " has won");  
118.             }  
119.               
120.     }  
121.   
122. }