初学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

相关文章

VSCode配置Anaconda Python环境的实现

《VSCode配置AnacondaPython环境的实现》VisualStudioCode中可以使用Anaconda环境进行Python开发,本文主要介绍了VSCode配置AnacondaPytho... 目录前言一、安装 Visual Studio Code 和 Anaconda二、创建或激活 conda

pytorch+torchvision+python版本对应及环境安装

《pytorch+torchvision+python版本对应及环境安装》本文主要介绍了pytorch+torchvision+python版本对应及环境安装,安装过程中需要注意Numpy版本的降级,... 目录一、版本对应二、安装命令(pip)1. 版本2. 安装全过程3. 命令相关解释参考文章一、版本对

讯飞webapi语音识别接口调用示例代码(python)

《讯飞webapi语音识别接口调用示例代码(python)》:本文主要介绍如何使用Python3调用讯飞WebAPI语音识别接口,重点解决了在处理语音识别结果时判断是否为最后一帧的问题,通过运行代... 目录前言一、环境二、引入库三、代码实例四、运行结果五、总结前言基于python3 讯飞webAPI语音

基于Python开发PDF转PNG的可视化工具

《基于Python开发PDF转PNG的可视化工具》在数字文档处理领域,PDF到图像格式的转换是常见需求,本文介绍如何利用Python的PyMuPDF库和Tkinter框架开发一个带图形界面的PDF转P... 目录一、引言二、功能特性三、技术架构1. 技术栈组成2. 系统架构javascript设计3.效果图

Python如何在Word中生成多种不同类型的图表

《Python如何在Word中生成多种不同类型的图表》Word文档中插入图表不仅能直观呈现数据,还能提升文档的可读性和专业性,本文将介绍如何使用Python在Word文档中创建和自定义各种图表,需要的... 目录在Word中创建柱形图在Word中创建条形图在Word中创建折线图在Word中创建饼图在Word

Python Excel实现自动添加编号

《PythonExcel实现自动添加编号》这篇文章主要为大家详细介绍了如何使用Python在Excel中实现自动添加编号效果,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、背景介绍2、库的安装3、核心代码4、完整代码1、背景介绍简单的说,就是在Excel中有一列h=会有重复

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后,需要到系统环境变量中添加两个变量2. 第3步 “在cmd中

Python FastAPI入门安装使用

《PythonFastAPI入门安装使用》FastAPI是一个现代、快速的PythonWeb框架,用于构建API,它基于Python3.6+的类型提示特性,使得代码更加简洁且易于绶护,这篇文章主要介... 目录第一节:FastAPI入门一、FastAPI框架介绍什么是ASGI服务(WSGI)二、FastAP

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod