输出包括两行,第一行一个整数n,代表arr数组长度,第二行n个整数代表数组arr[i]。
输出一个整数,代表最少跳的次数。
6 3 2 3 1 1 4
2
arr[0]==3,选择跳到位置2,arr[2]==3,可以跳到最后的位置。所以返回2。
时间复杂度O(n),额外空间复杂度O(1)
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] strArr = br.readLine().trim().split(" "); int[] arr = new int[n]; for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]); System.out.println(recurrent(arr, n - 1)); } private static int recurrent(int[] arr, int index) { if(index == 0) return 0; int start = index; // 将起点回退到能一步跳到index的最左点,以保证步数最少 for(int i = 0; i < index; i++){ if(index - i <= arr[i]){ // 如果在i处可以一下跳到index处,就把起点往左推 start = Math.min(start, i); } } return 1 + recurrent(arr, start); } }
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; vector<int>arr(n); for(int i=0;i<n;i++) cin>>arr[i]; int jm = 0, cur = 0, next = 0; for(int i=0;i<n;i++) { if(cur<i){ jm++; cur=next; } next=max(next,i+arr[i]); } cout<<jm<<endl; return 0; }
#输入数据 n=int(input()) number_list=list(map(int,input().split())) #答案 ans=0 #新的跳跃步数 new_step=0 #新的当前所在位置 new_index=0 #列表长度 length=len(number_list) #贪心思想,每次都跳跃最大步 #这样能保证总次数最少 for i in range(length): #如果新的当前所在位置 #小于当前列表下标 #证明还没有跳到最后位置 #继续跳跃 if new_index<i: ans+=1 new_index=new_step #每次都选择最大的步数进行跳跃 if new_step<i+number_list[i]: new_step=i+number_list[i] print(ans)
// 虽然把这题放在入门级别, 但还是有点思维难度的 #include <iostream> #include <vector> using namespace std; int main(){ int n; cin>>n; vector<int>v(n); for(int i =0;i<n;++i){ cin>>v[i]; } // 记录当前记录 int cur = 0; // 记录最远记录 int furth = 0; // 记录跳跃步数 int step = 0; for(int i = 0;i<n;++i){ furth = max(furth,v[i]+i); if(furth >= n-1){ cout<<step+1<<endl; break; }else if(i == cur){ step +=1; cur = furth; } } return 0; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); if (n == 0) { System.out.println(0); return; } int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } a[n - 1] = 0; for (int i = n - 2; i >= 0; i--) { int min = Integer.MAX_VALUE; for (int j = 1; j <= a[i] && i + j < n; j++) { min = Math.min(a[i + j], min); } a[i] = min + 1; } System.out.println(a[0]); } }
// 动态规划 import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner in = new Scanner(System.in); int n = Integer.valueOf(in.nextLine().trim()); int []array = new int[n]; String data = in.nextLine(); String[] s = data.split(" "); for (int i = 0; i < n; i++) { array[i] = Integer.valueOf(s[i]); } int []map = new int[n]; for (int i = 0; i < n; i++) { for (int j = i+1; j<n && j <= i+array[i]; j++) { if (map[j] <= 0) { map[j] = map[i]+1; } else { map[j] = map[i]+1 < map[j] ? map[i]+1 : map[j]; } } } System.out.println(map[n-1]); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for(int i=0;i<n;i++){ arr[i] = scanner.nextInt(); } int jump = 0; int curr = 0; int border = 0; for(int i = 0;i<n;i++){ if(curr < i){ jump++; curr = border; } border = Math.max(border,i+arr[i]); } System.out.print(jump); } }
import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); if(n==0){ System.out.println("输入错误"); return; } String[] s=br.readLine().split(" "); int[] arr=new int[n]; for(int i=0;i<n;++i){ arr[i]=Integer.parseInt(s[i]); } int count=jump(arr,n-1); System.out.println(count); } public static int jump(int[] arr,int end){ if(end==0) return 0; int left=end; for(int i=0;i<end;i++){ if(end-i<=arr[i]){ left=Math.min(i,left); } } return 1+jump(arr,left); } }