贪心算法的适用场景

问题能够分解成子问题进行解决,子问题的最优解能够递推到最终问题的最优解。这种子问题的最优解称为最优子结构。

贪心和动态规划的区别在于它对每个子问题的解决方案都做选择,不能回退。动态规划会保存以前的运算结果,并根据以前的结果对当前进行选择,
有回退功能。

题目一: 买卖股票的最佳时机 2

题目链接

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

分析思路:
看这个题目的意思是允许尽可能多的进行股票交易,如此的话,我们可以假象成,如果今天的股票比昨天的股票价格高就卖出,一直计算到最后一天即为最大收益。
参考代码:

题目二: 买卖股票的最佳时机含手续费

给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每次交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。

示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 – 1) – 2) + ((9 – 4) – 2) = 8.
注意:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

题目三: 跳跃游戏

题目链接

给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

分析思路:
这个题我们可以从后往前分析,首先判断倒数第二个元素能否到达最后一个元素,如果可以,我们将不再考虑最后一个元素,
因为根据刚才的分析如果可以到达倒数第二个,那么也可以到达最后一个元素。

然后依次往前递推,如果都能跳到的话,我们最后应该分析的就是第一个元素能否跳到第二个元素上。

这个比较符合动态规划的思想,我们先用动态规划解下这道题。

分析上面的代码,可以看出使用动态规划的时间复杂度是O(n^2),空间复杂度是O(n)。

下面我们使用贪心的思路看下这个问题,我们记录一个的坐标代表当前可达的最后节点,这个坐标初始等于nums.length-1,
然后我们每判断完是否可达,都向前移动这个坐标,直到遍历结束。

如果这个坐标等于0,那么认为可达,否则不可达。

这段代码的时间复杂度是O(n),空间复杂度是O(1),可以看出比动态规划解法有了明显的性能提升。

题目四: 坏了的计算器

题目链接

在显示着数字的坏计算器上,我们可以执行以下两种操作:
双倍(Double):将显示屏上的数字乘 2;
递减(Decrement):将显示屏上的数字减 1 。
最初,计算器显示数字 X。
返回显示数字 Y 所需的最小操作数。

示例 1:
输入:X = 2, Y = 3
输出:2
解释:先进行双倍运算,然后再进行递减运算 {2 -> 4 -> 3}.

示例 2:
输入:X = 5, Y = 8
输出:2
解释:先递减,再双倍 {5 -> 4 -> 8}.

分析思路:
这道题正向推导比较困难,因为无法知道是先乘二后递增,还是先递增后乘二,因此我们尝试反过来思考(反过来就可以直接除了),通过除法和递减计算目标数到初始数的最小次数。遇到奇数加一后除以二(奇数除完会减一),偶数直接除以二,直到目标数小于初始数,然后我们加上递减的次数就是最小次数。

为什么说不断除二就可以找到最小次数呢?因为乘除对数字的变化要大于递增和递减,这是基本的数学知识,想要找到最小次数,就必须能尽可能多的进行除法,这也是贪心算法的基本逻辑。
参考代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注