贪心算法思想
在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解 。
特征
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解 。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中,至于什么问题具有什么样的贪心选择性质是不确定的,需要具体问题具体分析 。
存在问题
贪心算法也存在如下问题:
- 不能保证解是最佳的。因为贪心算法总是从局部出发,并没从整体考虑
- 贪心算法一般用来解决求最大或最小解
- 贪心算法只能确定某些问题的可行性范围
用例
给你一个整数数组 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....
标签:一下,heights,算法,砖块,最优,梯子,贪心 From: https://www.cnblogs.com/xiaobaibuai/p/16788666.html