程序查找在Python中达到最后索引的最小步骤数

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为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。最后，由于它们的值均为5，因此我们可以从索引3跳到6。

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

  • pos：=一个空的映射

  • 对于每个索引i和以数值为单位的值n，

    • 在pos [n]的末尾插入i

  • n：= nums的大小

  • Visited：=列出大小为n的列表，并用False填充

  • 造访过[0]：=真

  • 当q不为空时，执行

    • 如果0 <= v <n且visited [v]为假，则

    • 访问过[v]：=真

    • 在q的末尾插入对（v，d + 1）

    • 返回d

    • (u,d)：= q的左元素，并删除左元素

    • 如果u与n-1相同，则

    • 对于列表pos [nums [u]]和[u-1，u + 1]中的每个v，执行

    • 删除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))

    输入项

    [4, 8, 8, 5, 4, 6, 5]

    输出结果

    3

    以上是 程序查找在Python中达到最后索引的最小步骤数 的全部内容， 来源链接： utcz.com/z/345301.html

    回到顶部