55. 跳跃游戏
本题不用纠结于可以跳几步,可以聚焦于覆盖范围,即 当前位置+当前跳数 能够覆盖的范围,若这个范围足以到达最后一个位置,则返回true;若for循环结束,则还没返回true,则返回false。 下面看代码:
class Solution {
public boolean canJump(int[] nums) {
if(nums.length == 1) return true;
int cover = 0;
for(int i=0; i<=cover; i++){
cover = Math.max(cover,i+nums[i]);
if(cover >= nums.length-1){
return true;
}
}
return false;
}
}
因为cover是覆盖范围,所以for循环的终止条件是i<=cover,最后一个位置是可以取到的。
45. 跳跃游戏 II
本题为 跳跃游戏I 的升级版,保证可以到达终点的情况下,要求出最短的跳跃次数。
还是仿照 跳跃游戏I 的思路,定义一个cover 用于记录最大覆盖范围,终止条件是: cover >= nums.size()-1 ,还要定义一个变量 largest 用于记录当前最远覆盖范围的下标,当i遍历到 largest 时,就要开始新的一步,即ans++。
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) return 0;
int cover = 0;
int ans = 0;
int largest = 0;
for(int i=0; i<nums.length; i++){
cover = Math.max(cover , nums[i]+i);//最大覆盖范围
if(cover >= nums.length-1){ //终止条件
return ans+1;
}
if(largest == i){ //需要开始新的一步
ans++;
largest = cover;
}
}
return ans+1;
}
}
455. 分发饼干
优先将大饼干喂给胃口大的,尽可能先把大胃口的孩子满足,此时for循环需要遍历胃口。 下面看代码:
class Solution {
public int findContentChildren(int[] g, int[] s) {
int ans = 0;
int j = s.length-1;
Arrays.sort(g);
Arrays.sort(s);
for(int i=g.length-1; i>=0; i--){
//没有越界 且 饼干尺寸大于胃口
if(j>=0 && s[j]>=g[i]){
ans++;
j--;
}
}
return ans;
}
}