求8.17京东笔试第三题解法
第三题回家过年
题目大致描述:n 个点、m 条边、期望路途长度 a。问:从点 1 到终点 n,长度为 a 的路径数有多少?
测试案例:
输入
3 6 2
1 2 1
1 2 1
1 2 1
2 3 1
2 3 1
2 3 1
输出:9
看大佬是用记忆化搜索或动态规划做的,菜鸡一开始也想到了 f(i, j) 表示点1 到 i,距离为 j 的方案数,但是没想通怎么处理循环路径(循环边会累加距离?),所以作罢。
交卷后想了想,感觉可以用 BFS,将遍历到的点相邻的点和到这些点的距离入队(距离大于 a 则跳过),好像也可以解决?
题目大致描述:n 个点、m 条边、期望路途长度 a。问:从点 1 到终点 n,长度为 a 的路径数有多少?
测试案例:
输入
3 6 2
1 2 1
1 2 1
1 2 1
2 3 1
2 3 1
2 3 1
输出:9
看大佬是用记忆化搜索或动态规划做的,菜鸡一开始也想到了 f(i, j) 表示点1 到 i,距离为 j 的方案数,但是没想通怎么处理循环路径(循环边会累加距离?),所以作罢。
交卷后想了想,感觉可以用 BFS,将遍历到的点相邻的点和到这些点的距离入队(距离大于 a 则跳过),好像也可以解决?
全部评论
DFS+记忆化,这题循环路径如果能走通的话应该算在答案里吧

bfs怎么做呢
M
Bfs只能通过50%
相关推荐
点赞 评论 收藏
分享
03-25 18:24
广东海洋大学 前端工程师
smile丶snow:感觉可以加一些ai相关的内容吧。现在面试很少能逃掉这些问题。羡慕里面感觉缺少一个项目背景。比如第二个项目后台管理系统…你为什么要做这个后台管理系统呢?是为了解决什么问题。比如你管理一个商品列表的增加减少。需要一个背景吧。哦或者说你第一个电子书那个是c端的,你肯定需要一个管理系统吧,那就是第二个后台管理系统,但这两个难道不应该是一个项目吗?可以稍微包装一下,最起码让人看着不是玩具项目。个人观点。 点赞 评论 收藏
分享
拼多多集团-PDD成长空间 1384人发布