我得到一个整数数组,其值大于或等于 0,例如: [5, 6, 0, 4, 2, 4, 1, 0, 0, 4]
我被要求实现一种算法,从索引 0 开始以最短的“跳数”遍历数组,其中遍历定义如下:
->从数组的第一个(第 0 个)索引开始,查看那里的数组值,您可以向前跳到不超过该值的任何数组索引。因此,在此示例中,您从包含值 5 的索引 0 开始,现在可以考虑跳转到索引 1 到 5 中的任何一个。
如果我选择跳到索引 3,它包含值 4,接下来我可以从当前索引 (3) 跳到最多 4 个点——所以我现在将索引 4 到 7 视为序列中的后续步骤。
我的算法必须确定一个最小跳数的解决方案,但可以在具有相同跳数的解决方案中任意选择。
对于这个例子,以下是有效的输出:
0, 5, 9, 出
这是我的实现:
public class ArrayJumper {
/**
* @param args the command line arguments
*/
int[] minJumps(int arr[], int n) {
int jumps[] = new int[n];
int tab[] = new int[n];// jumps[n-1] will hold the result
int i, j;
jumps[0] = 0;
tab[0] = 0;
if (n == 0 || arr[0] == 0) {
return jumps;
}
// Find the minimum number of jumps to reach arr[i]
// from arr[0], and assign this value to jumps[i]
for (i = 1; i < n; i++) {
jumps[i] = Integer.MAX_VALUE;
for (j = 0; j < i; j++) {
if (i <= j + arr[j] && jumps[j] != Integer.MAX_VALUE) {
if (jumps[i] >= jumps[j] + 1) {
jumps[i] = jumps[j] + 1;
tab[i] = j;
//break;
}
}
}
}
System.out.println(Arrays.toString(jumps));
return tab;
}
public static void main(String[] args) {
// TODO code application logic here
int arr[] = {5, 6, 0, 4, 2, 4, 1, 0, 0, 4};
//int arr[] = {2,3,1,1,2,4,2,0,1,1};
int n = arr.length;
int res[] = new int[n];
int inn[] = new int[n];
ArrayJumper a = new ArrayJumper();
inn = a.minJumps(arr, n);
System.out.println(Arrays.toString(inn));
inn[0] = 0;
String ans = " 0 ,";
for (int i = 0; i < n - 1; i++) {
if (inn[i] != inn[i + 1]) {
ans = ans.concat(inn[i + 1] + ",");
}
}
if (arr[inn[n - 1]] + inn[n - 1] == n - 1) {
ans = ans.concat(n - 1 + ",");
}
ans = ans.concat("out");
System.out.println(ans);
}
}
但是该解决方案适用于给定的输入,它对以下输出无效: {2,3,1,1,2,4,2,0,1,1}; 我不确定我错过了什么。如果我分别更改 break 语句,则注释输入都可以正常工作。 那么我该如何修改这个程序来获得
0,1,4,5,9,out 用于输入 {2,3,1,1,2,4,2,0,1,1}。
和 0, 5, 9, out 用于输入 {5, 6, 0, 4, 2, 4, 1, 0, 0, 4}
最佳答案
我相信您的 minJumps()
工作正常。您的问题在于答案的构造,ans
字符串。
我不明白您尝试这样做的逻辑。我相信你需要从“out”向后构建字符串。当 inn[3]
等于 2 时,这意味着如果您的解决方案通过输入的索引 3,它应该在 3 之前通过索引 2。但是您没有还不知道解决方案是否会跳过索引 3。
所以要反向构建它,你从“out”开始,“out”之前是什么?为了告诉你,你需要让结果数组长一个元素,这样新的最后一个元素告诉你在“out”之前要访问的最后一个索引。然后你可以这样做:
String ans = "out";
int index = n;
while (index > 0) {
index = inn[index];
ans = "" + index + ", " + ans;
}
System.out.println(ans);
要构建更长一个元素的数组,只需对您的方法进行一些简单的更改:
int jumps[] = new int[n + 1];
int tab[] = new int[n + 1];// jumps[n-1] will hold the result
和
for (i = 1; i <= n; i++) {
通过这些更改,输入 {5, 6, 0, 4, 2, 4, 1, 0, 0, 4} 产量
0, 5, 9, out
输入 {2,3,1,1,2,4,2,0,1,1} 给出
0, 1, 4, 5, 9, out
关于java - 打印到达数组末尾所需的最小跳转数序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41183096/