网易雷火9.28服务端笔试
第一题,纯暴力0.51,双指针ac;
第二题,纯暴力0.16,dp优化ac;
第三题,暴力模拟ac;
第四题,纯暴力0.18,dfs剪枝优化后0.52,起点选取优化后0.78,后面怎么优化都是0.78,有没有大佬说一下这个是怎么优化的?
我是这么想的,模拟水的深度,进行两点之间的连通性判断。水的深度跳跃式增加,理论上来说复杂度降了许多,但是最后这几个测试点没有过,是不是我思路的问题?有没有什么好的方法?
第二题,纯暴力0.16,dp优化ac;
第三题,暴力模拟ac;
第四题,纯暴力0.18,dfs剪枝优化后0.52,起点选取优化后0.78,后面怎么优化都是0.78,有没有大佬说一下这个是怎么优化的?
我是这么想的,模拟水的深度,进行两点之间的连通性判断。水的深度跳跃式增加,理论上来说复杂度降了许多,但是最后这几个测试点没有过,是不是我思路的问题?有没有什么好的方法?
全部评论
维护一个优先队列就行了,把起点入队,每次最浅的出队,再把ans和当前出队的深度进行比较,深度更深就更新ans(不能用max(ans, depth),需要用if判断,不然最后一个用例会超时),再把周围四个没访问过的入队,直到终点出队就行。
这次忘做了,还有机会吗
深度排序,遍历深度并查集判断连通
二分时间,判断当前时间是否连通(剪枝+bfs)
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享