Tic Tac Toe 检查是否获胜的最优解是啥？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Tic Tac Toe 检查是否获胜的最优解是啥？

Tic Tac Toe 检查是否获胜的最优解是啥？# JobHunting - 待字闺中

w*k2017-02-19 08:02

1 楼

一个NXN的board上放了一些棋子，要求返回是否有人获胜。
除了简单的每行每列及对角检查是否相同，还有更好的办法么？我的O（N*N）解法被拒
了。
我看网上说给一方的棋子assign -1 另一方assing +1，然后每一步update包括所有行
列对角和的数组，这样的确能够在已知上一步的状态下在O（1）内得知这一步是否有人
获胜，但在未知的情况下也还得访问board的每一个棋子，O（N*N）是必须的啊。

uj2017-02-19 08:02

2 楼

"但在未知的情况下也还得访问board的每一个棋子"??
社么意思？不懂

w*k2017-02-19 08:02

3 楼

假设给你的只是一个board[][]作为input，其它什么都没有，也就是
boolean win(int board[][])；
你能写一个比O(N*N)更好的算法么？

【在 uj 的大作中提到】

: "但在未知的情况下也还得访问board的每一个棋子"??
: 社么意思？不懂

uj2017-02-19 08:02

4 楼

* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
题目是给你空旗盘，然后一系列moves
如果解法是keep track rows, cols, diagonal, anti-diagonal 用掉空间 O(n),
每一个move，需要update 和检查4个数，你觉得是 N square complexity ??

w*k2017-02-19 08:02

5 楼

你看你的题目和我的不一样。

【在 uj 的大作中提到】

: * Your TicTacToe object will be instantiated and called as such:
: * TicTacToe obj = new TicTacToe(n);
: * int param_1 = obj.move(row,col,player);
: 题目是给你空旗盘，然后一系列moves
: 如果解法是keep track rows, cols, diagonal, anti-diagonal 用掉空间 O(n),
: 每一个move，需要update 和检查4个数，你觉得是 N square complexity ??

s*g2017-02-19 08:02

6 楼

请仔细描述什么叫被拒了
如果只是nxn的板子，啥都不知道，然后随机放上一把
那么你worst case至少要把格子都遍历一遍，O(N)或O(n2) (此处N = nxn，N or n的定
义很重要，有的可能死在定义上。。)
但是对方有没有给提示要求优化？如果你没能探讨可能的情形进行优化那可能面试就
终止了
优化就是根据之前的结果来优化下一个move的复杂度
对方不一定明确给出情形

【在 w****k 的大作中提到】

: 一个NXN的board上放了一些棋子，要求返回是否有人获胜。
: 除了简单的每行每列及对角检查是否相同，还有更好的办法么？我的O（N*N）解法被拒
: 了。
: 我看网上说给一方的棋子assign -1 另一方assing +1，然后每一步update包括所有行
: 列对角和的数组，这样的确能够在已知上一步的状态下在O（1）内得知这一步是否有人
: 获胜，但在未知的情况下也还得访问board的每一个棋子，O（N*N）是必须的啊。

e*s2017-02-19 08:02

7 楼

就光是检测？行列对角建数组是必须的吧
worse case依然是n^2但是average就不是了
worse case n queen的棋盘反过来是n^2, 但一个n queen总共也没几个解.
大部分情况下都early stop了
大概是这个意思?

【在 w****k 的大作中提到】

w*k2017-02-19 08:02

8 楼

我猜你说的是对的，我的确没有想过要从上一步的结果来优化，这可能被理解为视角有
限。如果他问如何在每一步检查谁胜，我倒是能想到。

【在 s**********g 的大作中提到】

: 请仔细描述什么叫被拒了
: 如果只是nxn的板子，啥都不知道，然后随机放上一把
: 那么你worst case至少要把格子都遍历一遍，O(N)或O(n2) (此处N = nxn，N or n的定
: 义很重要，有的可能死在定义上。。)
: 但是对方有没有给提示要求优化？如果你没能探讨可能的情形进行优化那可能面试就
: 终止了
: 优化就是根据之前的结果来优化下一个move的复杂度
: 对方不一定明确给出情形