先上题目
光明小学的小朋友们要举行一年一度的接力跑大赛了，但是小朋友们却遇到了一个难题：设计接力跑大赛的线路，你能帮助他们完成这项工作么？
光明小学可以抽象成一张有N个节点的图，每两点间都有一条道路相连。光明小学的每个班都有M个学生，所以你要为他们设计出一条恰好经过M条边的路径。
光明小学的小朋友们希望全盘考虑所有的因素，所以你需要把任意两点间经过M条边的最短路径的距离输出出来以供参考。你需要设计这样一个函数：
res[][] Solve( N, M, map[][]);
注意：map必然是N * N的二维数组，且map[i][j] == map[j][i]，map[i][i] == 0，-1e8 <= map[i][j] <= 1e8。（道路全部是无向边，无自环）2 <= N <= 100, 2 <= M <= 1e6。map数组表示了一张稠密图，其中任意两个不同节点i,j间都有一条边，边的长度为map[i][j]。N表示其中的节点数。
你要返回的数组也必然是一个N * N的二维数组，表示从i出发走到j，经过M条边的最短路径
你的路径中应考虑包含重复边的情况。样例：
N = 3
M = 2
map = {
{0, 2, 3},
{2, 0, 1},
{3, 1, 0}
}输出结果result为：
result = {
{4, 4, 3},
{4, 2, 5},
{3, 5, 2}
}输入样例：
3
2
3 3
0 2 3
2 0 1
3 1 0输出样例：
[[4, 4, 3],
[4, 2, 5],
[3, 5, 2]]
题目分析
首先确定的就是，题目给出的是一个有N个节点的无向完全图，同时，要求只能走M步，也就是搜索长度被确定为了M，那这样其实思路就很清晰了。由于只给了30分钟，那么太精巧的算法估计一时半会想不出来（对于我这种菜鸟来说啊哈哈哈哈或）那么怎么办？当然是暴力解法最有用了。通过递归的方法，在有限的步长下遍历所有的可能，然后返回最小距离即可。十分感谢CSDN的大佬@蛋烘糕（https://blog.csdn.net/u012465304/article/details/81180707）提供的思路，他的代码是C语言的，如果大家对C比较熟悉可以参考他的代码。
代码思路
这里就是一个比较头疼的地方了，如果是递归遍历，那么参数需要的东西就很多了，包括步长，距离等，同时，对于每一个点在搜索完后的回退，要记得同样要给步长减一，不过如果你的参数形式是这样的，比如len是步长dis是距离，参数是len + 1和dis + graph[new_start][dest]，这样的话，由于这样的传参方式不会改变变量本身大小，那么就直接用就好，不需要再回退的时候还要重新计算，算是一个小技巧。
实际我用了好多好多参数，但是用上的不多，测试结束后回看自己的代码，怕是会把HR气死
部分代码
欸，为了让大家也有锻炼的机会，我这里就提供深度遍历部分的Python代码，其他部分大家就可以参考这段代码依次类推啦，但是不瞒大家，我花时间最多的地方除了理解题目和思路，就是在如何按照格式输入的问题了……真是没想到：
def dfs(graph, dest, curr, step, M, N, min_dis, dis):
if step == M:
if curr == dest:
if min_dis > dis:
min_dis = dis
return min_dis
for i in range(N):
if i is not curr:
min_dis = dfs(graph, dest, i, step + 1, M, N, min_dis, dis + int(graph[curr][i]))
return min_dis
反思
现在也是校招旺季，我也参加了不少的编程线上测试，不得不说自己真的是菜得可怕，尤其是在Google的CodeJam上，自己绞尽脑汁好不容易拿下第一题的时候，看排行榜已经有人快做完了。
？？？？？
果然是大佬们啊，所以说其实写代码这个东西尤其是线上测试，我觉得就是要多练，很多的东西我觉着其实是有一些套路的，同时，比如做多了以后，手自然熟悉，不会一上手，大部分时间都花在了回忆基本操作上。尤其是在时间有限的情况下更为忌讳。当然哈哈哈，想要成为那些Google的大佬们还是需要很多时间的训练，同时再加上一点点天赋加成，应该也是可以无限接近的，加油加油！
网友评论