在Python中查找到达最后一个索引所需的最少步数的程序

在Python中查找到达最后一个索引所需的最少步数的程序

假设我们有一个名为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:=一个空映射
  • 对于nums中的每个索引i和值n,执行以下操作
    • 将i插入pos [n]的末尾
  • n:= nums的大小
  • visited:=制作大小为n的列表并将其填充为False
  • visited [0]:= True
  • while q不为空,执行以下操作
    • (u,d):= q的左元素,并删除左元素
    • 如果u与n-1相同,则
      • 返回d
    • 对于pos [nums [u]]和[u-1,u + 1]列表中的每个v,执行以下操作
      • 如果0 <=v
      • visited [v]:= True
      • 在q的末尾插入一对(v,d + 1)
  • 删除pos [nums [u]]

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

更多Python相关文章,请阅读:Python 教程

示例

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教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程