找终点python

找终点python

 难度指数：⭐⭐⭐⭐

通用一般算法：
python学习一点 快乐一点（4）找终点

def min_step(nums):res = float("inf")len_arr = len(nums)len_step = len(nums)//2+1for  i in range(1,len_step):step = 1 arr_index = iwhile (1):arr_index += int(nums[arr_index])step += 1 if arr_index > len_arr - 1:breakif arr_index == len_arr - 1:res = min(res,step)break        if (res == float("inf")):return -1else:return res

创新算法

idea

普遍算法：

• 遍历所有中位数之前的数，模拟前进。
• 耗时。

idea：

1. 假设存在能到达终点的路径。以终为始，以始为终。终点落在二分之一路径之外。
2. 最后一个途经点需满足数值等于步长（索引之差）。
3. 找出所有满足条件的第一个途经点，而后为单个途经点寻找下一个满足条件的所有途经点，直到途经点满足终点条件，即落在二分之一路径之外。最终得到所有可能的路径，以及最少的步数。

代码实现

def min_step0(nums):N=len(nums)temp=1begin_p=(N-1)//2end_ps=[N-1]while(len(end_ps)):valid=[]for n in end_ps:for i in range(1,n):if (i+nums[i]==n):if i<=begin_p:temp+=1return tempvalid.append(i)temp+=1if len(valid)==0:temp=-1end_ps=valid        return temp

对比验证

耗时对比：

from time import time
T=10
while T:nums=[random.randint(1,100) for _ in range(1,random.randint(1,100))]t1=time()print(min_step(nums))t2=time()print(min_step0(nums))t3=time()print(t2-t1,t3-t2)T-=1

完整代码如下：

import random
def min_step(nums):res = float("inf")len_arr = len(nums)len_step = len(nums)//2+1for  i in range(1,len_step):step = 1 arr_index = iwhile (1):arr_index += int(nums[arr_index])step += 1 if arr_index > len_arr - 1:breakif arr_index == len_arr - 1:res = min(res,step)break        if (res == float("inf")):return -1else:return resdef min_step0(nums):N=len(nums)temp=1begin_p=(N-1)//2end_ps=[N-1]while(len(end_ps)):valid=[]for n in end_ps:for i in range(1,n):if (i+nums[i]==n):if i<=begin_p:temp+=1return tempvalid.append(i)temp+=1if len(valid)==0:temp=-1end_ps=valid        return tempT=10
while T:nums=[random.randint(1,100) for _ in range(1,random.randint(1,100))]print(min_step(nums))print(min_step0(nums))T-=1