Cracking Coding Interview - 16.4 Tic Tac Win

Tic Tac Win: Design an algorithm to figure out if someone has won a game of tic-tac-toe.

Hints: #710, #732

解法

Tic-Tac-Toe就是那种井字棋，上面画圈圈和叉叉的那种。这个问题实际上就是给你一个残局，让你判断圈圈或者叉叉哪个赢了。

1
2
3

-|-|- 
-|-|-
-|-|-

最简单的办法就是检查每行，每列，两个对角线，那么时间复杂度是O(n)，n=棋盘的宽度，实际上是2 * n + 2次，在3x3的棋盘里就是检查8次。