当青训营遇上码上
前言
能加入到这届的青训营我非常的高兴，更期望自己不仅能经过这次的青训营之旅丰富自己的履历之余，还能够认识到更多的学习伙伴。最终经过高兴写码共享解说我创作创意和过程的一起，也期望大家能够及时纠正我的过错，伴我学习。
使命介绍
小青要找小码去玩，他们的家在一条直线上，当时小青在地点 N ，小码在地点 K （0≤N , K≤100 000），并且小码在自己家原地不动等待小青。小青有两种交通方法可选：步行和公交。 步行：小青能够在一分钟内从恣意节点 X 移动到节点 X-1 或 X+1 公交：小青能够在一分钟内从恣意节点 X 移动到节点 2X （公交不能够向后走）
请帮助小青告诉小码，小青最快到达时刻是多久？ 输入： 两个整数 N 和 K 输出： 小青到小码家所需的最短时刻（以分钟为单位）
使命分析
经过对标题的解读，不难看出这是一个求从起点N到终点K的最短途径的问题，能够运用宽度优先查找算法BFS进行解题。
宽度优先查找算法的查找过程一般是：
（1）从行列头取出一个结点，查看它依照扩展规矩是否能够扩展，假如能则发生一个新结点。
（2）查看新生成的结点，看它是否已在行列中存在，假如新结点现已在行列中呈现过，就抛弃这个结点，然后回到第（1）步。不然，假如新结点未曾在行列中呈现过，则将它加入到行列尾。
（3）查看新结点是否方针结点。假如新结点是方针结点，则查找成功，程序完毕；若新结点不是方针结点，则回到第（1）步，再从行列头取出结点进行扩展。
使命设计
假设小青起点N为节点N，并运用一个双端行列来完成宽度优先查找算法，接着运用一个set来记录现已拜访过的节点，这样就能够防止重复拜访现已拜访过的节点，由此来进步功率。
在这里，我假设小青和小码的方位关系为 N < K，代码中的边界条件也是基于此假设而设置的。假如你需要处理 N > K 的情况，需要对代码进行相应的修改。
另外，在这个问题中，假如起点和终点之间不存在途径，则回来 -1。
最终，这段代码的复杂度为 O(K)，由于只需要遍历K个节点即可找到终点，并且由于运用了set来判重，所以不存在重复便当相同节点的情况。
from collections import deque
def shortest_path(N, K):
queue = deque([(N, 0)])
visited = set()
while queue:
node, step = queue.popleft()
if node == K:
return step
if node not in visited:
visited.add(node)
if node - 1 >= 0:
queue.append((node - 1, step + 1))
if node + 1 <= K:
queue.append((node + 1, step + 1))
if node * 2 <= K:
queue.append((node * 2, step + 1))
return -1
if __name__ == '__main__':
n, k = map(int, input("请输入小青和小码的方位:").split())
print("最短时刻是：",shortest_path(n, k),"分钟")
总结
经过这次的解题，我认为这道标题也能够运用递归来完成宽度优先查找算法，每一层的递归能够看作为一层的BFS，但考虑到递归是一种比较消耗时刻的算法，关于量较大的数据，可能会导致超时，所以我暂时没用尝试运用递归进行解题。
写文章不易，假如你觉得文章对你有帮助，费事点一下点赞、收藏，你的支持是我写文章的最大动力！
最终，期望经过这次的解说创作创意和过程，能让掘友们看到关于这个主题的不一样的解法，也期望掘友们能够及时纠正我的过错。
