17.2 设计一个算法，判断玩家是否赢了井字游戏。
解法：
假设这个检查某人是否赢得了井字游戏的函数为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的棋盘是否有人赢，即同一棋子连成一线：
从上到下，从左到右，两条对角线。
C++实现代码：
#include<vector> #include<iostream> using namespace std; int convertBoardToInt(vector<vector<char> > &board) { int factor=1; int sum=0; int i,j; int v; for(i=0; i<3; i++) for(j=0; j<3; j++) { v=0; if(board[i][j]=='X') v=1; if(board[i][j]=='O') v=2; sum+=v*factor; factor*=3; } return sum; } char hasWon(vector<vector<char> > &board) { int i,j; int n=board.size(); //检查每一行 for(i=0; i<n; i++) { for(j=0; j<n-1; j++) { if(board[i][j]!=board[i][j+1]) break; } if(j==n-1) return board[i][j]; } //检查每一列 for(j=0; j<n; j++) { for(i=0; i<n-1; i++) { if(board[i][j]!=board[i+1][j]) break; } if(i==n-1) return board[i][j]; } //检查主对角线 for(j=0; j<n-1; j++) { if(board[j][j]!=board[j+1][j+1]) break; } if(j==n-1) return board[j][j]; for(i=0; i<n-1; i++) if(board[i][n-i-1]!=board[i+1][n-i-2]) break; if(i==n-1) return board[i][0]; return board.empty(); } int main() { vector<vector<char> > vec={{'X','X','O'},{'X','X','O'},{'X','O','O'}}; cout<<hasWon(vec)<<endl; }
![[leetcode/lintcode 题解] 阿里面试题：生成更大的陆地](https://ucc.alicdn.com/pic/developer-ecology/bc470bbcf0004c1f831aad877c7adb56.png?x-oss-process=image/resize,h_160,m_lfit)
![[leetcode/lintcode 题解]国内大厂高频面试题： 最小振幅](https://ucc.alicdn.com/pic/developer-ecology/c6e6b88f43a74bf68f8429a067c58fb0.png?x-oss-process=image/resize,h_160,m_lfit)