面试之谜：跳跃比赛 [英] Interview puzzle: Jump Game

问题描述

跳跃比赛： 给定的阵列，从第一个元素开始并到达最后通过跳跃。跳跃长度可以最多的值在阵列中的当前位置。当你达到跳跃的最低数量目标的最佳结果。

Jump Game: Given an array, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. The optimum result is when you reach the goal in minimum number of jumps.

什么是算法寻找最佳的结果？

What is an algorithm for finding the optimum result?

一个例子：给定数组A = {2,3,1,1,4}可能到达终点（索引表）方式是

An example: given array A = {2,3,1,1,4} the possible ways to reach the end (index list) are

1. 在0,2,3,4（跳到2索引2，然后跳到1至索引3，然后1到索引4）
2. 在0,1,4（跳到1索引1，然后跳转至3索引4）

由于第二溶液只有两个跳跃它是最佳的结果。

Since second solution has only 2 jumps it is the optimum result.

推荐答案

由于阵列 A 和你的当前位置的指数我，重复以下，直到你到达最后元素。

Overview

Given your array a and the index of your current position i, repeat the following until you reach the last element.

考虑所有候选人跳到元素，在 A [1 + 1] 到 A [A [1] + 1] 。对于索引每个这样的元素电子，计算 v = A [E] + 电子。如果这些元素中的一个是最后一个元素，则跳转到最后一个元素。否则，跳到元素的最大 v 。

Consider all candidate "jump-to elements" in a[i+1] to a[a[i] + i]. For each such element at index e, calculate v = a[e] + e. If one of the elements is the last element, jump to the last element. Otherwise, jump to the element with the maximal v.

更简单地说，触手可及的元素，寻找一个将让你最远的的下一步的跳跃。我们知道这个选择， X ，是正确的，因为相比于所有其他元素是，你可以跳转到时，元素到达从是可达元素从的X 的一个子集（除了从一个落后的跳跃的元素，这是显然糟糕的选择）。

More simply put, of the elements within reach, look for the one that will get you furthest on the next jump. We know this selection, x, is the right one because compared to every other element y you can jump to, the elements reachable from y are a subset of the elements reachable from x (except for elements from a backward jump, which are obviously bad choices).

该算法在O（n）的运行，因为每个元素只需进行一次审议（内容将被视为第二次可省略）。

This algorithm runs in O(n) because each element need be considered only once (elements that would be considered a second time can be skipped).

考虑值的数组 A ，indicies，我，和索引和值<$ C $的款项C> v 。

Consider the array of values a, indicies, i, and sums of index and value v.

i ->  0   1   2   3   4   5   6   7   8   9  10  11  12
a -> [4, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
v ->  4  12   3   4   5   6   7   8   9  10  11  12  13

开始指数0，并考虑接下来的4个元素。找到一个与最大 v 。该元素的索引为1，所以跳到1。现在考虑下11元。我们的目标是可以实现的，所以跳的目标。

Start at index 0 and consider the next 4 elements. Find the one with maximal v. That element is at index 1, so jump to 1. Now consider the next 11 elements. The goal is within reach, so jump to the goal.

在这里看到 或这里与code 。

这篇关于面试之谜：跳跃比赛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！