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

LeetCode算法题(Go语言实现)_52

news 来源：原创 2025/8/17 18:16:52

题目

给你一个下标从 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 位工人的总代价。

一、代码实现（Go语言）

import ("container/heap""sort"
)type element struct {cost  intindex int
}type MinHeap []elementfunc (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool {if h[i].cost == h[j].cost {return h[i].index < h[j].index}return h[i].cost < h[j].cost
}
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(element)) }
func (h *MinHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[:n-1]return x
}func totalCost(costs []int, k int, candidates int) int {n := len(costs)if candidates*2+k > n {sorted := make([]int, n)copy(sorted, costs)sort.Ints(sorted)sum := 0for i := 0; i < k; i++ {sum += sorted[i]}return sum}frontHeap, backHeap := &MinHeap{}, &MinHeap{}heap.Init(frontHeap)heap.Init(backHeap)i, j := candidates, n-candidates-1for idx := 0; idx < candidates; idx++ {heap.Push(frontHeap, element{cost: costs[idx], index: idx})}for idx := 0; idx < candidates; idx++ {pos := n - 1 - idxheap.Push(backHeap, element{cost: costs[pos], index: pos})}total := 0for k > 0 {k--var current elementuseFront := falseif frontHeap.Len() > 0 && backHeap.Len() > 0 {frontTop := (*frontHeap)[0]backTop := (*backHeap)[0]if frontTop.cost < backTop.cost || (frontTop.cost == backTop.cost && frontTop.index < backTop.index) {current = heap.Pop(frontHeap).(element)useFront = true} else {current = heap.Pop(backHeap).(element)}} else if frontHeap.Len() > 0 {current = heap.Pop(frontHeap).(element)useFront = true} else {current = heap.Pop(backHeap).(element)}total += current.costif useFront {if i <= j {heap.Push(frontHeap, element{cost: costs[i], index: i})i++}} else {if j >= i {heap.Push(backHeap, element{cost: costs[j], index: j})j--}}}return total
}

二、算法分析

1. 核心思路

双最小堆优化：使用两个最小堆分别管理前 candidates 和后 candidates 的候选工人，按代价和索引排序，确保快速取出最小值。
动态指针扩展：通过指针 i 和 j 动态扩展候选范围，前堆从左侧扩展，后堆从右侧收缩，避免重复处理元素。
特殊情况优化：当候选范围覆盖整个数组时（candidates*2 +k >n），直接排序取前 k 小元素之和。

2. 关键步骤

预处理特殊情况：若候选范围能覆盖所有选择，直接排序取前 k 小元素。
堆初始化：前堆和后堆分别存储初始候选元素。
层级处理：每次从堆顶取最小值，更新指针并扩展候选范围，直到完成 k 次选择。
边界处理：确保指针移动时不会交叉，避免重复处理元素。

3. 复杂度

指标	值	说明
时间复杂度	O(k log C)	C 为候选数，堆操作对数复杂度
空间复杂度	O©	堆最多存储 2C 个元素

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景验证

全候选覆盖：直接排序取最小 k 个元素。
指针交叉：停止扩展候选，仅处理堆中剩余元素。
索引冲突：优先选择索引更小的元素。

2. 扩展应用

动态数据流：支持实时插入新工人并调整堆结构。
多维度排序：增加工作经验、评级等指标作为次要排序条件。

3. 多语言实现

import heapqdef totalCost(costs, k, candidates):n = len(costs)if candidates * 2 + k > n:return sum(sorted(costs)[:k])front = [(costs[i], i) for i in range(candidates)]heapq.heapify(front)back = [(costs[n-1-i], n-1-i) for i in range(candidates)]heapq.heapify(back)i, j = candidates, n - candidates - 1total = 0for _ in range(k):if not front and not back:breakf_min = front[0] if front else (float('inf'), -1)b_min = back[0] if back else (float('inf'), -1)if f_min[0] < b_min[0] or (f_min[0] == b_min[0] and f_min[1] < b_min[1]):total += heapq.heappop(front)[0]if i <= j:heapq.heappush(front, (costs[i], i))i += 1else:total += heapq.heappop(back)[0]if j >= i:heapq.heappush(back, (costs[j], j))j -= 1return total

五、总结与优化

1. 算法对比

方法	优势	适用场景
双堆	动态扩展候选范围	大规模数据流处理
全排序	简单直接	候选范围覆盖全数组
暴力遍历	无需额外空间	极小规模数据（n < 50）

2. 工程优化

堆结构压缩：用元组 (cost, index) 替代对象，减少内存占用。
并行处理：多线程维护前堆和后堆的插入操作。
预计算优化：预处理部分候选范围以减少堆操作次数。

3. 扩展方向

多级候选策略：分层选择候选（如先选区域再选具体工人）。
动态调整候选数：根据剩余工人数量动态调整 candidates 值。

LeetCode算法题(Go语言实现)_52

题目给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人： 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。在每一轮雇佣中&#xf…...

编程日记 2025/8/17 18:16:52

基于尚硅谷FreeRTOS视频笔记——13—HAL库和RTOS时钟源问题

RTOS的时钟源就是系统定时器中断，通俗来说就是系统定时器每中断一次，就扫描一次RTOS，查看RTOS中有没有任务的切换。但是，系统存在一个HAL_Delay()函数，就是使用的系统定时器中断来执行的函数。当我们在RTOS中&…...

编程日记 2025/8/17 21:04:12

FPGA入门学习Day1——设计一个DDS信号发生器

目录一、DDS简介 （一）基本原理 （二）主要优势 （三）与传统技术的对比二、FPGA存储器 （一）ROM波形存储器 （二）RAM随机存取存储器 （三&…...

编程日记 2025/8/17 20:48:55

JavaScript-立即执行函数（Immediately Invoked Function Expression，IIFE）

立即执行函数（Immediately Invoked Function Expression，IIFE）是 JavaScript 里一种很独特的函数，它在定义后会马上执行。下面会详细介绍它的语法、用途、优点以及注意事项。一、语法立即执行函数一般有两种常见的语法形式&am…...

编程日记 2025/8/17 20:30:22

【Leetcode 每日一题 - 补卡】2537. 统计好子数组的数目

问题背景给你一个整数数组 n u m s nums nums 和一个整数 k k k，请你返回 n u m s nums nums 中好子数组的数目。一个子数组 a r r arr arr 如果有至少 k k k 对下标 ( i , j ) (i, j) (i,j) 满足 i < j i < j i<j 且 a r r [ i ] a r r [ …...

编程日记 2025/8/17 20:35:15

【工具-Krillin AI】视频翻译、配音、语音克隆于一体的一站式视频多语言转换工具~

Krillin AI 是全能型音视频本地化与增强解决工具。这款简约而强大的工具，集音视频翻译、配音、语音克隆于一身，支持横竖屏格式输出，确保在所有主流平台（哔哩哔哩，小红书，抖音，视频号&#xff0c…...

编程日记 2025/8/17 18:17:09

常用绑定事件方式有哪几种

绑定事件分为3种： 1、内联模式：将函数名直接作为标签属性的属性值（注意：这里是带括号的,不带括号不生效，但是在vue中可以加括号也可以不加括号，如果需要穿参数就加括号，不需要传参数可以不加&am…...

编程日记 2025/8/17 20:28:10

数据结构之BFS广度优先算法（腐烂的苹果）

队列这个数据结构在很多场景下都有使用，比如在实现二叉树的层序遍历，floodfill问题(等等未完成)中，都需要借助队列的先进先出特性，下面给出这几个问题的解法经典的二叉树的层序遍历算法图示，以下图所示的二叉树为例…...

编程日记 2025/8/17 18:17:03

linux 学习 1.开始学习

准备学习linux记录一下学习内容，只会包含必要的知识，和部分演示我采用的系统是Ubuntu24.04 初始掌握学习首先需要掌握如何查看帮助手册 man man # man 加任何命令可以看具体命令的帮助手册 man mkdir进入手册按 d(down)：往下翻半页u(u…...

编程日记 2025/8/17 21:00:06

Flink-01学习介绍Flink及上手小项目之词频统计

flink简介官网概述： 学习Flink具体包括四个关键概念：流数据的持续处理，事件时间，有状态流处理和状态快照。 Apache Flink 是一个开源的流处理框架，旨在处理批处理和实时数据处理，具有高吞吐量和低延迟的…...

编程日记 2025/8/17 20:56:09

【Linux我做主】探秘gcc/g++和动静态库

TOC Linux编译器gcc/g的使用 github地址有梦想的电信狗前言在软件开发的世界中，编译器如同匠人的工具，将人类可读的代码转化为机器执行的指令。对于Linux开发者而言，gcc和g是构建C/C程序的核心工具链，掌握它们的原理和使…...

编程日记 2025/8/17 18:17:24

工控系统前端设计(pyqt)

题目源自：白月黑羽的项目实战四-[工控系统前端] 代码已上传至gitcode https://gitcode.com/m0_37662818/Industrial_Control_System_Front_End 心得体会：直接用组态软件或者js吧项目亮点 tablemodel的使用，绑定了表格和数据风机自定义ite…...

编程日记 2025/8/17 21:18:55

一台 Master 多节点玩转 Kubernetes：sealos 一键部署实践

文章目录一台 Master 多节点玩转 Kubernetes：sealos 一键部署实践🔗 参考链接🌐 部署环境📦 安装包说明🔧 前期准备🚀 使用 sealos 安装 Kubernetes✅ 验证集群状态📌 后续可做的优化和拓展&am…...

编程日记 2025/8/17 18:17:08

写书的三驾马车

2019年8月19日23:52:28 先亮出我们的兵器组合： GitBook Git Markdown，享受行云流水一般的写作个人秀 GitBook : 一个基于 Node.js 的文档格式转换工具，支持 Markdown 和 AsciiDoc 两种语法格式，可以输出 HTML、PDF等格式的…...

编程日记 2025/8/17 21:34:56

科学护理进行性核上性麻痹，缓解病痛提升生活质量

进行性核上性麻痹是一种罕见的神经系统变性疾病，患者常出现姿势平衡障碍、吞咽困难、眼球运动异常等症状。通过科学的健康护理，能在一定程度上减轻患者痛苦，提升生活质量。日常护理，保障安全舒适患者日常活动时，需确…...

编程日记 2025/8/18 1:18:19

第七章：7.2求方程axx+bx+c=0的根，用3个函数，分别求当：bb-4ac大于0、等于0和小于0时的根并输出结果。从主函数输入a、b、c的值

//求方程a*x*xb*xc0的根，用3个函数，分别求当：b*b-4*a*c大于0、等于0和小于0时的根并输出结果。 //从主函数输入a、b、c的值 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<math.h> void s1(float a, float b, fl…...

编程日记 2025/8/17 20:55:17

优选算法系列（7.BFS 解决最短路问题）

简介： 先走到A，之后弹出A再把A能走到的地方加进去向外扩展把队列里面的元素（B，C）弹出来，再把B，C能到的地方入队列一直这样那么最短路程就是扩展的层数。迷宫中离入口最近的出口（me…...

编程日记 2025/8/17 18:17:11

定时发送邮件部署邮件服务查看有没有安装mailx,安装了 [root192 ~]# rpm -q mailx mailx-12.5-43.fc38.x86_64去网易拿一下授权码,写到配置文件里 vim /etc/mail.rcset fromxxxxxxx163.com set smtpsmtp.163.com set smtp-auth-userxxxxxxx163.com set smtp-auth-passwor…...

编程日记 2025/8/17 18:17:06

Java反射知识点学习笔记

目录一、定义二、获取class对象的三种方式 1、Class.forName("全类名") 2、类名.class 3、对象.getClass() 三、案例 1、获取 class 反射对象三种方式 2、利用反射获取构造方法 3、利用反射获取成员变量 4、利用反射获取成员方法 Java反射是一种强大的编…...

编程日记 2025/8/17 21:35:08

Unity ShaderLab引用HLSL文件找不到其中函数

在写Unity Shader的过程中，常常需要将方法封装到HLSL文件中，今天遇到一个这样的报错， 明明hlsl文件路径引用没问题，却引用不到方法并且将分散文件中的函数复制过来一切正常，最终定位到HLSL的预编译指令中这指令的…...

编程日记 2025/8/17 1:41:51

【文献笔记】LLM-based control code generation using image recognition

LLM-based control code generation using image recognition 原文代码标题翻译：基于图像识别的LLM控制代码生成 1. 内容介绍 1.1. 简介论文提出了一种基于LLM的新方法，通过图像识别从管道仪表图（Piping and Instrumentation Diagrams,…...

编程日记 2025/8/17 13:01:54

算法之贪心算法

贪心算法贪心算法核心思想常见应用场景典型案例案例一：找零问题案例二：活动选择问题案例三：货仓选址问题贪心算法的应用详解霍夫曼编码最小生成树Dijkstra最短路径算法总结贪心算法核心思想贪心算法（Greedy Algorithm&…...

编程日记 2025/8/17 20:46:30

从“链主”到“全链”：供应链数字化转型的底层逻辑

1. 制造业与供应链数字化转型的必然性 1.1. 核心概念与战略重要性制造业的数字化转型，是利用新一代数字技术（如工业互联网、人工智能、大数据、云计算、边缘计算等）对制造业的整体价值链进行根本性重塑的过程。这不仅涉及技术的应用&#…...

编程日记 2025/8/17 20:31:00

【Windows本地部署n8n工作流自动平台结合内网穿透远程在线访问】

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kwan 的首页,持续学…...

编程日记 2025/8/17 20:54:32

Python中如何加密/解密敏感信息（如用户密码、token）

敏感信息，如用户密码、API密钥、访问令牌（token）、信用卡号以及其他个人身份信息（PII），构成了现代应用程序和系统中最为关键的部分。这些信息一旦被未经授权的第三方获取，可能引发灾难性的后果，从个人隐私泄露到企业经济损失，甚至是大规模的社会安全问题。保护这些敏感…...

编程日记 2025/8/17 19:54:32

Win10如何一键切换IP地址教程

切换IP地址可能对于许多用户来说是一个相对陌生但又可能经常需要进行的操作。无论是出于网络安全、突破网络限制还是仅仅为了测试目的，一键切换IP地址都能带来极大的便利。以下是在 Windows 10 中通过批处理脚本实现一键切换 IP 地址的详细教程： 方法一&…...

编程日记 2025/8/17 20:24:27

2021-11-09 C++三位数平方含有该数

缘由求解，运算函数，哪位大神教一下-编程语言-CSDN问答 void 三位数平方含有该数() {//缘由https://ask.csdn.net/questions/7560152?spm1005.2025.3001.5141int a 100, aa 1000, f 0;while (a < aa){f a*a;while (f > a)if ((f - a) % aa)f …...

编程日记 2025/8/17 18:17:12

高效检测书签网址，告别无效链接烦恼

软件介绍你是否有过面对浏览器中满满的书签，却不知道哪些网址还“健在”，哪些已经“跑路”的烦恼？别担心，今天就给大家介绍一款神奇的小工具——“网址小卫士”。检测轻松搞定还在一个个手动检查书签网址的有效性吗&#xf…...

编程日记 2025/8/17 19:52:37

SpringBoot高校学生评教系统设计实现

概述基于SpringBoot的高校学生评教系统项目，该系统包含了学生评教、教师管理等功能，适合作为JavaWeb学习项目。主要内容 1. 学生功能模块查看评教信息：可以查看学期、院系、任课教师、课程名称等信息评价打分功能：可以对课…...

编程日记 2025/8/17 21:18:16

代码随想录算法训练营第二十天

LeetCode题目: 39. 组合总和40. 组合总和 II131. 分割回文串2176. 统计数组中相等且可以被整除的数对(每日一题) 其他: 今日总结往期打卡 39. 组合总和跳转: 39. 组合总和学习: 代码随想录公开讲解问题: 给你一个无重复元素的整数数组 candidates 和一个目标整数 targ…...

编程日记 2025/8/17 4:42:29

C++入门基础：命名空间，缺省参数，函数重载，输入输出

命名空间： C语言是基于C语言的，融入了面向对象编程思想，有了很多有用的库，所以接下来我们将学习C如何优化C语言的不足的。在C/C语言实践中，在全局作用域中变量，函数，类会有很多，这…...

编程日记 2025/8/17 20:46:44

GPU怎么绑定到服务器上

确认服务器与 GPU 兼容性1：不同的服务器和 GPU 型号连接方式有所不同，要确保所选的 GPU 卡与服务器兼容。可通过服务器和 GPU 的产品文档，或使用服务器厂商提供的兼容性查询工具进行确认。安装前准备：关闭服务器电源，并…...

编程日记 2025/8/17 20:18:58

opencv函数展示2

一、像素操作与算术运算 1.cv2.split() 2. cv2.merge() 3.cv2.add() 4.cv2.bitwise_and() 5.cv2.bitwise_or() 6.cv2.inRange() 二、仿射变换 1.cv2.getRotationMatrix2D() 2.cv2.warpAffine() 3.cv2.flip() 4.cv2.resize() 三、透视变换 1.cv2.getPerspectiveTransform() 2…...

编程日记 2025/8/17 20:54:27

零基础上手Python数据分析 (16)：DataFrame 常用统计分析方法

写在前面 —— 超越简单排序，探索数据内在规律，掌握Pandas统计分析基础上一篇博客，我们学习了如何使用 Pandas 对 DataFrame 进行排序和排名，这使得我们能够更好地组织数据并快速定位关键信息。然而，仅仅对数据进行排序和排名，还不足以完全理解数据。要想更深入地解…...

编程日记 2025/8/17 21:37:26

文件系统软硬连接

🌻个人主页：路飞雪吖~ 🌠专栏：Linux 目录一、理解文件系统 🌠磁盘结构二、软硬连接 🌟软硬链接 🌠软链接： 🌠硬链接： 🌟理解软硬链接的应…...

编程日记 2025/8/17 21:00:53

Linux环境基础开发工具使用

本节目标： 1. 学习yum工具，进行软件安装 2. 掌握vim编辑器使用，学会vim的简单配置 3. 掌握gcc/g编译器的使用，并了解其过程，原理 4. 掌握简单gdb使用于调试 5. 掌握简单的Makefile编写，了解其运行思想…...

编程日记 2025/8/17 20:03:39

秘密任务 2.0：如何利用 WebSockets + DTOs 设计实时操作

在之前的文章中，我们探讨了为什么 DTO 是提升 API 效率和安全性的秘密武器。现在，我们进入了一个全新的场景——我们将深入探讨如何通过 WebSockets DTOs 实现实时操作！ Agent X 正在进行一项高风险的卧底任务。突然，总部更新了…...

编程日记 2025/8/17 20:40:25

LeetCode hot 100—括号生成

题目数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。示例示例 1： 输入：n 3 输出：["((()))","(()())","(())()","()(())",&…...

编程日记 2025/8/17 8:02:12

2025.04.17【Dendrogram】生信数据可视化：Dendrogram图表详解

Dendrogram customization Go further with ggraph: edge style, general layout, node features, adding labels, and more. Customized circular dendrogram Learn how to build a circular dendrogram with proper labels. 文章目录 Dendrogram customizationCustomized c…...

编程日记 2025/8/17 18:17:07

题目