概述

贪心算法(Greedy Algorithm)是一种在解决问题时,按照某种标准在每一步都选择当前最优解(局部最优解)的算法。它期望通过一系列局部最优解的选择,最终能够得到全局最优解。

贪心算法的核心思想

贪心算法的核心思想是每一步都采取最优选择,即所谓的“贪心选择”。算法会根据某种贪心策略,逐步做出局部最优的选择,并希望通过这些局部最优的选择能够得到最终的全局最优解。

贪心算法的一般步骤

  1. 问题分解:将问题分解为若干个子问题。
  2. 选择贪心策略:为每个子问题选取局部最优解(通常是通过某种评价标准,选择当前最有利的选择)。
  3. 合并子问题的解:将每次的选择累积起来,直到解决完所有子问题,得到最终的全局解。

贪心算法的应用场景

贪心算法适用于那些通过选择局部最优解,最终能够得到全局最优解的问题。一般来说,贪心算法并不总是能找到全局最优解,但在某些特定问题中,它可以得到最优解。常见的贪心算法应用场景包括:

  1. 最小生成树问题:Kruskal 和 Prim 算法都是基于贪心策略的,能够找到加权连通图的最小生成树。
  2. 活动选择问题:用于选择最多的不重叠活动,典型的贪心选择是选择结束时间最早的活动。
  3. 背包问题(贪心版的 0-1 背包问题):按物品的单位价值从高到低进行选择,直到装满背包。

贪心算法的优缺点

优点

  • 简单、高效:由于只关注局部最优,贪心算法通常比较简单,运行速度较快。
  • 直接、可实现性强:贪心算法容易实现,对于某些问题是最佳解决方案。

缺点

  • 不适用于所有问题:贪心算法无法保证在所有问题中都能找到全局最优解,尤其是当局部最优解无法组合成全局最优解时。
  • 需要问题具备“贪心选择性质”:即从局部最优能够推导出全局最优。

刷题

买卖股票的最佳时机

题目

121. 买卖股票的最佳时机 - 力扣(LeetCode)

思路

初始思路:以每一个数组元素为买入点,找出利润的最大值,时间复杂度是O(n)

优化思路:在遍历的过程中,我们始终选择当前最小的买入价格,并计算卖出的最大可能利润。

代码

初始代码

public int maxProfit(int[] prices) {
        int n = prices.length;
        int max = 0;
        for (int i = 0; i < n; i++) {
            for(int j=i+1;j<n;j++){
                if(prices[j]>prices[i]){
                    max = Math.max(max,prices[j]-prices[i]);
                }
            }
        }
        return max;
    }

优化后的代码

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

跳跃游戏

题目

55. 跳跃游戏 - 力扣(LeetCode)

思路

  • 初始化一个变量 maxReach,表示当前能够到达的最远位置。
  • 遍历数组的每一个元素,对于每个元素 nums[i],检查是否可以从当前位置到达更远的位置,即 maxReach 是否大于或等于当前下标 i。
  • 在遍历的过程中,不断更新能够到达的最远位置 maxReach 为 i + nums[i]。
  • 如果在遍历过程中,某个位置的 maxReach 大于或等于最后一个下标,则返回 true;否则,如果遍历结束仍未达到最后一个下标,则返回 false。

代码

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

跳跃游戏Ⅱ

题目

45. 跳跃游戏 II - 力扣(LeetCode)

思路

1.定义状态:

  • 维护两个变量 curEnd 和 curFarthest:
  • curEnd 表示当前跳跃范围的最远边界。
  • curFarthest 表示通过当前步能够到达的最远位置。

2.遍历数组:

  • 遍历 nums,在每次遍历时,我们会更新 curMax,表示通过当前跳跃可以到达的最远位置。
  • 当遍历到 curEnd 时,表示当前跳跃已经完成,必须进行下一次跳跃,并更新 max 为 curMax,跳跃次数加1。
  • 最后,如果遍历到了数组的最后一个位置,返回跳跃次数即可。

贪心策略:

  • 在每一次跳跃中,我们尽可能向前跳得最远,这样才能保证在最少的跳跃次数内到达数组末尾。

代码

public int jump(int[] nums) {
        int n = nums.length;
        int max = 0;
        int curMax = 0;
        int sum =0;
        for(int i = 0; i < n; i++) {
            if(i==n-1){
                break;
            }
            curMax = Math.max(curMax, nums[i] + i);
            if(i==max){
                max = curMax;
                sum++;
            }
        }
        return sum;
    }

划分字母区间

题目

763. 划分字母区间 - 力扣(LeetCode)

思路

  • 用一个last数组,记录每个字母出现的最远位置
  • 遍历数组,使用start和end记录当前划分字符串的开头和结尾
  • 每次不断的更新当前字符串的最远位置
  • 当i和end相等,即代表当前字符串划分结束

代码

public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<Integer>();
        int[] last = new int[26];
        for(int i=0;i<s.length();i++){
            last[s.charAt(i)-'a']=i;
        }
        int end = 0,start = 0;
        for(int i=0;i<s.length();i++){
            end = Math.max(end, last[s.charAt(i)-'a']);
            if(i==end){
                res.add(end-start+1);
                start=i+1;
            }
        }
        return res;
    }

结语

每次做贪心都觉得自己智商低

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部