华为机试练习（九）找终点

题目描述 给定一个正整数数组，最大为100个成员，从第一个成员开始，走到数组最后一个成员最少的步骤数。第一步必须从第一元素开始，1<=步长<len/2, 第二步开始以所在成员的数字走相应的步数，如果目标不可达返回-1，只输出最少的步骤数。

样例输入 7 5 9 4 2 6 8 3 5 4 3 9

样例输出 2

说明 第一步走2步（2<len/2），走到9，第二步走9步到底最后一个成员，最少步数两步

【分析】 第一步可以走 [1,len/2) 的任意一种，遍历所有情况，找到符合要求的最小步骤

【实现】

// 输入
const input = "7 5 9 4 2 6 8 3 5 4 3 9"
const arr = input.split(" ").map((x) => parseInt(x, 10))
const len = arr.length

// 记录最小步数
let res = Infinity

// 第一步最多只能走 len/2
const range = len / 2

for (let i = 1; i < range; i++) {
          
   
	// 走的步数
    let count = 1
	// 当前索引
    let index = i
    
    while (1) {
          
   
    	// 向后走 arr[index] 步
        index += arr[index]
        // 步数加1
        count++
        if (index > (len - 1)) {
          
   
        	// 当走的长度超出了范围，说明这种情况不符合要求
            break
        } else if (index === (len - 1)) {
          
   
        	// 刚好走到最后一个成员，更新最小步数
            res = Math.min(res, count)
            break
        }
    }
}

if (res === Infinity) {
          
   
	// 没有符合要求的情况，输出-1
    console.log(-1);
} else {
          
   
    console.log(res)
}

做荣耀笔试题的时候刚好遇到了这道题，当时没来得及细想，只通过了 80%

回头再看发现应该是第 12 行的循环遍历在笔试时写错了，当时想的是从最大步长开始遍历，遇到符合要求的就结束循环并输出，现在想来必须要完整的遍历所有情况，才能找到步长最小的；从最大步长找到的，并不能保证它所用的步数最小！