程序查找在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。最后，由于它们的值均为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