376. 摆动序列
首先是对“摆动”的判断,为什么等于号要在同一边,可以在一个平坡中只计算一次左边的平坡到上坡或者下坡,为了避免两端的特殊判断,右端结束算一个坡,所以答案初始是1,在开头加上和第一个元素大小一致的头元素,漏掉了单调中包含平坡误判的情况,因为以下判断方法是每次更新predis,然后判断当前dis,如果是一次摆动就算入,因为考虑到了平坡,虽然只会梯形的平坡算入一次拐点,但是存在单调区间的拐点,也会被算进去,所以如果是在一个单调区间里面,不应该把pre改成0,造成在单调区间里峰值的误判,而是在有峰值的时候,单调的方向真的改变了,才把predis更改正负
(preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)
55. 跳跃游戏
因为可以选择步数范围内跳几步,范围就是i+nums[i],然后进一步更新最大范围
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxx = 0;
for(int i = 0;i<=maxx;i++){
if(maxx>=nums.size()-1) return true;
maxx = max(maxx, i+nums[i]);
}
return false;
}
};
45.跳跃游戏II
这里我自己做的思路和解析有些区别,这里我把return ans 放在i>premax之前,而判断return的时候返回的ans,是通过当前的maxx(也就是下一次跳跃的范围,也就是ans+1的范围)就会导致我刚开始需要ans=1, 这里我代码繁琐的主要问题是没有弄清楚ans对应的当前步数范围,还是下一步数范围
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size()<=1) return 0;
int maxx = 0;
int ans = 1;
int premax = maxx;
for(int i = 0;i<=maxx;i++){
if(maxx>=nums.size()-1) return ans;
if(i>premax){
premax = maxx;
ans++;
}
maxx = max(maxx, i+nums[i]);
}
return ans;
}
};