阿里笔试的一道算法题题目：获取一个正整数数组的最优跳动方式，要求如下:
1）从数组中间的任意位置开始向右跳，每次跳动的步伐数不能超过该位置对应元素的值
2）在跳动次数最少的情况下计算每次跳动的步伐
以下是实现，采用Java实现~
package test;
/**
*为静态工具类，具体功能见方法
* @author ZOUHENG
*/
public class MinStepToArrayEnd {
/**
* 根据当前位置的跳动范围返回一个最优的位置，该位置使得连续两次跳动可获得最远距离 如果当前位置可以直接跳出数组范围，则最有位置为当前位置
* 这里默认传入的参数已经经过验证，满足要求
*
* @param target
* 目标数组
* @param currentLocation
* 当前位置,对应元素的从左到右的排列位置，第一个元素为1，最后一个元素为数组长度
* @return 最优秀位置
*/
private static int getBestLocation(int[] target, int currentLocation) {
// 初始化二连跳的最远位置，可以超出数组范围
int maxLocation = currentLocation + target[currentLocation - 1];
// 初始化当前位置
int bestLocation = currentLocation;
// 遍历当前位置覆盖的元素，获得二连跳的最远位置和对应的最优位置
for (int i = 0; i <= target[currentLocation - 1]; i++) {
int temp = target[(i + currentLocation) - 1] + (i + currentLocation);
if (temp >= target.length) {
return i + currentLocation;
}
if (temp > maxLocation) {
maxLocation = temp;
bestLocation = i + currentLocation;
}
}
return bestLocation;
}
/**
* 根据最佳位置与当前位置计算调动的步伐数量
*
* @param target
* @param currentLocation
* @return
*/
private static int getJumpSteps(int[] target, int currentLocation) {
int bestLocation = getBestLocation(target, currentLocation);
// 如果最佳位置与当前位置相等，则说明可以直接从当前位置跳到末端，因此直接返回剩下的步伐
if (bestLocation == currentLocation) {
return target.length - currentLocation;
}
// 如果不等，则返回最佳位置与当前位置的步伐差
return bestLocation - currentLocation;
}
/**
* 获取一个正整数数组的最优跳动方式，要求如下:
* 从数组中间的任意位置开始向右跳，每次跳动的步伐数不能超过该位置对应元素的值
* 在跳动次数最少的情况下计算每次跳动的步伐
*
* @param target
* @param currentLocation
* @return
* @throws Exception
*
*/
public static String getStepsResult(int[] target, int currentLocation) throws Exception {
if (null == target || target.length == 0)
throw new CheckParamException("数组参数为空或未初始化,请检查······");
for (int i : target)
if (i < 1)
throw new CheckParamException("数组成员包含小于非正整数");
if (currentLocation < 1 || currentLocation > target.length)
throw new CheckParamException("开始位置参数不正确，必须大于等于1并且小于等于" + target.length);
String result = "";
int jumpSteps = getJumpSteps(target, currentLocation);
while (jumpSteps + currentLocation != target.length) {
result += jumpSteps + ",";
currentLocation = getBestLocation(target, currentLocation);
jumpSteps = getJumpSteps(target, currentLocation);
}
return result + jumpSteps;
}