Leetcode 刷题记录 18—— 贪心算法

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答，01~07为C++语言，08及以后为Java语言。

01 买卖股票的最佳时机

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = prices[0];
        int ans = 0;

        for(int i=0; i<prices.length; i++){
            //最低股票价格
            minPrice = Math.min(prices[i], minPrice);
            //当日股票价格 - 最低股票价格 取最大值
            ans = Math.max(prices[i] - minPrice, ans); 
        }
        return ans;
    }
}

02 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        //只要道路不断延申，人终将走到终点
    	int path = 0;
        for(int i=0; i<nums.length; i++){
            if(i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }
}

03 跳跃游戏Ⅱ

class Solution {
    public int jump(int[] nums) {
        int ans = 0, path = 0;
        int start = 0, end = 1; //初始起跳范围，左闭右开区间
        while(end < nums.length){
            for(int i=start; i<end; i++){
                path = Math.max(path, i + nums[i]);
            }

            //更新起跳范围
            start = end;
            end = path + 1;
            ans++;
        }
        return ans;
    }
}

04 划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        int n = s.length();
        for(int i=0; i<n; i++){
            last[s.charAt(i) - 'a'] = i; //字母 -> 索引
        }

        List<Integer> partition = new LinkedList<>();
        int start = 0, end = 0;
        for(int i=0; i<n; i++){
            end = Math.max(end, last[s.charAt(i) - 'a']);

            if(end == i){
                partition.add(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
}