例如: 4 2 2 1 0 2 返回 false
2 1 3 1 1 0 返回 true
bool jump(int array[], int size) { }
public class Item05 { public static boolean flag = false; //标志位 /** * 递归实现 * @param array 台阶数组 * @param position 当前台阶位置 */ public static void jump(int[] array, int position) { int steps = array[position]; //可以到达的台阶数 //从1到step循环,i为跳的阶数 for (int i = 1; i <= steps; i++) { if (position + i == array.length - 1){ flag = true; return ; }else jump(array, position + i); } } public static void main(String[] args) { int[] arrays = { 2, 1, 3, 1, 1, 0 }; jump(arrays, 0); System.out.println(flag); } }
def canJump(self, nums): maxStep=nums[0] for i in range(1,len(nums)): if maxStep==0: return False maxStep-=1 if maxStep<nums[i]: maxStep=nums[i] return True
// 从后向前 逐个判断 用到标志位 【比较好理解】 #include <iostream> using namespace std; #include <vector> bool jump(int array[], int size) { bool can = false; vector<bool> is(size, false); is[size - 1] = true; for (int i = size - 2; i >= 0; i--) { for (int j =1; j <= array[i]; j++) { if (i + j <= size - 1) { if (is[i + j] == true) { is[i] = true; break; } } } if (i == 0 && is[i] == true) { can = true; } } return can; } void test_jump() { int arr1[6] = {4 ,2, 2 ,1, 0, 2}; int arr2[6] = {2 ,1 ,3 ,1 ,1 ,0}; cout<<jump(arr1,6)<<endl; cout<<jump(arr2,6)<<endl; } int main() { test_jump(); return 0; }
//时间复杂度: o(n)~o(n^2) //空间复杂度:o(n); #include<stdio.h> #include<malloc.h> int jump(int arr[], int size) { int *p_flag = NULL; int i, j; if (NULL == arr || 0 >= size) return 0; else if (1 == size) return 1; p_flag = (int*)malloc(sizeof(int)*size); //对应第i个台阶的flag,若为1则表示可以到达,0则不可以 memset(p_flag, 0, sizeof(int)*size); if (arr[0] <= 0) return 0; for (i = 1; i <= arr[0]; i++) p_flag[i] = 1; for (i = 1; i < size; i++) { //台阶从第1个开始,如果当前这个台阶i可以到达,当前台阶最大可向前走arr[i]步, //置标志位,使台阶第 i+1 到 i + arr[i] 台阶标志位都为1; if (1 == p_flag[i]) { // 注意条件 i + j < size 避免溢出 for (j = 1; j <= arr[i] && i + j < size; j++) { p_flag[i + j] = 1; } //可能存在中间第i个台阶就可以直接跳arr[i]步,直接到最后一个台阶,此时可提前结束判断。 if (1 == p_flag[size - 1]) return 1; } } return p_flag[size - 1];//返回最后一个台阶标志 } int main() { int arr[2][20] = { { 4, 2, 2, 1, 0, 2 } , { 2, 1, 3, 1, 1, 0 } }; printf("arr0: %d\n", jump(&arr[0][0], 6)); printf("arr1: %d\n", jump(&arr[1][0], 6)); return 0; }
这道题我考虑用递归的方法解题。 package zhang;
//4 2 2 1 0 2 返回 false
//2 1 3 1 1 0 返回 true
public class Step {
private boolean flag=false;//设置标志位
public static void main(String[] args)
{
int [] ladder={2,1,3,1,1,0};
Step step=new Step();
step.stepLadder(ladder, 0);
if(step.flag)
System.out.println("可以到达!");
else
System.out.println("无法到达!");
}
public void stepLadder(int [] ladder,int start)
{
int i;
for(i=start;i<=ladder.length-1;i++)
{
if((ladder[start]==0)||(start+ladder[start]>ladder.length-1))
break;
if(start+ladder[start]==ladder.length-1)
flag=true;
else
stepLadder(ladder,start+ladder[start]);
}
}
}从数组第一个开始跳,下次跳的位置为本次的开始位置加上跳的步数(题目只是说了最大步数,不一定非得跳最大步数)start+ladder[start],那么从ladder[start]往后的数组又是一个跳台阶问题,可以考虑用递归
static boolean jump(int array[], int size) { boolean []boolArr = new boolean[size]; return isJump(array, boolArr, 0, size); } private static boolean isJump(int[] arr, boolean[] boolArr, int i, int size) { // TODO Auto-generated method stub if (i == size - 1) return true; if (arr[i] == 0) { boolArr[i] = false; } boolean isNextStepOk = isJump(arr, boolArr, i + 1, size); if (isNextStepOk) { boolArr[i] = true; } if ((isNextStepOk && arr[i] > 0 ) || size - i - 1 <= arr[i]) return true; for (int k = i + 2; k < i + arr[i]; k++) { if (boolArr[k] == true)return true; } return false; }
public class CanReachTop { private boolean canReach(int i, boolean[][] w) { if (i == 0) return true; boolean rst = false; for (int j = 0; j < i; j++) { rst = rst || w[j][i]; } return rst; } public boolean jump(int array[], int size) { int n = array.length; boolean[][] w = new boolean[n][n]; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (canReach(i, w)) { if (j - i <= array[i]) { w[i][j] = true; if (j == n - 1) return true; } } } } return false; } public static void main(String[] args) { CanReachTop canReachTop = new CanReachTop(); int[] a = {4, 2, 2, 1, 0, 2}; System.out.println(canReachTop.jump(a, 3)); } }
bool jump(int array[], int size) { if(array == NULL || size <= 0) { cout<<"输入有误..."<<endl; return false; } bool isLastOne = false; int i=0; while(i < size-1) { if(array[i] == 0) { isLastOne = false; break; } i += array[i]; } if( i == size-1) isLastOne=true; return isLastOne; }