跳转至

Day27 | Part2

约 364 个字 25 行代码 预计阅读时间 2 分钟

122.买卖股票的最佳时机II

只有一只股票 & 只有买或卖 → 把利润分为每天为单位的维度, 收集每天的正利润即可, 图示

  • 局部最优：收集每天的正利润; 全局最优：求得最大利润

1
2
3
4
5
6
int maxProfit(vector<int>& prices) {
    int res = 0;
    for(int i = 1; i < prices.size(); i ++)
        res += max(prices[i] - prices[i - 1], 0);
    return res;
}
也可以利用动态规划

55.跳跃游戏

跳几步无所谓, 关键是可跳的覆盖范围 → 转化为跳跃覆盖范围究竟可不可以覆盖到终点

  • 每次移动取最大跳跃步数(得到最大的覆盖范围)，每移动一个单位，就更新最大覆盖范围 图示
1
2
3
4
5
6
7
8
9
bool canJump(vector<int>& nums) {
    if(nums.size() == 1) return true;
    int dis = 0;
    for(int i = 0; i <= dis; i ++) {
        dis = max(dis, i + nums[i]); 
        if(dis >= nums.size() - 1) return true;
    }
    return false;
}

45.跳跃游戏II

要计算最少步数，什么时候步数才一定要加一呢？

  • 局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一
  • 整体最优：一步尽可能多走，从而达到最少步数

从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数。需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖， 图示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int jump(vector<int>& nums) {
    if(nums.size() == 1) return 0;
    //curDis当前覆盖的最远距离下标, nextDis下一步..
    int cnt = 0, curDis = 0, nextDis = 0;
    for(int i = 0; i < nums.size() - 1; i ++) {
        nextDis = max(nextDis, i + nums[i]);
        if(i == curDis) curDis = nextDis, cnt ++;
    }
    return cnt;
}

其精髓在于控制移动下标i只移动到nums.size() - 2的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一 参考

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论