侧边栏壁纸
博主头像
峰峰火火

一条咸鱼罢了

  • 累计撰写 122 篇文章
  • 累计创建 89 个标签
  • 累计收到 59 条评论

目 录CONTENT

文章目录

学一下贪心算法

峰峰火火
2022-08-19 / 0 评论 / 0 点赞 / 365 阅读 / 780 字 / 正在检测是否收录...
温馨提示:
若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

贪心算法思想

在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解 。

特征

1、贪心选择性质

  一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解 。

2、最优子结构性质

  当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中,至于什么问题具有什么样的贪心选择性质是不确定的,需要具体问题具体分析 。

存在问题

贪心算法也存在如下问题:

  1. 不能保证解是最佳的。因为贪心算法总是从局部出发,并没从整体考虑
  2. 贪心算法一般用来解决求最大或最小解
  3. 贪心算法只能确定某些问题的可行性范围

用例

LeetCode - 1642 可以到达的最远建筑


给你一个整数数组 heights ,表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。

你从建筑物 0 开始旅程,不断向后面的建筑物移动,期间可能会用到砖块或梯子。

当从建筑物 i 移动到建筑物 i+1(下标 从 0 开始 )时:

如果当前建筑物的高度 大于或等于 下一建筑物的高度,则不需要梯子或砖块
如果当前建筑的高度 小于 下一个建筑的高度,您可以使用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳方式使用给定的梯子和砖块,返回你可以到达的最远建筑物的下标(下标 从 0 开始 )。
 

利用贪心算法

因为梯子可以跨越任意高度,所以优先使用砖块,砖块不够了再使用梯子。

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int i = 0;
        while (i < heights.length - 1) {
            if (heights[i] >= heights[i + 1]) {
                i++;
                continue;
            }
            int sp = heights[i + 1] - heights[i];
            if (bricks >= sp) {
                bricks -= sp;
                i++;
                continue;
            }
            if (ladders > 0) {
                ladders--;
                i++;
                continue;
            }
            break;
        }
        return i;
    }
}

只做到局部最优解,对于本道题,用例如
[2,7,8,9,10,11]
5
1
不能通过,因为2-7差值最大,原理上应该使用梯子就可以,后面差值小的才使用砖块。

进一步优化

loading…

0

评论区