第20天--算法（Leetcode 45,46,55）
45.跳跃游戏2
public int jump(int[] nums) {
if(nums == null || nums.length < 1) {
return 0;
}
int step = 0;
int cur = 0;
int next = nums[0];
for(int i = 1;i < nums.length;i ++) {
if(next >= nums.length - 1) {
step ++;
break;
}
if(i > cur) {
step ++;
cur = next;
}
next = Math.max(i + nums[i],next);
}
return step;
}
46.全排列
public List> permute(int[] nums) {
List> res = new ArrayList<>();
process(res,nums,0);
return res;
}
public void process(List> res,int nums[],int index) {
if(index == nums.length) {
List cur = new ArrayList<>();
for(int num : nums) {
cur.add(num);
}
res.add(cur);
}else {
for(int j = index;j < nums.length;j ++) {
swap(nums,index,j);
process(res,nums,index + 1);
swap(nums,index,j);
}
}
}
public void swap(int arr[],int x,int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
55.跳跃游戏
public boolean canJump(int[] nums) {
int N = nums.length;
int max = nums[0];
for(int i = 1;i < nums.length;i ++) {
if(max < i) {
return false;
}
if(max >= nums.length - 1) {
return true;
}
max = Math.max(max,i + nums[i]);
}
return true;
}