当前位置: 首页 > news >正文

【算法】(Python)贪心算法

贪心算法:

  • 又称贪婪算法,greedy algorithm。
  • 贪心地追求局部最优解,即每一步当前状态下最优选择。
  • 试图通过各局部最优解达到最终全局最优解。但不从整体最优上考虑,不一定全局最优解。
  • 步骤:从初始状态拆分成一步一步的,每一步确保当前状态最优解,再下一步。
  • 关键:具体的贪心策略(选择能产生问题最优解的最优度量标准)。
  • 使用条件:贪心选择(一个问题最优解可通过一系列局部最优解达到,每一步可依赖以前的选择,不可回溯),最优子结构(一个问题最优解包含其子问题的最优解)。

案例:

1、(难度:简单)【力扣】1710. 卡车上的最大单元数

 解题思路:每一步优先挑选当前可装载的最大单元数量的箱子。

  1. 将列表按单元数量(元素中下标为1的值)降序排列。
  2. 遍历列表中所有元素,
  3. 若当前元素的箱子最大数量已经达到指定总数量,则单元总数=指定总数量*单元数量,并结束,返回单元总数。
  4. 若当前箱子最大数量在指定总数量之内,则当前箱子最大数量*单元数量,累加到单元总数中,剩余指定总数量=指定总数量-当前箱子最大数量;
  5. 再判断列表中下一个元素,
  6. 直到遍历完列表中所有元素,或者达到指定总数量,返回单元总数。

 知识点:列表.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. 买卖股票的最佳时机含手续费

解题思路:买卖为一次交易、计算一次手续费,则买入时计算手续费。买入价尽可能当前最低价,卖出价尽可能当前最高价。

  1. 初始买入价为列表第一日价格(含手续费),
  2. 依次遍历列表中每日价格,
  3. 若当前价(含手续费)<买入价,即当前价格比前一天低,则当前价(含手续费)为新的买入价。若当前价(不含手续费)>买入价,则假装卖出,计算利润(若前一日也假装卖出则利润加上当前价与前一日的差价),并假装当天免手续费买入,即当天价(不含手续费)为买入价,
  4. 下一日价格,当前价再与买入价比较。
  5. 遍历完列表所有元素,返回总利润。
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. 最低加油次数

解题思路:一个优先队列记录每个加油站的加油量(降序,最大油量在前)。计算每到一个地方的剩余油量,若不足则优先使用最大油量加油。

  1. 遍历每个地方和目的地(n+1),
  2. 计算从上一个位置到达当前地方后的剩余油量,
  3. 若剩余油量不足,则依次从优先队列取出最大油量加油,每加一次统计一次,直到加满或优先队列为空(即没有油可加),
  4. 若加完油后剩余油量仍不足,则无法到达目的地,返回-1,
  5. 每到达一个加油站,将加油量添加到优先队列,并将当前地方设为上一位置,用于下一个地方计算判断油量。

 知识点:二维数组[子数组下标][子数组中元素下标]:获取二维数组中元素。二维数组:数组中的元素类型仍为数组。

               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

注:本题其他解题方法:动态规划。本文忽略。


http://www.mrgr.cn/news/67171.html

相关文章:

  • 1.3 自然语言处理的应用
  • # Ubuntu 达人九步养成记(1)
  • Unity网络开发基础(part5.网络协议)
  • C# Modbus RTU通讯回顾
  • 【Eclipse系列】Eclipse版本与jdk对应版本
  • 基于python深度学习的交通标志图像识别设计与实现,卷积神经网络(CNN)作为主要架构
  • 解决return code from pthread_create() is 22报错问题
  • 数据结构 ——— 链式二叉树oj题:相同的树
  • mqtt 传递和推送 温湿度计消息 js
  • 盘点10款录音转文字工具,帮你开启高效记录。
  • 架构零散知识点
  • 看到你还在用Maven,Gradle难道不香吗?
  • 接口测试用例设计的关键步骤与技巧解析
  • 深度学习:循环神经网络(RNN)详解
  • openssl生成加密,公钥实现非对称加密
  • 通过 SSH 连接远程 Ubuntu 服务器
  • Uniapp全局文件执行顺序详解
  • 第11章 LAMP架构企业实战
  • 基于STM32的智能声音跟随小车设计
  • html语法
  • 第2章-立项 2.1硬件工程师为什么要关注立项
  • 微服务系列五:避免雪崩问题的限流、隔离、熔断措施
  • 探索人工智能的不同形态与未来方向:从ANI到AGI,再到ASI
  • 写歌词的技巧和方法:精准用词,让歌词熠熠生辉,妙笔生词AI智能写歌词软件
  • MySQL是怎么保证高可用的?
  • 人工智能:引领未来的变革之路