代码随想录day32

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

● 力扣题目链接
● 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
● 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
● 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路

● 价格有一个价格数组，前后两天的价格差构成利润数组，我们把利润数组中所有大于零的元素加和即可

代码

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 1) return 0;
        int profit = 0;
        int[] pro = new int[prices.length - 1];
        for (int i = 0; i < pro.length; i++) {
            pro[i] = prices[i + 1] - prices[i];
            if (pro[i] > 0) profit += pro[i];
        }
        return profit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

55. 跳跃游戏

思路

● 遍历覆盖范围，在此期间不断更新覆盖范围，一旦覆盖了末尾，就返回true

代码

class Solution {
    public boolean canJump(int[] nums) {
        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;
    }
}
1
2
3
4
5
6
7
8
9
10

45.跳跃游戏 II

● 力扣题目链接
● 给定一个非负整数数组，你最初位于数组的第一个位置。
● 数组中的每个元素代表你在该位置可以跳跃的最大长度。
● 你的目标是使用最少的跳跃次数到达数组的最后一个位置。

思路

● 记录当前位置和下一步最大位置

代码

class Solution {
    public int jump(int[] nums) {
        int count = 0;
        int curDistance = 0;
        int nextDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            nextDistance = Math.max(nextDistance, nums[i] + i);
            if (nextDistance >= nums.length - 1) {
                count++;
                break;
            }
            if (i == curDistance) {
                curDistance = nextDistance;
                count++;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19