从M走到N最少步数

echobingo

发布于 2018-10-10 03:41:24

81200

代码可运行

文章被收录于专栏：Bingo的深度学习杂货店Bingo的深度学习杂货店

运行总次数：0

代码可运行

题目描述：

假设一个人站在 X 轴的正半轴上，起始点在 M 点（0 <= M <= 100000），他每次可以向左走一步，向右走一步，或者走到所在坐标乘以2的位置，最终来到 N 点（0 <= N <= 100000）。问：所需的最少步数是几步？（如果不能从 M 走到 N 点，则返回 -1）

举例：M = 2，N = 13，则按照 2 -> 3 -> 6 -> 12 -> 13 的走法，最少步数是 4。

解题思路：

此题可用深搜 + 剪枝的方法，可以理解为一棵三叉树。树的结点表示走到的位置，树的深度表示走的步数。这棵三叉树有一个重要的特点：先出现的新结点（新位置）一定是走得最少的步数的位置。

举例说明：

第 0 层                                 4
                              /         |           \
                            3           5             8
                         /  |  \      /  |  \       /  |  \
                       2    4*  6     4  6* 10      7  9  16

在这棵三叉树中，第 2 层的 4*，在原点处已经走过，所以要剪去这个分支，不然会无限往下增加深度；同理，第二个出现的 6* 也要剪去。

具体实现过程，可以维护一个队列 q 和一个已走过的位置数组 visit。q 中是树的结点，代表当前所在位置。visit 数组记录位置是否走过，如果走过，标记为 True。visit 的作用就是用来剪枝，防止已经走过的位置又重新加入到队列 q 中。

如果 M 能到达 N，则结果一定会出现在队列 q 中，这就是程序的出口。

Python 实现：

from collections import deque
class Solution:
    def minStep(self, begin, end):
        """
        :type begin: int, 0 <= begin <= MAX
        :type end: int, 0 <= end <= MAX
        :rtype: int
        """
        MAX = 100000
        if begin < 0 or end < 0 or begin > MAX or end > MAX: # 输入不合法
            return -1
        visit = [False] * (MAX + 1) # 某个结点已经走过
        visit[begin] = True
        sq = deque()  # 新位置结点进入队列
        step = 0
        sq.append((begin, 0))
        while sq:  # 外层循环步数加1，表示当前层 sq 中所有结点判断完
            while sq and sq[0][1] == step:  # 当前层
                i = sq.popleft()
                if i[0] == end:   # 出口必然是队列中的结点
                    return step
                if 0 <= i[0] + 1 <= MAX and not visit[i[0] + 1]:  # 剪枝
                    sq.append((i[0] + 1, step + 1))
                    visit[i[0] + 1] = True
                if 0 <= i[0] - 1 <= MAX and not visit[i[0] - 1]:  # 剪枝
                    sq.append((i[0] - 1, step + 1))
                    visit[i[0] - 1] = True
                if 0 <= i[0] * 2 <= MAX and not visit[i[0] * 2]:  # 剪枝
                    sq.append((i[0] * 2, step + 1))
                    visit[i[0] * 2] = True
            step += 1
        return step

begin = 2
end = 13
print(Solution().minStep(begin, end))  # 4

知识补充：

1、Pyton 双向队列用法：

from collections import deque
q = deque()

这是一个双向队列，可以把它理解成一个列表，只不过在左右两侧都可以进行插入和弹出操作：

q.append(i)
q.appendleft(i)  # 左侧插入
q.insert(ind, val)  # 在索引 ind 前插入一个值 val
i = q.pop()   # 右侧删除
i = q.popleft()  # 左侧删除
if q:   # 判断不为空
    #...
q[0]  # 得到队列头元素
q[-1]  # 得到队列尾元素
q.clear()  # 清空队列
q.reverse() # 队列中的所有元素进行翻转
q.rotate()   # 向右旋转队列 n步（默认 n = 1），如果n为负，向左旋转。