Tips为了更好地整合文章，我现已将本文章收录至专栏“青训营题解”，专栏内有其他方向的内容，感兴趣的小伙伴能够关注一下专栏。

当青训营遇上码上

标题：寻友之旅

小青要找小码去玩，他们的家在一条直线上，当时小青在地址 N ，小码在地址 K (0≤N , K≤100000)，并且小码在自己家原地不动等候小青。小青有两种交通方式可选：步行和公交。
步行：小青能够在一分钟内从恣意节点 X 移动到节点 X-1 或 X+1
公交：小青能够在一分钟内从恣意节点 X 移动到节点 2X (公交不能够向后走)
请帮助小青通知小码，小青最快抵达时刻是多久？
输入： 两个整数 N 和 K
输出： 小青到小码家所需的最短时刻（以分钟为单位）

解题思路

解法一：广度优先查找

这道标题能够运用广度优先查找算法来处理，即从小青地点的地址开端，顺次查找小青能够抵达的一切节点，直到找到小码地点的节点。

咱们能够运用一个字典来存储每个节点的步数，然后运用双端行列来存储每个节点。关于每个节点，咱们都将它的左右节点和公交节点参加行列，并更新字典中对应节点的步数。

当咱们找到小码地点的节点时，就能够回来它的步数，表示小青到小码家的最短时刻。假如在查找过程中行列为空，说明没有找到小码地点的节点，此时应该回来 -1。

详细能够看看代码完成

代码完成（Python）：

from collections import deque
def shortest_time(n, k):
    # 用于存储每个节点的步数
    steps = {}
    # 用于存储每个节点的父节点
    parents = {}
    # 将小青的位置参加行列
    queue = deque([n])
    # 将小青的位置设为 0 步
    steps[n] = 0
    # 将小青的父节点设为 None
    parents[n] = None
    # 循环直到行列为空
    while queue:
        # 取出队首元素
        curr = queue.popleft()
        # 假如当时节点便是小码地点的节点，直接回来步数
        if curr == k:
            return steps[k]
        # 将当时节点的左右节点参加行列
        if curr - 1 >= 0:
            if curr - 1 not in steps:
                queue.append(curr - 1)
                steps[curr - 1] = steps[curr] + 1
                parents[curr - 1] = curr
        if curr + 1 <= 100000:
            if curr + 1 not in steps:
                queue.append(curr + 1)
                steps[curr + 1] = steps[curr] + 1
                parents[curr + 1] = curr
        # 将当时节点的公交节点参加行列
        if curr * 2 <= 100000:
            if curr * 2 not in steps:
                queue.append(curr * 2)
                steps[curr * 2] = steps[curr] + 1
                parents[curr * 2] = curr
    # 假如没有找到小码地点的节点，回来 -1
    return -1

解法二：堆优化的迪杰斯特拉算法

为了优化时刻复杂度，这道标题咱们能够运用堆优化的迪杰斯特拉算法来处理。

堆优化的迪杰斯特拉算法

堆优化的迪杰斯特拉算法是一种用于处理单源最短途径问题的最短途径算法。它的基本思想是从起点开端，逐步扩展能够抵达的节点，并经过运用堆数据结构来保护已扩展节点的信息，从而削减枚举节点的次数。

假设有一个带权有向图，需求求出单源最短途径。那么堆优化的迪杰斯特拉算法的流程如下：

  1. 将起点参加到堆中，并设置起点的间隔为 0。
  2. 取出堆顶元素，假如现已求出了结束的最短途径，则中止算法。
  3. 关于当时节点的每一个相邻节点，假如经过当时节点抵达该相邻节点的途径比之前现已求出的途径短，则更新该相邻节点的间隔，并将该相邻节点参加到堆中。
  4. 重复步骤 2 和 3 直到堆为空或许现已求出了结束的最短途径。

关于本题而言，思路如下：

  • 首先，咱们需求界说一个字典来存储每个节点到起点的间隔。
  • 然后，咱们能够运用一个堆来保护一切未被拓宽的节点的间隔，并在每一次拓宽节点时，将该节点的一切相邻节点参加堆中。
  • 最后，咱们能够在遍历完好个图后，回来结束的间隔即可。

详细能够看看代码完成：

代码完成（Python）：

import heapq
def dijkstra(n, k):
    # 存储每个节点的间隔
    distances = [float('inf') for _ in range(100001)]
    # 将起点设为 0 步
    distances[n] = 0
    # 存储现已确认的节点
    processed = set()
    # 初始化堆
    heap = [(0, n)]
    while heap:
        # 取出堆中最小的节点
        distance, curr = heapq.heappop(heap)
        # 假如节点现已被确认，越过
        if curr in processed:
            continue
            # 将节点标记为现已确认
        processed.add(curr)
        # 遍历当时节点的邻接点
        for neighbor in (curr - 1, curr + 1, curr * 2):
            # 假如邻接点不在范围内或许现已被确认，越过
            if neighbor < 0 or neighbor > 100000 or neighbor in processed:
                continue
            # 假如能够更新邻接点的间隔，则将新的间隔参加堆中
            if distance + 1 < distances[neighbor]:
                distances[neighbor] = distance + 1
                heapq.heappush(heap, (distances[neighbor], neighbor))
        # 回来小码地点的节点的间隔
    return distances[k]

成果展现

测试用代码：

# 读入输入
n, k = map(int, input("输入小青和小码的位置，用空格间隔：").split())
# 计算最短途径
result1 = shortest_time(n,k)
result2 = dijkstra(n, k)
# 输出成果
print("BDF解法，最短时刻：",result1,"分钟")
print("堆优化的迪杰斯特拉，最短时刻：",result2,"分钟")

测试用例

2 4096

输出成果

当青训营遇上码上掘金之”寻友之旅“

解法比较

先说定论：我认为，在这道标题中，堆优化的迪杰斯特拉算法更优。

原因是广度优先查找是一种暴力枚举的办法，时刻复杂度为 O(N)，空间复杂度也为 O(N)。在本题中，N能够达到 100000，因此广度优先查找的时刻和空间复杂度都较大，不能很好地处理这道标题。

相反，堆优化的迪杰斯特拉算法是一种运用堆数据结构的最短途径算法，设节点为V、边数为E，算法的时刻复杂度为 O((V+E)logV)，空间复杂度为 O(V)。在本题中，由于图中边数 E 比节点数 V 少得多，因此堆优化的迪杰斯特拉算法的时刻复杂度为 O(VlogV)，相关于广度优先查找的 O(N) 来说，时刻复杂度要小得多，能更快地处理这道标题。

此外，堆优化的迪杰斯特拉算法的空间复杂度也比广度优先查找的空间复杂度小得多，更适合处理这道标题。

因此，在这道标题中，堆优化的迪杰斯特拉算法更优。

文章完好代码&结束

见代码片段： 主题 3：寻友之旅 – 码上 ()
假如你有其他的思路或许更好的解法，亦或许你发现了文章呈现了错误或有不足，欢迎在谈论区和我沟通，我看到了一定会回复。

写文章不易，假如你觉得文章对你有帮助，费事点一下点赞、保藏，你的支持是我写文章的最大动力！