脸书店面

yywwd 发表于 2020-9-18 13:59
#1 利口 衣耳漆舞-变体，3x3 变 任意 nxn ，要求O(1)的时间复杂度解出来
请问楼主时间要求是不是写错了。 ...

每次输入一步，都进行判断这步是否分出了胜负。 O(1)是指每一步的复杂度。

sieg 发表于 2020-9-18 11:39
第一题，O（1） 时间复杂度。。？楼主的意思是O（1）判断是否有胜负手？
第二题，是不是 蠡口 而散

第一题，对的, 每下一步棋，用 O(1) 判断这步的胜负手。
第二题，是的，利口 而散 更接近面试官的题目描述

谢谢楼主分享，第一题目这个变体挺有意思。

听说最近FB没有E4 HC了？

计数吧 我觉得
行 列 斜对角分别计数
最开始为0
放X 就+1
放0就-1
当其中一个==n或者-n或者下完结束

kylelua 发表于 2020-9-18 21:14
没错，O(1) 是指判断每一步是否获胜的复杂度。步数是一个一个给的。

每row每col每dia各给两个counter，每步加当前步的counter，什么时候counter等于边长就可以返回结果了。

终于有一个帖子是可以看到一点内容的了。。。谢谢楼主

这个tic toc的题，算法不难，可是20分钟我肯定写不出来啊。看到差距了！

khart 发表于 2020-10-4 09:46
这个tic toc的题，算法不难，可是20分钟我肯定写不出来啊。看到差距了！

刚做了一下，用了40分钟！思考用什么方法判断输赢多花了十分钟。一个数组指针的bug卡了十分钟。

第二题的复杂度是(nlogk)吧？如果n表示一共有多少个数，然后用个priorityqueue