用 Python 编写程序，查找到达最后一个索引所需的最少步数

pythonserver side programmingprogramming

假设我们有一个名为 nums 的数字列表，我们当前位于 nums[0]。在每一步中，我们可以从当前索引 i 跳转到 i + 1 或 i - 1 或 j，其中 nums[i] == nums[j]。我们必须找到达到最终索引所需的最少步数。

因此，如果输入为 nums = [4, 8, 8, 5, 4, 6, 5]，则输出将为 3，因为我们可以从索引 0 跳转到索引 4，因为它们的值都是 4。然后我们跳回到索引 3。最后，我们可以从索引 3 跳转到 6，因为它们的值都是 5。

为了解决这个问题，我们将遵循以下步骤 −

pos := 一个空映射
对于每个索引 i 和 nums 中的值 n，执行
- 在 pos[n] 的末尾插入 i
n := nums 的大小
visited := 创建一个大小为 n 的列表，并且用 False 填充
visited[0] := True
当 q 不为空时，执行
- (u, d) := q 的左元素，并删除左元素
- 如果 u 与 n - 1 相同，则
  - 返回 d
- 对于列表 pos[nums[u]] 和 [u - 1, u + 1] 中的每个 v，执行
  - 如果 0 <= v < n 且 visit[v] 为 false，则
    - visited[v] := True
    - 在 q 末尾插入对 (v, d + 1)
- 删除 pos[nums[u]]

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, nums):
      from collections import defaultdict, deque
      pos = defaultdict(list)
      for i, n in enumerate(nums):
         pos[n].append(i)
      q = deque([(0, 0)])
      n = len(nums)
      visited = [False] * n
      visited[0] = True
      while q:
         u, d = q.popleft()
         if u == n - 1:
            return d
         for v in pos[nums[u]] + [u - 1, u + 1]:
            if 0 <= v < n and not visited[v]:
               visited[v] = True
               q.append((v, d + 1))
         del pos[nums[u]]
ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))