55. 跳跃游戏

题目

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

C++

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <mutex>
#include <thread>
#include <algorithm>
using namespace std;int main(){printf("n:");int n;scanf("%d",&n);vector<int> nums(n);for(int i=0;i<n;i++){printf("n%d:",i+1);int temp;scanf("%d",&temp);nums[i]=temp;}int length=nums.size();int distance=0;for( int i=0;i<length;i++  ){int len=nums[i];if( i<=distance  ){distance=max(distance,i+len);if( distance>=length ){printf("true");}}}return 0;
}

时间复杂度

$O(N)$

空间复杂度

$O(1)$

Java

import java.util.Scanner;
import java.util.Vector;
import java.lang.Math;public class java55{public static void main(String [] args){Scanner s=new Scanner(System.in);System.out.print("n:");int n=s.nextInt();Vector<Integer> nums=new Vector<Integer>(n);	for( int i=0;i<n;i++  ){System.out.print("n"+(i+1)+":");int temp=s.nextInt();nums.add(temp);}int length=nums.size();int distance=0;for( int i=0;i<length;i++  ){int len=nums.get(i);if( i<=distance  ){distance=Math.max(distance,i+len);if( distance>=length  ){System.out.println("true");}}}	}
}

时间复杂度

$O(N)$

空间复杂度

$O(1)$

Python

print("n:");
n=int(input());
nums=[0 for _ in range(n)];
for i in range(n):print("n"+str(i+1)+":");temp=int(input());nums[i]=temp;
profit=0;
cost=float('inf');
for i in range(n):price=nums[i];if price<cost:cost=price;temp=price-cost;if temp>profit:profit=temp;
print("Result:"+str(profit));

时间复杂度

$O(N)$

空间复杂度

$O(1)$