w****k
发帖数: 755 | 1 一个NXN的board上放了一些棋子，要求返回是否有人获胜。
除了简单的每行每列及对角检查是否相同，还有更好的办法么？我的O（N*N）解法被拒
了。
我看网上说给一方的棋子assign -1 另一方assing +1，然后每一步update包括所有行
列对角和的数组，这样的确能够在已知上一步的状态下在O（1）内得知这一步是否有人
获胜，但在未知的情况下也还得访问board的每一个棋子，O（N*N）是必须的啊。 |
uj
发帖数: 324 | 2 "但在未知的情况下也还得访问board的每一个棋子"??
社么意思？不懂 |
w****k
发帖数: 755 | 3 假设给你的只是一个board[][]作为input，其它什么都没有，也就是
boolean win(int board[][])；
你能写一个比O(N*N)更好的算法么？
【在 uj 的大作中提到】
: "但在未知的情况下也还得访问board的每一个棋子"??
: 社么意思？不懂
|
uj
发帖数: 324 | 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****k
发帖数: 755 | 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**********g
发帖数: 14942 | 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*******s
发帖数: 1979 | 7 就光是检测？行列对角建数组是必须的吧
worse case依然是n^2但是average就不是了
worse case n queen的棋盘反过来是n^2, 但一个n queen总共也没几个解.
大部分情况下都early stop了
大概是这个意思?
【在 w****k 的大作中提到】
: 一个NXN的board上放了一些棋子，要求返回是否有人获胜。
: 除了简单的每行每列及对角检查是否相同，还有更好的办法么？我的O（N*N）解法被拒
: 了。
: 我看网上说给一方的棋子assign -1 另一方assing +1，然后每一步update包括所有行
: 列对角和的数组，这样的确能够在已知上一步的状态下在O（1）内得知这一步是否有人
: 获胜，但在未知的情况下也还得访问board的每一个棋子，O（N*N）是必须的啊。
|
w****k
发帖数: 755 | 8 我猜你说的是对的，我的确没有想过要从上一步的结果来优化，这可能被理解为视角有
限。如果他问如何在每一步检查谁胜，我倒是能想到。
【在 s**********g 的大作中提到】
: 请仔细描述什么叫被拒了
: 如果只是nxn的板子，啥都不知道，然后随机放上一把
: 那么你worst case至少要把格子都遍历一遍，O(N)或O(n2) (此处N = nxn，N or n的定
: 义很重要，有的可能死在定义上。。)
: 但是对方有没有给提示要求优化？如果你没能探讨可能的情形进行优化 那可能面试就
: 终止了
: 优化就是根据之前的结果来优化下一个move的复杂度
: 对方不一定明确给出情形
|
