hot100之贪心

这篇文章介绍了hot100之贪心，分享给大家做个参考，收藏Java资料网收获更多编程知识

买卖股票的最佳时期(121)

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < prices.length; i++){
            min = Math.min(min, prices[i]);
            res = Math.max(res,prices[i] - min);
        }
        return res;
    }
}

• 感悟

贪心就是贪局部最优解, 扩散到全局

跳跃游戏(055)

class Solution {
    public boolean canJump(int[] nums) {
        int max_length = 0;
        int i = 0;
        for (; max_length >= i && i < nums.length; i++){
            max_length = Math.max(max_length, i + nums[i]);
        }
        return i == nums.length;
    }
}

• 分析

max_length来维护理论可达距离

跳跃游戏II(045)

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int res = 0;
        int curr = 0;
        int nextCurr = 0;
        for (int i = 0; i < n-1 ; i++){
            nextCurr = Math.max(nextCurr, i+ nums[i]);
            if (i == curr){
                curr = nextCurr;
                res++;
            }
        }
        return res;
    }
}

• 分析

curr 维护本次跳跃最大可达距离

nextCurr 通过遍历途经点, 维护下次跳跃最大可达距离

划分字母区间(763)

class Solution {
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        int[] last = new int[26];
        for (int i = 0 ; i < n; i++){
            last[charArray[i]- 'a'] = i;
        }

        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++){
            end = Math.max(end, last[charArray[i] - 'a']);
            if (end == i){
                res.add(end - start + 1);
                start = i+1;
            }
        }
        return res;
    }
}

• 分析

将字符串预处理, 产生每个字符的最大索引

提取[start,end]范围内字符的最远索引来更新end

• 感悟

遇到这种熟悉又陌生的题型真别怕, 先把陌生数据转换成熟悉的, 这题就跟跳跃游戏II(045)一样了

文章来源:https://www.cnblogs.com/many-bucket/p/18942353
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！