CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第三十一天

Posted on

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

贪心策略，只在第二天的价格高于今天时才买。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {

        int profit = 0;
        int diff = 0;

        for (int i = 0; i < prices.length - 1; i++) {
            diff = prices[i + 1] - prices[i];

            // purchase iff next day's price is higher than today's
            if (diff > 0){
                profit += diff;
            }
        }

        return profit;
    }
}

LeetCode 50. 跳跃游戏

还挺有趣的，有点类似于脑筋急转弯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canJump(int[] nums) {

        if (nums.length == 1) {
            return true;
        }

        int approach = nums[0];

        for (int i = 0; i <= approach; i++) {
            approach = Math.max(approach, i + nums[i]);
            if(approach >= nums.length - 1) {
                return true;
            }
        }

        return false;
    }
}

LeetCode 45. 跳跃游戏ii

这道题的贪心解法特别的巧妙，巧妙的点在于它利用了当前范围内的最大可能覆盖范围进行了贪心，curRange意味着当前跳跃次数范围内的边界，超出这个边界则意味着步数的增加。遍历的终点在于nums.length - 2， 因为题目已经给定，必然存在能跳跃到终点的解存在，那么这个最后一站的最大可能性就是nums.length - 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int jump(int[] nums) {

        if (nums.length == 1) {
            return 0;
        }

        int curRange = 0;
        int potential = 0;
        int res = 0;

        // here our traverse stops at i == nums.length -2
        // if as this case, i == curRange, it naturally
        // need one more step, and res would increase by 1
        // else, it means that the curRangg has already covered
        // the nums.length - 1
        for (int i = 0; i < nums.length - 1; i++) {
            
            potential = Math.max(potential, i + nums[i]);

            if (i == curRange) {
                res++;
                curRange = potential;
            }
        }

        return res;
    }
}