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

Leecode刷题C语言之超过阈值的最小操作数②

执行结果:通过

执行用时和内存消耗如下:

 

 

 

// 最小堆的节点结构体
typedef struct {long long* heap;int size;int capacity;
} MinHeap;// 初始化最小堆
MinHeap* createMinHeap(int capacity) {MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->heap = (long long*)malloc(capacity * sizeof(long long));return minHeap;
}// 插入元素到最小堆
void insert(MinHeap* minHeap, long long value) {if (minHeap->size == minHeap->capacity) {return; // 堆已满}int i = minHeap->size++;while (i != 0 && value < minHeap->heap[(i - 1) / 2]) {minHeap->heap[i] = minHeap->heap[(i - 1) / 2];i = (i - 1) / 2;}minHeap->heap[i] = value;
}// 移除并返回最小堆的最小元素
long long extractMin(MinHeap* minHeap) {if (minHeap->size <= 0) {return -1;}if (minHeap->size == 1) {minHeap->size--;return minHeap->heap[0];}long long root = minHeap->heap[0];minHeap->heap[0] = minHeap->heap[--minHeap->size];int i = 0;while (2 * i + 1 < minHeap->size) {int leftChild = 2 * i + 1;int rightChild = 2 * i + 2;int smallest = i;if (leftChild < minHeap->size && minHeap->heap[leftChild] < minHeap->heap[smallest]) {smallest = leftChild;}if (rightChild < minHeap->size && minHeap->heap[rightChild] < minHeap->heap[smallest]) {smallest = rightChild;}if (smallest != i) {long long temp = minHeap->heap[smallest];minHeap->heap[smallest] = minHeap->heap[i];minHeap->heap[i] = temp;i = smallest;} else {break;}}return root;
}// 释放最小堆内存
void freeMinHeap(MinHeap* minHeap) {free(minHeap->heap);free(minHeap);
}int minOperations(int* nums, int numsSize, int k) {MinHeap* minHeap = createMinHeap(numsSize);for (int i = 0; i < numsSize; ++i) {insert(minHeap, nums[i]);}int operations = 0;while (minHeap->size >= 2 && minHeap->heap[0] < k) {long long x = extractMin(minHeap);long long y = extractMin(minHeap);long long newValue = x * 2 + y;insert(minHeap, newValue);++operations;}freeMinHeap(minHeap);return operations;
}

解题思路:

这段代码实现了一个最小堆数据结构,并利用它来解决一个特定的问题:给定一个整数数组 nums 和一个整数 k,计算将数组中的元素通过一系列操作转换成大于或等于 k 的最小元素所需的最少操作次数。每次操作可以取出堆中的两个最小元素,将它们相加后乘以2,再将结果放回堆中。

下面是代码的解题思路:

  1. 定义最小堆结构体
    • MinHeap 结构体包含三个成员:指向堆数组的指针 heap,堆的当前大小 size,以及堆的容量 capacity
  2. 初始化最小堆
    • createMinHeap 函数分配内存并初始化一个最小堆,设置堆的大小为0,并分配足够的空间来存储指定容量的元素。
  3. 插入元素到最小堆
    • insert 函数将一个新元素添加到最小堆中。如果堆未满,它首先将元素添加到堆的末尾,然后通过上滤(bubble up)操作将其移动到正确的位置,以保持堆的性质。
  4. 移除并返回最小元素
    • extractMin 函数移除并返回堆中的最小元素(根元素)。它首先将根元素替换为堆中的最后一个元素,然后通过下滤(bubble down)操作将新的根元素移动到正确的位置。
  5. 释放最小堆内存
    • freeMinHeap 函数释放最小堆所占用的内存。
  6. 计算最少操作次数
    • minOperations 函数是解决问题的核心。它首先创建一个最小堆,并将数组 nums 中的所有元素插入堆中。
    • 然后,它进入一个循环,只要堆的大小至少为2且堆顶元素(最小元素)小于 k,就执行以下操作:
      • 从堆中取出两个最小元素 x 和 y
      • 计算新值 newValue = x * 2 + y
      • 将 newValue 插入堆中。
      • 操作次数 operations 加1。
    • 循环结束后,释放堆的内存,并返回操作次数 operations

这种方法利用了最小堆的性质,确保了每次操作都能有效地处理当前最小的元素,从而以尽可能少的操作次数达到目标值 k

相关文章:

Leecode刷题C语言之超过阈值的最小操作数②

执行结果:通过 执行用时和内存消耗如下&#xff1a; // 最小堆的节点结构体 typedef struct {long long* heap;int size;int capacity; } MinHeap;// 初始化最小堆 MinHeap* createMinHeap(int capacity) {MinHeap* minHeap (MinHeap*)malloc(sizeof(MinHeap));minHeap->s…...

【Linux】11.Linux基础开发工具使用(4)

文章目录 3. Linux调试器-gdb使用3.1 背景3.2 下载安装3.3 使用gdb查询3.4 开始使用 3. Linux调试器-gdb使用 3.1 背景 程序的发布方式有两种&#xff0c;debug模式和release模式 Linux gcc/g出来的二进制程序&#xff0c;默认是release模式 要使用gdb调试&#xff0c;必须…...

Cesium中的CustomDataSource 详解

Cesium CustomDataSource 详解 在 Cesium 中&#xff0c;CustomDataSource 是一个强大的类&#xff0c;用于处理自定义的地理数据。它提供了一种方法&#xff0c;可以通过程序方式添加、管理和更新动态的地理实体&#xff0c;而无需依赖外部数据格式&#xff08;如 GeoJSON 或…...

win32汇编环境,窗口程序中组合框的应用举例

;运行效果 ;win32汇编环境,窗口程序中组合框的应用举例 ;比如在窗口程序中生成组合框&#xff0c;增加子项&#xff0c;删除某项&#xff0c;取得指定项内容等 ;直接抄进RadAsm可编译运行。重点部分加备注。 ;以下是ASM文件 ;>>>>>>>>>>>>…...

Wireshark 使用教程:网络分析从入门到精通

一、引言 在网络技术的广阔领域中&#xff0c;网络协议分析是一项至关重要的技能。Wireshark 作为一款开源且功能强大的网络协议分析工具&#xff0c;被广泛应用于网络故障排查、网络安全检测以及网络协议研究等诸多方面。本文将深入且详细地介绍 Wireshark 的使用方法&#x…...

菜品管理(day03)

公共字段自动填充 问题分析 业务表中的公共字段&#xff1a; 而针对于这些字段&#xff0c;我们的赋值方式为&#xff1a; 在新增数据时, 将createTime、updateTime 设置为当前时间, createUser、updateUser设置为当前登录用户ID。 在更新数据时, 将updateTime 设置为当前时间…...

Scira - 一个极简的开源 AI 搜索引擎

支持实时搜索 、学术论文分析 、社交媒体洞察 、YouTube 搜索 、航班追踪 、电影搜索&#xff0c;功能倒是挺多。 但是目前只支持 xAI 的 Grok 还不能换模型&#xff0c;不过用的 Vercel SDK 支持下 DeepSeek 应该很容易 https://index.html.zone/ai/scira...

利用源码安装httpd

方法一&#xff1a; 1&#xff0c;下载源码 [rootopenEuler-1 ~]# wget https://archive.apache.org/dist/httpd/httpd-2.4.46.tar.gz [rootopenEuler-1 ~]# ls anaconda-ks.cfg httpd-2.4.46.tar.gz mysql-8.0.36-linux-glibc2.12-x86_64.tar.xz 2&#xff0c;进行压缩 […...

软件测试 —— Selenium(等待)

软件测试 —— Selenium&#xff08;等待&#xff09; 一个例子强制等待使用示例&#xff1a;为什么不推荐使用强制等待&#xff1f;更好的选择 隐式等待 implicitly_wait&#xff08;&#xff09;隐式等待和强制等待的区别隐式等待&#xff08;Implicit Wait&#xff09;强制等…...

图像模糊度(清晰度)检测 EsFFT 算法详细分析

图像模糊度检测算法 基于频域的算法 傅里叶变换法:先将图像进行傅里叶变换得到频谱图,频谱图中心为低频,向外扩展为高频。通过屏蔽频谱图中心区域实现高通滤波,保留图像边缘等高频信息,再求频谱图的均值即平均高频幅值,该值越小,图像越模糊。但传统FFT方法存在不足,如…...

快速上手 HarmonyOS 应用开发

一、DevEco Studio 安装与配置 1. DevEco Studio 简介 DevEco Studio 是 HarmonyOS 的一站式集成开发环境&#xff08;IDE&#xff09;&#xff0c;提供了丰富的工具和功能&#xff0c;支持 HarmonyOS 应用开发的全流程。 2. DevEco Studio 下载与安装 下载地址&#xff1a…...

金融项目实战 06|Python实现接口自动化——日志、实名认证和开户接口

目录 一、日志封装及应用&#xff08;理解&#xff09; 二、认证开户接口脚本编写 1、代码编写 1️⃣api目录 2️⃣script目录 2、BeautifulSoup库 1️⃣简介及例子 2️⃣提取html数据工具封装 3、认证开户参数化 一、日志封装及应用&#xff08;理解&#xff09; &…...

Lianwei 安全周报|2025.1.13

新的一周又开始了&#xff0c;以下是本周「Lianwei周报」&#xff0c;我们总结推荐了本周的政策/标准/指南最新动态、热点资讯和安全事件&#xff0c;保证大家不错过本周的每一个重点&#xff01; 政策/标准/指南最新动态 01 美国国土安全部发布《公共部门生成式人工智能部署手…...

【C#深度学习之路】如何使用C#实现Yolo8/11 Segment 全尺寸模型的训练和推理

【C#深度学习之路】如何使用C#实现Yolo8/11 Segment 全尺寸模型的训练和推理 项目背景项目实现推理过程训练过程 项目展望写在最后项目下载链接 本文为原创文章&#xff0c;若需要转载&#xff0c;请注明出处。 原文地址&#xff1a;https://blog.csdn.net/qq_30270773/article…...

【Compose multiplatform教程】05 IOS环境编译

了解如何使现有的 Android 应用程序跨平台&#xff0c;以便它在 Android 和 iOS 上都能运行。您将能够在一个位置编写代码并针对 Android 和 iOS 进行测试一次。 本教程使用一个示例 Android 应用程序&#xff0c;其中包含用于输入用户名和密码的单个屏幕。凭证经过验证并保存…...

【声音场景分类--论文阅读】

1.基于小波时频图特征在声音场景分类 基于小波时频图特征在声音场景分类任务中的表现 2.增强增强高效音频分类网络 https://arxiv.org/pdf/2204.11479v5 https://github.com/Alibaba-MIIL/AudioClassfication 音频分类网络如图4所示。在此阶段&#xff0c;主要重点是建立一…...

浅谈云计算02 | 云计算模式的演进

云计算计算模式的演进 一、云计算计算模式的起源追溯1.2 个人计算机与桌面计算 二、云计算计算模式的发展阶段2.1 效用计算的出现2.2 客户机/服务器模式2.3 集群计算2.4 服务计算2.5 分布式计算2.6 网格计算 三、云计算计算模式的成熟与多元化3.1 主流云计算服务模式的确立3.1.…...

【专题】2025年节日营销趋势洞察报告汇总PDF洞察(附原数据表)

原文链接&#xff1a; https://tecdat.cn/?p38813 在当今复杂多变且竞争激烈的消费市场环境下&#xff0c;节日营销已成为企业获取市场份额、提升品牌影响力的关键战略时机。我们深知深入洞察节日营销趋势对于企业决策的重要性。 本报告汇总基于对 2024 年多个关键消费节点及…...

AR 在高校实验室安全教育中的应用

AR应用APP可以内置实验室安全功能介绍&#xff0c;学习并考试&#xff08;为满足教育部关于实验室人员准入条件&#xff09;&#xff0c;AR主模块。其中AR主模块应该包括图形标识码的扫描&#xff0c;生成相应模型&#xff0c;或者火灾、逃生等应急处置的路线及动画演示。考试采…...

PHP智慧小区物业管理小程序

&#x1f31f;智慧小区物业管理小程序&#xff1a;重塑社区生活&#xff0c;开启便捷高效新篇章 &#x1f31f; 智慧小区物业管理小程序是一款基于PHPUniApp精心雕琢的智慧小区物业管理小程序&#xff0c;它犹如一股清新的科技之风&#xff0c;吹进了现代智慧小区的每一个角落…...

使用防抖与节流优化 Vue 中的异步函数调用

使用防抖与节流优化 Vue 中的异步函数调用 在 Vue 项目中&#xff0c;我们经常需要处理用户交互事件&#xff0c;例如点击、输入、切换复选框等。这些事件可能频繁触发&#xff0c;尤其在用户快速操作的情况下&#xff0c;如果每次触发都执行复杂的逻辑&#xff08;如异步网络…...

【大厂面试AI算法题中的知识点】方向涉及:ML/DL/CV/NLP/大数据...本篇介绍自动驾驶检测模型如何针对corner case 优化?

【大厂面试AI算法题中的知识点】方向涉及&#xff1a;ML/DL/CV/NLP/大数据…本篇介绍自动驾驶检测模型如何针对corner case 优化&#xff1f; 【大厂面试AI算法题中的知识点】方向涉及&#xff1a;ML/DL/CV/NLP/大数据…本篇介绍自动驾驶检测模型如何针对corner case 优化&…...

Android CustomTextField

在 Compose 中开发用户界面时&#xff0c;需要处理输入框和键盘的交互&#xff0c;例如在键盘弹出时调整布局位置&#xff0c;避免遮挡重要内容。本篇博客将通过一个完整的示例展示如何实现这一功能。 功能概述 本例实现了一个简单的输入框。当输入框获得焦点或输入文字时&…...

源码编译安装httpd 2.4,提供系统服务管理脚本并测试(两种方法实现)

一、源码编译安装httpd 2.4 # 从官网下载httpd源代码 [rootopenEuler-2 ~]# wget https://downloads.apache.org/httpd/httpd-2.4.62.tar.gz# 解压并进入到该目录中 [rootopenEuler-2 ~]# tar -zxvf httpd-2.4.62.tar.gz [rootopenEuler-2 ~]# cd httpd-2.4.62/# 安装httpd编译…...

ubuntu24.04安装docker显卡工具包nvidia-container-toolkit

问题描述 docker 容器启动时如果需要访问 gpu &#xff0c;需要安装 nvidia-container-toolkit 才行&#xff0c;否则会提示如下错误 sudo docker run --rm -it --gpus all ubuntu:latest docker: Error response from daemon: could not select device driver "" …...

mac intel芯片下载安卓模拟器

一、调研 目前主流两个模拟器&#xff1a; 雷神模拟器 不支持macosmumu模拟器pro版 不支持macos intel芯片 搜索到mumu的Q&A中有 “Intel芯片Mac如何安装MuMu&#xff1f;” q&a&#x1f517;&#xff1a;https://mumu.163.com/mac/faq/install-on-intel-mac.html 提…...

4 原型(Protoytpe)模式

原型模式 1.1 分类 &#xff08;对象&#xff09;创建型 1.2 提出问题 希望复制一个状态完全相同的对象。首先&#xff0c;新建一个相同类的对象。 然后&#xff0c;复制所有成员变量。 但是&#xff0c;有时候不知道具体类型&#xff0c;而且成员变量可能是私有的。&#…...

kafka的listeners和advertised.listeners,配置内外网分流

总结&#xff1a; listeners 指明 kafka 当前节点监听本机的哪个网卡 advertised.listeners 指明客户端通过哪个 ip 可以访问到当前节点 内网和外网并不必须是是我们通常说的公司内部网络和公网&#xff0c;只要是两块网卡都可以&#xff0c;不管是这两块网卡是公网、内网、甚至…...

Mac——Docker desktop安装与使用教程

摘要 本文是一篇关于Mac系统下Docker Desktop安装与使用教程的博文。首先介绍连接WiFi网络&#xff0c;然后详细阐述了如何在Mac上安装Docker&#xff0c;包括下载地址以及不同芯片版本的选择。接着讲解了如何下载基础镜像和指定版本镜像&#xff0c;旨在帮助用户在Mac上高效使…...

Redis十大数据类型详解

Redis&#xff08;一&#xff09; 十大数据类型 redis字符串&#xff08;String&#xff09; string是redis最基本的类型&#xff0c;一个key对应一个value string类型是二进制安全的&#xff0c;意思是redis的string可以包含任何数据。例如说是jpg图片或者序列化对象 一个re…...

.net core 中使用AsyncLocal传递变量

官网 https://github.com/dotnet/runtime/blob/16b6369b7509e58c35431f05681a9f9e5d10afaa/src/libraries/System.Private.CoreLib/src/System/Threading/AsyncLocal.cs#L45 AsyncLocal是一个在.NET中用来在同步任务和异步任务中保持全局变量的工具类。它允许你在不同线程的同…...

C#Halcon视觉流程框架个人封装流程心得

一&#xff0c;实现效果 1&#xff0c;初始界面 2&#xff0c;加载流程 3&#xff0c;点击流程列表“加载2D图像" 4&#xff0c;设置图像预处理参数与画线找线 5&#xff0c;执行流程 6&#xff0c;折叠工具箱 7&#xff0c;折叠操作区域 二&#xff0c;实现流程 1&…...

web第一次作业

系统登录代码&#xff1a; <!DOCTYPE html> <html lang"zh"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>第一次作业</title…...

Kylin Linux V10 替换安装源,并在服务器上启用 EPEL 仓库

查看系统版本&#xff1a; cat /etc/os-releaseNAME"Kylin Linux Advanced Server" VERSION"V10 (Lance)" ID"kylin" VERSION_ID"V10" PRETTY_NAME"Kylin Linux Advanced Server V10 (Lance)" ANSI_COLOR"0;31"u…...

备战蓝桥杯:树的存储与遍历(dfs和bfs)

树的概念 树的逻辑结构是树形结构&#xff0c;和我们之前的线性结构又不太一样了&#xff0c;是一种一对多的关系 树的结点分为根节点&#xff0c;叶子结点&#xff08;没有分支的结点&#xff09; 以及分支结点 从上往下看&#xff0c;每个结点都有0个或多个后继 从下往上…...

[Deep Learning] Anaconda+CUDA+CuDNN+Pytorch(GPU)环境配置-2025

文章目录 [Deep Learning] AnacondaCUDACuDNNPytorch(GPU)环境配置-20250. 引子1. 安装Anaconda1.1 安装包下载&#xff1a;1.2 启用安装包安装1.3 配置(系统)环境变量1.4 验证Anaconda是否安装完毕1.5 Anaconda换源 2. 安装CUDACuDNN2.1 判断本机的CUDA版本2.2 下载适合自己CU…...

计算机的错误计算(二百一十二)

摘要 利用两个大模型计算 实验表明&#xff0c;两个大模型均进行了中肯的分析。另外&#xff0c;其中一个大模型给出了 Python代码&#xff0c;运行后&#xff0c;结果中有7位错误数字&#xff1b;而一个大模型进行加减运算时出错。 例1. 计算 下面是与一个大模型的对话…...

Inxpect毫米波安全雷达:精准检测与动态保护,工业自动化可靠选择

Inxpect毫米波安全雷达具备“精准检测、动态区域保护、环境适应性”三大核心功能。在工业自动化和机器人系统里&#xff0c;这些功能发挥着重要作用,有助于提升安全性与效率。Inxpect雷达运用毫米波技术&#xff0c;在诸如存在灰尘、烟雾或碎屑等复杂环境中&#xff0c;也能保持…...

springboot房屋租赁管理系统

Spring Boot房屋租赁管理系统是一种基于Spring Boot框架构建的&#xff0c;旨在解决传统租房市场中房源信息更新不及时、虚假信息泛滥、交易流程繁琐等问题的信息化解决方案。 一、系统背景与目的 随着城市化进程的加快和人口流动性的增强&#xff0c;租房市场需求急剧增长。…...

如何使用wireshark 解密TLS-SSL报文

目录 前言 原理 操作 前言 现在网站都是https 或者 很多站点都支持 http2。这些站点为了保证数据的安全都通过TLS/SSL 加密过&#xff0c;用wireshark 并不能很好的去解析报文&#xff0c;我们就需要用wireshark去解密这些报文。我主要讲解下mac 在 chrome 怎么配置的&…...

Gensim字典和语料库

自然语言处理(NLP)是计算机科学中涉及语言数据处理的核心领域之一,应用广泛,包括文本分类、情感分析、机器翻译、主题建模等任务。在处理海量文本时,如何将非结构化的语言数据转化为机器能够理解的结构化数据,是解决这些任务的关键。 Gensim 是一个用于处理和分析文本数…...

RK3588-NPU pytorch-image-models 模型编译测试

RK3588-NPU pytorch-image-models 模型编译测试 一.背景二.操作步骤1.下载依赖2.创建容器3.安装依赖4.创建脚本A.生成模型名列表B.生成ONNX模型C.生成RKNN模型D.批量测试脚本 一.背景 测试RK3588-NPU对https://github.com/huggingface/pytorch-image-models.git中模型的支持程…...

Doris 导入慢该如何排查及优化?

在使用 Apache Doris 进行数据导入时&#xff0c;经常会遇到导入性能不理想的情况。今天我们就来深入分析这些问题的原因及其解决方案&#xff01; Stream Load 导入慢 Stream Load 支持通过 HTTP 协议将本地文件或数据流导入到 Doris 中的一种方式&#xff0c;其速度还是相当…...

iOS - 关联对象的实现

根据源码总结一下关联对象(Associated Objects)的实现&#xff1a; 1. 关联对象的基本结构 // 对象的 isa 结构中包含关联对象标记 union isa_t {struct {uintptr_t nonpointer : 1; // 是否使用优化的 isauintptr_t has_assoc : 1; // 是否有关联对象// ...其他位…...

AudioGPT全新的 音频内容理解与生成系统

AudioGPT全新的 音频内容理解与生成系统 ChatGPT、GPT-4等大型语言模型 (LLM) 在语言理解、生成、交互和推理方面表现出的非凡能力,引起了学界和业界的极大关注,也让人们看到了LLM在构建通用人工智能 (AGI) 系统方面的潜力。 现有的GPT模型具有极高的语言生成能力,是目前最…...

【maptalks】加载SVG和GIF

加载SVG和GIF 一、加载SVG方法一&#xff1a;直接载入SVG文件&#xff0c;类似载入图片方法二&#xff1a;载入SVG路径 二、加载GIFVUEmaptalks实现GIF可拖拽点VUEmaptalks实现GIF跟随线条动画 一、加载SVG 方法一&#xff1a;直接载入SVG文件&#xff0c;类似载入图片 缺点&…...

【HarmonyOS NEXT】鸿蒙跳转华为应用市场目标APP下载页

【HarmonyOS NEXT】鸿蒙跳转华为应用市场目标APP下载页 一、问题背景&#xff1a; 如今&#xff0c;大家都离不开各种手机应用。随着鸿蒙系统用户越来越多&#xff0c;大家都希望能在鸿蒙设备上快速找到想用的 APP。华为应用市场里有海量的 APP&#xff0c;但之前从鸿蒙设备进…...

《leetcode-runner》【图解】如何手搓一个debug调试器——调试程序【JDI开发】【万字详解】

前文&#xff1a; 《leetcode-runner》如何手搓一个debug调试器——引言 《leetcode-runner》如何手搓一个debug调试器——架构 《leetcode-runner》如何手搓一个debug调试器——指令系统 本文主要聚焦于如何编写调试程序 背景 在leetcode算法背景下&#xff0c;用户只编写了…...

【高阶数据结构】线段树加乘(维护序列)详细解释乘与加懒标记

文章目录 1.题目[AHOI2009] 维护序列 2.懒标记处理先加后乘的形式1. 先加后乘的操作 先乘后加的形式2. 先乘后加的操作**乘法操作****加法操作** 懒标记的下传 3.代码 1.题目 题目来源:https://www.luogu.com.cn/problem/P2023 [AHOI2009] 维护序列 题目背景 老师交给小可可…...

ElasticSearch常见知识点

1、什么是ElasticSearch&#xff1f; Elasticsearch 是基于 Lucene 的 Restful 的分布式实时全文搜索引擎&#xff0c;每个字段都被索引并可被搜索&#xff0c;可以快速存储、搜索、分析海量的数据。 2、什么是倒排索引&#xff1f; 正常的索引是比如二叉树。倒排索引是用内容…...