狗家阳谷挂经 攒人品

木易wen 发表于 2019-3-2 22:48
lz第三轮没给提示吗 需要parent指针才能O(1)

一点提示没有，我后来那办法纯粹自己想的。。我最后问小哥问题时候小哥也说需要用parent 指针。。。

simpleg 发表于 2019-3-2 17:55
princeton 算法书的网站 介绍了一种方法，可以借鉴。

https://algs4.cs.princeton.edu/41graph/Maze.j ...

用bfs做的话，空间比这个小一些...

lxy16555 发表于 2019-3-2 14:30
楼主请问，第一题的第一个follow up有没有什么好方法吗？
给一个历史猜词记录怎么判断是不是好的猜想？

我就是这里答得不太好。。我说的是如果guess的bull分数越高，就越好。。但我不确定

tianchez 发表于 2019-3-2 23:27
用bfs做的话，空间比这个小一些...

请问楼主的bfs做法，是不是就是随机生成一条从起点到终点的路径啊？ 剩下的地方都是墙？
多谢哈

visa 发表于 2019-3-3 07:30
请问楼主的bfs做法，是不是就是随机生成一条从起点到终点的路径啊？ 剩下的地方都是墙？
多谢哈

不完全是，大概是随机四个方向选一个走，用一个visited array记录走过的路，如果选的那个方向已经走过了，就mark成墙，如果没有，就走过去

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

多谢！第一个能看到的面经。。。

tianchez 发表于 2019-3-3 08:37
我设计了一个class 叫cell

class cell{

谢谢楼主，那么楼主是不是还维护了一个stack呀？

visa 发表于 2019-3-3 08:52
谢谢楼主，那么楼主是不是还维护了一个stack呀？

不用，只需要一个bfs都需要的deque和boolean[][] visited就行，而且因为deque会不断的poll，不会存所有的cell，所以空间比dfs/recursion要好