h****8
发帖数: 599 | 1 design an algorithm to figure out if someone has won in a game of tic-tac-
toe, N*N board.
普通答案是O（N^2)，就是一行一行，一列一列地去数，比如用户用的是黑色，就计算
某一行或列总共黑色的格子数目，如果最后是N个格子，那么就赢了
但答案中说，如果增加两个array,来分别记录每一行每一列各数出多少个黑色格子，就
可以达到O（N）。原文是这样：
runtime could be reduced to O(N) with the addition of row and column count
arrays and two sums for the diagonals
我不明白这是如何做到的。在第157页 谢谢大家 | j***n
发帖数: 301 | 2 这个，N2的棋盘，不用都看一遍就能定胜负？
【在 h****8 的大作中提到】
: design an algorithm to figure out if someone has won in a game of tic-tac-
: toe, N*N board.
: 普通答案是O（N^2)，就是一行一行，一列一列地去数，比如用户用的是黑色，就计算
: 某一行或列总共黑色的格子数目，如果最后是N个格子，那么就赢了
: 但答案中说，如果增加两个array,来分别记录每一行每一列各数出多少个黑色格子，就
: 可以达到O（N）。原文是这样：
: runtime could be reduced to O(N) with the addition of row and column count
: arrays and two sums for the diagonals
: 我不明白这是如何做到的。在第157页 谢谢大家
| h****8
发帖数: 599 | 3 就是阿 我也不明白 它增加两个array,唯一与之前不同的在于，之前每次数完，判断完
是不是N，就把这个变量扔掉了，而现在是把数完的结果存起来
难道只要数某些行就可以判段？
【在 j***n 的大作中提到】
: 这个，N2的棋盘，不用都看一遍就能定胜负？
| z*********3
发帖数: 37 | 4 O(N)不可能吧。。。我怎么没在careercup上发现有这么一段话 | h****8
发帖数: 599 | 5 page 157, question 9.1
【在 z*********3 的大作中提到】
: O(N)不可能吧。。。我怎么没在careercup上发现有这么一段话
| t****t
发帖数: 6806 | 6 你理解得不对吧, 我觉得它的意思是如果棋盘的状态maintain多两个数组, 就可以快速
的判断是不是胜, 这个很正确啊
比如你每走一步都要看是不是赢了, 那你其实只要把新走的那一步牵涉到的行, 列以及
对角线上的count+1就行了, 对不对
【在 h****8 的大作中提到】
: page 157, question 9.1
| h****8
发帖数: 599 | 7 是这个意思啊 好吧 谢拉
【在 t****t 的大作中提到】
: 你理解得不对吧, 我觉得它的意思是如果棋盘的状态maintain多两个数组, 就可以快速
: 的判断是不是胜, 这个很正确啊
: 比如你每走一步都要看是不是赢了, 那你其实只要把新走的那一步牵涉到的行, 列以及
: 对角线上的count+1就行了, 对不对
| m*****g
发帖数: 226 | 8 如果只看每走一步的话
每次只要检查新走的那个子所在的行列和对角线，不用纪录以前的状态也是O(n)阿 |
|
