12个回答
30
该网站提出的解决方案的时间复杂度是线性的，因为你只需要遍历一次数组。算法通过使用一些巧妙的技巧避免了我提出的解决方案中的内部循环。
变量maxReach始终存储数组中可达到的最大位置。jump存储到达该位置所需的跳跃次数。step存储我们仍然可以走的步数（并在第一个数组位置处初始化步数）
在迭代过程中，上述值按以下方式更新：
首先，我们测试是否已经到达数组的末尾，在这种情况下，我们只需要返回jump变量。
接下来，我们更新可达到的最大位置。这等于maxReach和i+A[i]（从当前位置可以走的步数）的最大值。
我们用一步走到当前索引，因此必须减少steps。
如果没有剩余的步数（即steps=0），那么我们必须使用一次跳跃。因此要增加jump。由于我们知道从位置i到达maxReach是可能的，因此我们将步数初始化为到达maxReach所需的步数。
public class Solution {
public int jump(int[] A) {
if (A.length <= 1)
return 0;
int maxReach = A[0];
int step = A[0];
int jump = 1;
for (int i = 1; i < A.length; i++) {
if (i == A.length - 1)
return jump;
if (i + A[i] > maxReach)
maxReach = i + A[i];
step--;
if (step == 0) {
jump++;
step = maxReach - i;
}
}
return jump;
}
}
例子：
int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0]; // A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0]; // A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1; // we will always need to take at least one jump.
/*************************************
* First iteration (i=1)
************************************/
if (i + A[i] > maxReach) // 1+3 > 1, we can reach further now!
maxReach = i + A[i] // maxReach = 4, we now know that index 4 is the largest index we can reach.
step-- // we used a step to get to this index position, so we decrease it
if (step == 0) {
++jump; // we ran out of steps, this means that we have made a jump
// this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
// but we can continue with the 3 steps received at array position 2.
steps = maxReach-i // we know that by some combination of 2 jumps, we can reach position 4.
// therefore in the current situation, we can minimaly take 3
// more steps to reach position 4 => step = 3
}
/*************************************
* Second iteration (i=2)
************************************/
if (i + A[i] > maxReach) // 2+5 > 4, we can reach further now!
maxReach = i + A[i] // maxReach = 7, we now know that index 7 is the largest index we can reach.
step-- // we used a step so now step = 2
if (step==0){
// step
}
/*************************************
* Second iteration (i=3)
************************************/
if (i + A[i] > maxReach) // 3+8 > 7, we can reach further now!
maxReach = i + A[i] // maxReach = 11, we now know that index 11 is the largest index we can reach.
step-- // we used a step so now step = 1
if (step==0){
// step
}
/*************************************
* Third iteration (i=4)
************************************/
if (i + A[i] > maxReach) // 4+9 > 11, we can reach further now!
maxReach = i + A[i] // maxReach = 13, we now know that index 13 is the largest index we can reach.
step-- // we used a step so now step = 0
if (step == 0) {
++jump; // we ran out of steps, this means that we have made a jump.
// jump is now equal to 3.
steps = maxReach-i // there exists a combination of jumps to reach index 13, so
// we still have a budget of 9 steps
}
/************************************
* remaining iterations
***********************************
// nothing much changes now until we reach the end of the array.
我的次优算法在 O(nk) 时间内运行，其中n为数组中元素的数量，k为数组中最大的元素，并使用对 array[i] 进行内部循环。下面的算法避免了这个循环。
代码
public static int minimum_steps(int[] array) {
int[] min_to_end = new int[array.length];
for (int i = array.length - 2; i >= 0; --i) {
if (array[i] <= 0)
min_to_end[i] = Integer.MAX_VALUE;
else {
int minimum = Integer.MAX_VALUE;
for (int k = 1; k <= array[i]; ++k) {
if (i + k < array.length)
minimum = Math.min(min_to_end[i+k], minimum);
else
break;
}
min_to_end[i] = minimum + 1;
}
}
return min_to_end[0];
}
- Niels Billen
9
2为什么这是线性时间的？ - Codor
1我认为这不是线性时间。需要一个线性时间的解决方案。 - Walt
1谢谢你抽出时间回复。没必要道歉 :). 如果你对线性时间解决方案有任何想法，请告诉我。我分享的LeetCode链接声称有线性时间解决方案。只是我无法理解它。你能否请看一下？ - Walt
感谢您抽出时间来做这件事。 当您说step=最大步骤数时，我仍然不明白存储哪个步骤...... 一个例子会有所帮助 :( .. 再次感谢并对我的愚蠢表示歉意。 - Walt
1@NielsBillen - 函数
jump 从不失败（例如：A[] = {0,1} 和 A[]={1,3,1,0,0,0,0,1}，根据问题描述应该会失败）。你是否应该在循环开始时添加一个条件：if (steps == 0) return INT_MAX;，并在函数末尾添加一个返回（虽然你永远不应该到达那里）：return INT_MAX;？谢谢！ - Captain Crunch显示剩余4条评论
7
以下是上述问题贪心方法的基本思路，其余为代码要求。
给定数组输入：a[]={1,3,5,8,9,2,6,7,6,8,9}。
现在我们从第一个元素开始，即i=0且a[i]=1。因此，我们最多可以跳一步，所以既然没有其他选择，我们就采取这个步骤。
目前我们在i=1处，a[i]=3。所以我们当前可以跳3步，但是我们考虑从当前位置开始可能的所有跳跃，并达到范围内的最大距离。那么我们有什么选择呢？我们可以跳1步、2步或3步。因此，我们对每个大小的跳跃进行调查，选择可以将我们带入数组更远的那个跳跃。
一旦我们决定了哪一个跳跃，我们就采取那个跳跃大小并更新我们迄今为止所做的跳跃次数，以及我们可以到达的最远距离以及我们现在必须决定下一步应采取的步数。就这样。这就是我们如何通过线性遍历数组来选择最佳选项的方式。
这就是你可能正在寻找的算法的基本思路，接下来是编写算法使其正常工作。干杯！
希望有人穿越时空，发现这个直觉很有用！:) :P“晚了好几年”@Vasilescu Andrei - 说得好。有时候我觉得我们就像穿越者一样。
给定数组输入：a[]={1,3,5,8,9,2,6,7,6,8,9}。
现在我们从第一个元素开始，即i=0且a[i]=1。因此，我们最多可以跳一步，所以既然没有其他选择，我们就采取这个步骤。
目前我们在i=1处，a[i]=3。所以我们当前可以跳3步，但是我们考虑从当前位置开始可能的所有跳跃，并达到范围内的最大距离。那么我们有什么选择呢？我们可以跳1步、2步或3步。因此，我们对每个大小的跳跃进行调查，选择可以将我们带入数组更远的那个跳跃。
一旦我们决定了哪一个跳跃，我们就采取那个跳跃大小并更新我们迄今为止所做的跳跃次数，以及我们可以到达的最远距离以及我们现在必须决定下一步应采取的步数。就这样。这就是我们如何通过线性遍历数组来选择最佳选项的方式。
这就是你可能正在寻找的算法的基本思路，接下来是编写算法使其正常工作。干杯！
希望有人穿越时空，发现这个直觉很有用！:) :P“晚了好几年”@Vasilescu Andrei - 说得好。有时候我觉得我们就像穿越者一样。
- Sid Ray
1
非常好的解释。 - ashutosh tiwari
3
这里已经有一些非常好的答案，但我感觉我可以帮助解释算法为什么正确以及背后的直觉。我喜欢这个问题，因为直观的动态规划方法在最坏情况下的时间复杂度为O(n²)，而贪心方法（激发了这个问题的方法）在最坏情况下的时间复杂度为O(n)（它实际上只访问数组的每个元素一次）。对我来说，这个算法有点像Dijkstra算法，它解决了另一个单源最短路径问题，也是贪心算法。
首先，请记住从问题陈述中得出的结论：A[i]表示从该索引处跳跃到的最大位置，但如果A[i]>1，则可以从i处进行较小的跳跃，因此从i=0开始的跳跃序列可以是使用比每个索引允许的更小的跳跃。这很重要，因为您将看到该算法从未明确考虑过那些更小的跳跃或它们的位置。
其次，有助于将你提到的算法看作是给自己“绳索的绳索”（steps = maxReach - i;）以到达末尾，并在尝试穿过数组时消耗这个绳索（steps--;）。
第三，注意该算法没有跟踪可能是从开始到输入数组A结尾的最短序列中的特定索引i。实际上，只有当它“用完了绳索”（从前一个绳索）时，它才增加变量jump（给自己一根新的绳索），以便可以在主循环中继续迭代以“尝试”到达末尾。
具体来说，为了使算法正确，它需要：
记录从每个位置i出发可以到达的最远距离
maxReach。需要注意的是，即使此时已经明确了到达新位置将需要更多的“跳跃”，因为超过了之前给自己的步数（也就是用尽了绳子），甚至没有最短路径实际上访问该元素，这个量对于每个位置都要更新。这些更新的目的是确定下一次跳跃可以到达的距离，以便在用完当前的绳子后它可以再重新给自己那么长的绳。计算出要继续遍历数组到达末尾时必须采取的最少跳跃次数
jumps，当你从上一个绳索中用尽所有步数steps时要考虑这个数量。
参考算法:
public class Solution {
public int jump(int[] A) {
if (A.length <= 1)
return 0;
int maxReach = A[0];
int step = A[0];
int jump = 1;
for (int i = 1; i < A.length; i++) {
if (i == A.length - 1)
return jump;
if (i + A[i] > maxReach)
maxReach = i + A[i];
step--;
if (step == 0) {
jump++;
step = maxReach - i;
}
}
return jump;
}
}
- Amelio Vazquez-Reina
1
1我有一个问题。在这个问题中，与其他动态规划问题相比，我们如何知道我们可以使用贪心方法？我理解解决方案，但是我很难理解为什么它有效，因为大多数此类最大化或最小化问题通常通过dp最优地解决。另外，在每次迭代中，为什么我们不能在发现当前步骤不足以到达maxreach时立即更新步骤。为什么要等待步骤变为0？ - Ak01
2
虽然来晚了几年，但这里还是有另一个O(n)解决方案，对我来说很有意义。
/// <summary>
///
/// The actual problem is if it's worth not to jump to the rightmost in order to land on a value that pushes us further than if we jumped on the rightmost.
///
/// However , if we approach the problem from the end, we go end to start,always jumping to the leftmost
///
/// with this approach , these is no point in not jumping to the leftmost from end to start , because leftmost will always be the index that has the leftmost leftmost :) , so always choosing leftmost is the fastest way to reach start
///
/// </summary>
/// <param name="arr"></param>
static void Jumps (int[] arr)
{
var LeftMostReacher = new int[arr.Length];
//let's see , for each element , how far back can it be reached from
LeftMostReacher[0] = -1; //the leftmost reacher of 0 is -1
var unReachableIndex = 1; //this is the first index that hasn't been reached by anyone yet
//we use this unReachableIndex var so each index's leftmost reacher is the first that was able to jump to it . Once flagged by the first reacher , new reachers can't be the leftmost anymore so they check starting from unReachableIndex
// this design insures that the inner loop never flags the same index twice , so the runtime of these two loops together is O(n)
for (int i = 0; i < arr.Length; i++)
{
int maxReach = i + arr[i];
for (; unReachableIndex <= maxReach && unReachableIndex < arr.Length; unReachableIndex++)
{
LeftMostReacher[unReachableIndex] = i;
}
}
// we just go back from the end and then reverse the path
int index = LeftMostReacher.Length - 1;
var st = new Stack<int>();
while (index != -1)
{
st.Push(index);
index = LeftMostReacher[index];
}
while (st.Count != 0)
{
Console.Write(arr[st.Pop()] + " ");
}
Console.WriteLine();
}
static void Main ()
{
var nrs = new[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
Jumps(nrs);
}
- Vasilescu Andrei
2
最少跳几次才能到达终点的问题的简单 Python 代码。
ar=[1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
minJumpIdx=0
res=[0]*len(ar)
i=1
while(i<len(ar) and i>minJumpIdx):
if minJumpIdx+ar[minJumpIdx]>=i:
res[i]=res[minJumpIdx]+1
i+=1
else:
minJumpIdx+=1
if res[-1]==0:
print(-1)
else:
print(res[-1])
- Vishwanath Hiremath
1
这里有另一种线性解决方案。代码长度比leet code链接中建议的长，但我认为它更易于理解。它基于两个观察结果：到达
i + 1位置所需的步骤数永远不少于到达i位置所需的步骤数，并且每个元素将其值+1分配给i + 1 ... i + a[i]段。public class Solution {
public int jump(int[] a) {
int n = a.length;
// count[i] is the number of "open" segments with value i
int[] count = new int[n];
// the number of steps to reach the i-th position
int[] dp = new int[n];
Arrays.fill(dp, n);
// toDelete[i] is the list of values of segments
// that close in the i-th position
ArrayList<Integer>[] toDelete = new ArrayList[n];
for (int i = 0; i < n; i++)
toDelete[i] = new ArrayList<>();
// Initially, the value is 0(for the first element).
toDelete[0].add(0);
int min = 0;
count[0]++;
for (int i = 0; i < n; i++) {
// Finds the new minimum. It uses the fact that it cannot decrease.
while (min < n && count[min] == 0)
min++;
// If min == n, then there is no path. So we can stop.
if (min == n)
break;
dp[i] = min;
if (dp[i] + 1 < n) {
// Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
count[dp[i] + 1]++;
if (i + a[i] < n)
toDelete[i + a[i]].add(dp[i] + 1);
}
// Processes closing segments in this position.
for (int deleted : toDelete[i])
count[deleted]--;
}
return dp[n - 1];
}
}
复杂度分析:
toDelete列表中的所有元素总数是O(n)。这是因为在每个位置i最多只添加一个元素。因此，处理所有toDelete列表中的元素需要线性时间。min值只能增加。因此，内部的while循环总共最多进行n次迭代。外部的
for循环显然进行n次迭代。因此，时间复杂度是线性的。
- kraskevich
4
1非常感谢。您能否为代码和时间复杂度提供更多的解释？当您说“到达i + 1位置所需的步骤数永远不少于到达i位置所需的步骤数”时，您的意思是从特定位置j到达i+1的步骤数始终小于到达i的步骤数，对吗？ - Walt
@Walt 关于步骤数量：这意味着对于所有的
i，都有 dp[i] <= dp[i + 1]。 - kraskevich非常感谢@ILoveCoding添加了复杂性分析。但是我还无法理解算法。 :( 如果您能在那里添加一些注释，或者说明它的工作原理，那就太好了。 - Walt
@Walt 让我们回忆一下一个天真的解决方案：对于每个i，迭代j = i + 1 ... i + a[i]：dp[j] = min(dp[j]，dp[i] + 1)。因此它创建了一个带有dp[i] + 1值的段[i + 1，i + a[i]]。与其以这种方式迭代，我们可以维护一组“打开”的段及其值（打开意味着k + 1 <= i <= k + a[k]）。 - kraskevich
1
好的，我花了很多时间来理解O(n)算法，我将尝试用最简单的方式解释逻辑：
在数组中的每个“i”处，您知道该值是当前可达到的最远值，还知道当前结束值。当您到达当前结束值时，就知道是时候跳跃并使用当前可达到的最远值来更新当前结束值。
下面的图片可能有所帮助：
- fight_club
1
我已经用Python完成了这个任务。使用简单术语编写的代码更加简洁。这可能会对你有所帮助。
def minJump(a):
end=len(a)
count=0
i=a[0]
tempList1=a
while(i<=end):
if(i==0):
return 0
tempList1=a[count+1:count+i+1]
max_index=a.index(max(tempList1))
count+=1
i=a[max_index]
end=end-max_index
return count+1
- Ishaan Sharma
0
如果你需要为贪心方法编写一个Python解决方案，这段代码将帮助你解决上述问题：）
def minJumps(self, arr, n):
#code here
if(n <= 1):
return(0)
if(arr[0] == 0):
return -1
maxrange, step = arr[0], arr[0]
jumps = 1
for i in range(1,n):
if (i == len(arr) - 1):
return jumps
maxrange = max(maxrange, i+arr[i])
step -= 1
if(step == 0):
jumps += 1
if(i>=maxrange):
return -1
step = maxrange - i
return(jumps)
- Jeevan Lenka
0
这是另一种解决方案。在此解决方案中，最坏情况的复杂度为O(n)，而平均情况的复杂度小于O(n)。我不知道如何进行平均情况复杂度分析，所以无法确定确切的平均情况复杂度。但是，在leet code上，速度比99.22%的提交更快。
def minJumps(self, arr, n):
current_w=0 # current_index
last_w=n-1 # last_index
max_reach=0 # value of index upto which we have analysed array for optimum solution
max_jumps=arr[0] # maximum jumps that can be taken from a current_index
hop=0 # total jumps
while current_w<last_w:
max_jumps=arr[current_w]
if max_jumps==0:
return -1
if max_jumps==1:
max_reach=max_jumps+current_w
current_w+=1
elif max_jumps<last_w-current_w: # if maximum steps does not reach to last index
can_jump_to=arr[max_reach+1:max_jumps+current_w+1] # subarray in which we have to search for a wall,jumping to which can take us to required solution
jump_to=max(range(len(can_jump_to)),key=lambda x: x+can_jump_to[x])+max_reach+1 # finding index of wall whoose definition mentioned in above comment
max_reach=max_jumps+current_w #updating max_reach
current_w=jump_to #updating current position
else:
current_w=last_w
hop+=1
return hop
- Saurav
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接