【算法】(Python)贪心算法
贪心算法:
- 又称贪婪算法,greedy algorithm。
- 贪心地追求局部最优解,即每一步当前状态下最优选择。
- 试图通过各局部最优解达到最终全局最优解。但不从整体最优上考虑,不一定全局最优解。
- 步骤:从初始状态拆分成一步一步的,每一步确保当前状态最优解,再下一步。
- 关键:具体的贪心策略(选择能产生问题最优解的最优度量标准)。
- 使用条件:贪心选择(一个问题最优解可通过一系列局部最优解达到,每一步可依赖以前的选择,不可回溯),最优子结构(一个问题最优解包含其子问题的最优解)。
案例:
1、(难度:简单)【力扣】1710. 卡车上的最大单元数
解题思路:每一步优先挑选当前可装载的最大单元数量的箱子。
- 将列表按单元数量(元素中下标为1的值)降序排列。
- 遍历列表中所有元素,
- 若当前元素的箱子最大数量已经达到指定总数量,则单元总数=指定总数量*单元数量,并结束,返回单元总数。
- 若当前箱子最大数量在指定总数量之内,则当前箱子最大数量*单元数量,累加到单元总数中,剩余指定总数量=指定总数量-当前箱子最大数量;
- 再判断列表中下一个元素,
- 直到遍历完列表中所有元素,或者达到指定总数量,返回单元总数。
知识点:列表.sort(key=排序条件, reverse=True):列表按照排序条件降序排列。
class Solution:def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:# 将列表按单元数量(即各元素下标为1的值)降序排列boxTypes.sort(key=lambda x: x[1], reverse=True)total = 0 # 记录可装载的单元总数# 遍历列表,指定最大数量依次减去最大箱子数量计算剩余数量,并统计单元总数# i为箱子数量,j为每个箱子的单元数量for i, j in boxTypes:if i >= truckSize:total += truckSize * jbreaktotal += i * jtruckSize -= ireturn total
2、(难度:中等)【力扣】714. 买卖股票的最佳时机含手续费
解题思路:买卖为一次交易、计算一次手续费,则买入时计算手续费。买入价尽可能当前最低价,卖出价尽可能当前最高价。
- 初始买入价为列表第一日价格(含手续费),
- 依次遍历列表中每日价格,
- 若当前价(含手续费)<买入价,即当前价格比前一天低,则当前价(含手续费)为新的买入价。若当前价(不含手续费)>买入价,则假装卖出,计算利润(若前一日也假装卖出则利润加上当前价与前一日的差价),并假装当天免手续费买入,即当天价(不含手续费)为买入价,
- 下一日价格,当前价再与买入价比较。
- 遍历完列表所有元素,返回总利润。
class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:profit = 0 # 记录总收益buy = prices[0] + fee # 初始买入# 遍历每个价格for i in prices:# 若当前价+手续费<买入价,则当前价买入if i + fee < buy:buy = i + fee# 当前价格>买入价,(假装卖出)计算利润(当前价与买入价的差),# 并假装以当前价免手续费买入(若明天价比当前价高,明天收益就是明天价与当前价之间的差)elif i > buy:profit += (i - buy)buy = ireturn profit
注:本题其他解题方法:动态规划。本文忽略。
3、(难度:困难)【力扣】871. 最低加油次数
解题思路:一个优先队列记录每个加油站的加油量(降序,最大油量在前)。计算每到一个地方的剩余油量,若不足则优先使用最大油量加油。
- 遍历每个地方和目的地(n+1),
- 计算从上一个位置到达当前地方后的剩余油量,
- 若剩余油量不足,则依次从优先队列取出最大油量加油,每加一次统计一次,直到加满或优先队列为空(即没有油可加),
- 若加完油后剩余油量仍不足,则无法到达目的地,返回-1,
- 每到达一个加油站,将加油量添加到优先队列,并将当前地方设为上一位置,用于下一个地方计算判断油量。
知识点:二维数组[子数组下标][子数组中元素下标]:获取二维数组中元素。二维数组:数组中的元素类型仍为数组。
python中heapq库用于操作堆(最小堆,最大堆),应用于优先队列和堆排序。此处为优先队列。
heapq.heappush(队列, 元素):往优先队列添加元素,自动生成最小堆(父节点小于所有子节点,左右子节点无大小要求)。元素前加负号“-”,则各元素负数后的最小堆,类似最大堆,取出时前面也加负号“-”即为最大值。
heapq.heappop(队列):从优先队列中取出最小值。
class Solution:def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int: import heapqres = 0 # 统计加油次数fuel_list = [] # 油量优先队列(最大的在前),记录每个加油站的加油量fuel = startFuel # 记录目前油量pre = 0 # 记录上一个位置# 遍历每个加油站和目的地n = len(stations)for i in range(n + 1):# 记录当前位置,若加油站则为元素中下标为0的值,若目的地则为targetif i < n: cur = stations[i][0]else: cur = target# 计算达到当前位置,剩余油量fuel -= cur - pre# 若剩余油量<0,且油量优先队列中有元素,依次按最大油量加油,直到加满或油量优先队列为空while fuel < 0 and fuel_list:# 油量优先队列为了从大到小排列,元素是负数fuel += (-heapq.heappop(fuel_list)) # 从优先队列取出最大值res += 1# 若加油后,剩余油量仍<0,说明即使加满油也到不了目的地if fuel < 0: return -1# 每到一个加油站,将油量添加到油量优先队列中if i < n:# 油量优先队列为了从大到小排列,元素是负数heapq.heappush(fuel_list, -stations[i][1]) # 添加到优先队列(最大堆)pre = curreturn res
以上是从上次位置到达该加油站后剩余油量判断,也可以直接判断从起始位置到达各加油站时油量是否充足,若不足则取出油量优先队列的最大值加油。
class Solution:def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:import heapqh = [] # 油量优先队列(最大的在前),记录每个加油站的加油量res = 0 # 统计加油次数# 遍历每个加油站和目的地for long, fuel in stations + [[target, 0]]:# 若油量不够,则从优先队列取出最大油量加油while startFuel < long:# 若优先队列为空(即没有油可加),即无法到达目的地if not h: return -1startFuel -= heapq.heappop(h)res += 1# 每到一个加油站,就将油量添加到优先队列heapq.heappush(h, -fuel)return res
注:本题其他解题方法:动态规划。本文忽略。