初学python记录:力扣2462. 雇佣 K 位工人的总代价

2024-05-02 04:28

本文主要是介绍初学python记录:力扣2462. 雇佣 K 位工人的总代价,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

给你一个下标从 0 开始的整数数组 costs ,其中 costs[i] 是雇佣第 i 位工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人:

  • 总共进行 k 轮雇佣,且每一轮恰好雇佣一位工人。
  • 在每一轮雇佣中,从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人,如果有多位代价相同且最小的工人,选择下标更小的一位工人。
    • 比方说,costs = [3,2,7,7,1,2] 且 candidates = 2 ,第一轮雇佣中,我们选择第 4 位工人,因为他的代价最小 [3,2,7,7,1,2] 。
    • 第二轮雇佣,我们选择第 1 位工人,因为他们的代价与第 4 位工人一样都是最小代价,而且下标更小,[3,2,7,7,2] 。注意每一轮雇佣后,剩余工人的下标可能会发生变化。
  • 如果剩余员工数目不足 candidates 人,那么下一轮雇佣他们中代价最小的一人,如果有多位代价相同且最小的工人,选择下标更小的一位工人。
  • 一位工人只能被选择一次。

返回雇佣恰好 k 位工人的总代价。

提示:

  • 1 <= costs.length <= 105
  • 1 <= costs[i] <= 105
  • 1 <= k, candidates <= costs.length

思考:

暴力解法

招k个人即为k次循环,每次判断待选人与candidates的大小关系,选出题意所需的最小花销和员工索引,从待选人中去掉该员工,进行下一次循环。每次花销相加即为结果,代码如下:

class Solution(object):def totalCost(self, costs, k, candidates):""":type costs: List[int]:type k: int:type candidates: int:rtype: int"""n = len(costs)ans = 0for _ in range(k):if n < candidates:# 如果剩余员工数目不足 candidates 人,那么下一轮雇佣他们中代价最小的一人,如果有多位代价相同且最小的工人,选择下标更小的一位工人。min_value = min(costs)index = costs.index(min_value)ans += min_valuecosts.pop(index)n -= 1else:# 在每一轮雇佣中,从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人,如果有多位代价相同且最小的工人,选择下标更小的一位工人。min_value = 10 ** 6for i in range(candidates):if costs[i] < min_value:min_value = costs[i]index = ifor j in range(n - candidates, n):if costs[j] < min_value:min_value = costs[j]index = jans += min_valuecosts.pop(index)n -= 1return ans

提交超时,卡在第 132 / 162  个例子:

优化——最小堆

1. 设n为costs数组的长度(即候选人数量),若n - candidates*2 < k,则我们选取的k个人一定是整个costs数组中最小的k个数,所以直接返回最小的k个数的和即可;

2. 否则,分别用两个最小堆储存 前candidates个元素后candidates个元素,每次比较两个最小堆的堆顶元素,选更小的从堆顶弹出并加到ans,并向堆中填充对应位置的新元素。直到选完k个人为止。

代码如下:

class Solution(object):def totalCost(self, costs, k, candidates):""":type costs: List[int]:type k: int:type candidates: int:rtype: int"""n = len(costs)    # 待选人数量ans = 0if n < candidates*2 + k:costs.sort()return sum(costs[:k])wait_1 = costs[:candidates]     # 前candidates个元素wait_2 = costs[-candidates:]     # 后candidates个元素# 转成最小堆的形式heapify(wait_1)heapify(wait_2)left = candidatesright = n - 1 - candidatesfor _ in range(k):# 比较两个最小堆堆顶元素,选更小的弹出并加到ans,并向堆中填充对应位置的新元素if wait_1[0] <= wait_2[0]:ans += heapreplace(wait_1, costs[left])left += 1else:ans += heapreplace(wait_2, costs[right])right -= 1return ans

提交通过:

 

 

这篇关于初学python记录:力扣2462. 雇佣 K 位工人的总代价的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/953381

相关文章

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传:从崩溃边缘抢救进度二、多线程加速:榨干网络带宽三、速度控制:做网络的好邻居四、终端交互

Python中注释使用方法举例详解

《Python中注释使用方法举例详解》在Python编程语言中注释是必不可少的一部分,它有助于提高代码的可读性和维护性,:本文主要介绍Python中注释使用方法的相关资料,需要的朋友可以参考下... 目录一、前言二、什么是注释?示例:三、单行注释语法:以 China编程# 开头,后面的内容为注释内容示例:示例:四

Python中win32包的安装及常见用途介绍

《Python中win32包的安装及常见用途介绍》在Windows环境下,PythonWin32模块通常随Python安装包一起安装,:本文主要介绍Python中win32包的安装及常见用途的相关... 目录前言主要组件安装方法常见用途1. 操作Windows注册表2. 操作Windows服务3. 窗口操作

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提

python常用的正则表达式及作用

《python常用的正则表达式及作用》正则表达式是处理字符串的强大工具,Python通过re模块提供正则表达式支持,本文给大家介绍python常用的正则表达式及作用详解,感兴趣的朋友跟随小编一起看看吧... 目录python常用正则表达式及作用基本匹配模式常用正则表达式示例常用量词边界匹配分组和捕获常用re

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分,使用python生成公钥与私钥,然后保存在两个文

python删除xml中的w:ascii属性的步骤

《python删除xml中的w:ascii属性的步骤》使用xml.etree.ElementTree删除WordXML中w:ascii属性,需注册命名空间并定位rFonts元素,通过del操作删除属... 可以使用python的XML.etree.ElementTree模块通过以下步骤删除XML中的w:as

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者(Producer)配置1. 创建 Spr

使用Python绘制3D堆叠条形图全解析

《使用Python绘制3D堆叠条形图全解析》在数据可视化的工具箱里,3D图表总能带来眼前一亮的效果,本文就来和大家聊聊如何使用Python实现绘制3D堆叠条形图,感兴趣的小伙伴可以了解下... 目录为什么选择 3D 堆叠条形图代码实现:从数据到 3D 世界的搭建核心代码逐行解析细节优化应用场景:3D 堆叠图

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧