問題描述:
給定一個正整數數組,設為nums,最大為100個成員,求從第一個成員開始,正好走到數組最后一個成員,所使用的最少步驟數。要求:
- 第一步必須從第一元素開始,且1<=第一步的步長<len/2;(len為數組的長度,需要自行解析)。
- 從第二步開始,只能以所在成員的數字走相應的步數,不能多也不能少,如果目標不可達返回-1,只輸出最少的步驟數量。
- 只能向數組的尾部走,不能往回走。
輸入描述
由正整數組成的數組,以空格分隔,
數組長度
小于100,請自行解析數據數量。
輸出描述
正整數,表示最少的步數,如果不存在輸出-1
示例1
輸入
7 5 9 4 2 6 8 3 5 4 3 9
輸出
2
說明
第一步:第一個可選步長選擇2,從第一個成員7開始走2步,到達9;第二步:從9開始,經過自身數字9對應的9個成員到最后。
解題思路:
列表模擬:
- 遍歷前n/2個元素
- 對每個元素,下一跳索引 [i+1] = 索引 [i] + 值 [i]
- 判斷是否能剛好到達最后一個元素
循環條件:
- 若當前索引 = 數組長度 - 1,則將當前步數加入ans列表
- 若當前索引 > 數組長度 - 1,則跳出循環
- 否則繼續下一跳
代碼實現:
arr = list(map(int,input().split()))
n = len(arr)
s = int(n/2)
ans = []
for index in range(s):step = 1#記錄次數while index < n:index += arr[index]if index >= n:breakelif index == n-1:ans.append(step+1)step += 1
if len(ans) != 0:ans.sort()print(ans[0])
else:print(-1)