网易雷火9.28服务端笔试

第一题,纯暴力0.51,双指针ac;
第二题,纯暴力0.16,dp优化ac;
第三题,暴力模拟ac;
第四题,纯暴力0.18,dfs剪枝优化后0.52,起点选取优化后0.78,后面怎么优化都是0.78,有没有大佬说一下这个是怎么优化的?
我是这么想的,模拟水的深度,进行两点之间的连通性判断。水的深度跳跃式增加,理论上来说复杂度降了许多,但是最后这几个测试点没有过,是不是我思路的问题?有没有什么好的方法?
全部评论
第四题就是小顶堆+bfs,其实就相当于你不要闲着,一直沿着能走的路,总能走到终点的,一直能走的路就是当前最小高度的路。感觉这一点想清楚了就容易了,然后二分+dfs好像会超时一丢丢,这种数据量即mnlogmn应该只会超时一丢丢,因为mn最大值是490000,一般来说1e5支持nlogn的。但是你可以借鉴a*算法,尝试先探离目标点近的点,不知道会不会超时。
点赞 回复 分享
发布于 今天 11:05 上海
校友哎,来百度做同事呀
点赞 回复 分享
发布于 昨天 13:18 山东
突然觉得能暴力到0.78已经是天才了
点赞 回复 分享
发布于 昨天 11:18 广东
怀疑雷火最后5%测试点藏了算法导论
点赞 回复 分享
发布于 昨天 11:18 山西
给了多长时间做题
点赞 回复 分享
发布于 昨天 11:11 陕西
维护一个优先队列就行了,把起点入队,每次最浅的出队,再把ans和当前出队的深度进行比较,深度更深就更新ans(不能用max(ans, depth),需要用if判断,不然最后一个用例会超时),再把周围四个没访问过的入队,直到终点出队就行。
点赞 回复 分享
发布于 昨天 01:57 浙江
这次忘做了,还有机会吗
点赞 回复 分享
发布于 09-28 18:38 江苏
深度排序,遍历深度并查集判断连通
点赞 回复 分享
发布于 09-28 17:22 浙江
二分时间,判断当前时间是否连通(剪枝+bfs)
点赞 回复 分享
发布于 09-28 17:21 北京

相关推荐

09-28 20:00
上海大学 Java
点赞 评论 收藏
分享
09-28 16:30
南开大学 C++
投递网易游戏雷火等公司10个岗位
点赞 评论 收藏
分享
ResourceUt...:mark献❀得🐧
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务