【左程云算法全讲4】比较器和堆
系列综述:
💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。
🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考各平台大佬的文章,其中也可能含有少量的个人实验自证。
🤭结语:如果有帮到你的地方,就点个赞和关注一下呗,谢谢🎈🎄🌷!!!
🌈【C++】秋招&实习面经汇总篇
文章目录
- 堆
- 比较器
- 参考博客
😊点此到文末惊喜↩︎
堆
- 完全二叉树的数组表示,当前结点下标为i(第0位不用,从而可以使用移位操作进行快速处理)
- 左孩子: 2 ∗ i ⟺ ( i < < 1 ) 2 * i \iff (i << 1) 2∗i⟺(i<<1)
- 右孩子: 2 ∗ i + 1 ⟺ ( i < < 1 ∣ 1 ) 2 * i + 1 \iff (i << 1 | 1) 2∗i+1⟺(i<<1∣1)
- 父结点: ( i ) / 2 ⟺ ( i > > 1 ) (i) / 2 \iff (i >> 1) (i)/2⟺(i>>1)
- 堆
- 通过下沉和上浮操作,进行处理
// 插入底部,插入结点自底向上上浮
void HeapUp(vector<int> &vec, int index) {// 若当前结点大于父亲结点,则交换while (vec[index] > vec[(index - 1) / 2]) {swap(vec[index], vec[(index - 1) / 2]);index = (index-1) / 2;}
}// 弹出根节点,插入结点自顶向下下沉
void HeapDown(vector<int> &vec, int index, int heap_size) {int left = index * 2 + 1;while (left < heap_size) { // 表示孩子,即至少有一个左孩子// 有右孩子 && 右孩子值大于左孩子 则最大下标为右孩子,否则是左孩子int largest = left + 1 < heap_size && vec[left+1] > vec[left] ? left+1 : left;// largest中存储自己和左右孩子中最大的largest = vec[largest] > vec[index] ? largest : index;if (largest == index) break; // 如果是根结点则停止swap(vec[largest], vec[index]);// 迭代条件index = largest;left = index * 2 + 1;}
}
// 堆排序
void HeapSort(vector<int> vec) {if (vec.empty() || vec.size() < 2) return ;// 依次将每个数插入,建立大根堆for (int i = 0; i < vec.size(); ++i) {HeapUp(vec, i);}// 每次将大根堆的堆顶元素与数组尾元素交换int heap_size = vec.size();swap(vec[0], vec[--heap_size]);while (heap_size > 0) {HeapDown(vec[0], vec[head_size]);swap(vec[0], vec[--heap_size]);}
}
- 已知一个几乎有序的数组, 若把数组排好序,每个元素移动的距离一定不超过k,并且k相对与数组长度比较小
- 将前k个数放入小根堆中,每次弹出一个堆顶元素,并将下一个数加入堆中
在这里插入代码片
比较器
- 比较器
- 原理:通过重载比较运算符,然后进行两个元素的按某种条件的大小比较
- 优点:可用于泛型编程
- 自定义cmp函数,传入堆中,从而实现自定义的比较
🚩点此跳转到首行↩︎
参考博客
- 对数器
- 单调队列
- 快速链表quicklist
- 《深入理解计算机系统》
- 侯捷C++全系列视频
- 待定引用
- 待定引用
- 待定引用
相关文章:
【左程云算法全讲4】比较器和堆
系列综述: 💞目的:本系列是个人整理为了秋招面试的,整理期间苛求每个知识点,平衡理解简易度与深入程度。 🥰来源:材料主要源于左程云算法课程进行的,每个知识点的修正和深入主要参考…...
【计算机组成与设计】Chisel取指和指令译码设计
本次试验分为三个部分: 目录 设计译码电路 设计寄存器文件 实现一个32个字的指令存储器 设计译码电路 输入位32bit的一个机器字,按照课本MIPS 指令格式,完成add、sub、lw、sw指令译码,其他指令一律译码成nop指令。输入信号名…...
「Verilog学习笔记」位拆分与运算
专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点,刷题网站用的是牛客网 1、寄存器的位是可以分开单独运算的,并不是一个输入就一定是一个数据,在很多情况下,一个输入既包括数据又包括地址等其他有效信息 2、需…...
protobufjs实现protobuf序列化与反序列化
系列文章目录 websocket训练地址:https://www.qiulianmao.com,正在搭建中 基础-websocket逆向基础-http拦截基础-websocket拦截基础-base64编码与解码基础-python实现protobuf序列化与反序列化基础-前端js实现protobuf序列化与反序列化基础-protobufjs实现protobuf序列化与反…...
el-select多选以tag展示时,超过显示长度以...省略号显示,且在一行展示
效果: 代码: <span>系统词典维度:</span><el-selectv-model"dNum"placeholder"请选择"multiplecollapse-tags //设置collapse-tags属性将它们合并为一段文字size"small"style"width:160p…...
计算机网络第4章-通用转发和SDN
引子: 在前面,我们将基于目的地转发的特征总结为两个步骤: 查找目的IP地址(匹配),然后将分组发送到有特定输出端口的交换结构(“动作”)。 但是这种转发特征会带来许多问题&#…...
DDD技术方案落地实践 | 京东云技术团队
1. 引言 从接触领域驱动设计的初学阶段,到实现一个旧系统改造到DDD模型,再到按DDD规范落地的3个的项目。对于领域驱动模型设计研发,从开始的各种疑惑到吸收各种先进的理念,目前在技术实施这一块已经基本比较成熟。在既往经验中总…...
MySQL 案例:update set 和 and 的坑
问题描述 最近碰到到一个奇怪的问题,update 语句执行没有报错,但是没有更新数据,具体有问题的语句类似于如下形式: update test.stu set cname 0 and math 90 and his 80 where id 100; 复制 原因分析 直观上看ÿ…...
VSCode remote-ssh 连接远端服务器失败
系统 Mac os Intel处理器 描述 该问题在上午时还没有,下午突然毫无征兆的发生,当时没有更新vscode,没有更新插件。 分析 网上对于该问题的答案多是说磁盘空间不够vscode不能下载相应插件,我所遇到的并不是这种情况。报的错误多是…...
通达信动量线MTM指标原理详解及MTM底背离选股公式
MTM指标(动量线指标)用于衡量价格的动量和趋势,以判断未来价格的变化。计算方法很简单,用当前价格减去一段时间(通常为12日)前的价格,计算得到的差值的正负和大小,可以判断可能的趋势…...
汇编-DUP操作符
DUP操作符使用整数表达式作为计数器, 为多个数据项分配存储空间。 在为字符串或数组分配存储空间时,这个操作符尤其有用,并且可以使用初始化或非初始化数据: .data BYTE 20 DUP(0) ;20个字节,都等于0 BYTE 20 …...
2311C++抽象工厂
1,为啥需要工厂设计模式?工厂设计模式可解决什么问题? 先看一下示例,多态示例. #include <iostream> using namespace std; class Shape { public:Shape() { }virtual void drawShape(){cout << "base draw shape" << endl;} }; class Rectang…...
Lavarel定时任务的使用
系统为window 执行命令(执行一次命令只会根据当前时间运行一次定时任务) php artisan schedule:run创建一个任务类(在Jobs文件夹下面) <?phpnamespace App\Jobs;use Illuminate\Bus\Queueable; use Illuminate\Contracts\Queue\ShouldBeUnique; use Illuminate\Contract…...
Java开发者的网络安全指南(二)
目录 一、加密和数据保护 二、身份验证和授权 三、Web应用程序安全 四、安全编码实践 五、网络防火墙和入侵检测系统 六、日志和监视 七、漏洞管理 八、安全教育和培训 九、结论 介绍: 简要说明网络安全的重要性和为什么Java开发者需要关注它。 一、加密…...
Python基础学习016__UnitTest
# UnitTest是python自带的一个单元测试框架,不需要额外安装 # 也是自动化脚本执行框架,使用UnitTest来管理,运行多个框架 # 为什么使用:能够组织多个用例去执行.提供了丰富的断言方法,能够生成测试报告 # 核心要素: # Testcase:测试用例:这个测试用例是UnitTest的组成部分,不是…...
一物一码需求,标签制作功能轻松解决
许多行业存在为人员、物品、设备等做一物一码标签的需求,可使用草料标签制作功能。直接选择标签样式,填入数据,即可批量生成标签,还可批量排版,更易落地。还可保存标签样式,后续多次复用样式,批…...
【Linux】七、基础IO
预备知识 文件 属性(本质上也是数据)内容; 文件的所有操作大致有两种,对内容的操作,和对属性的操作; 文件在磁盘中放置,磁盘是硬件,只有操作系统可以真正的访问磁盘;C\C…...
Elasticsearch语法之Term query不区分大小写
设置关键词是否区分大小写 说明:case_insensitive是term的可选参数,默认为false,表示关键词区分大小写,设置为true表示关键词不区分大小写。该参数在7.10.0开始有效 需求:分别使用关键词"iphone"和"I…...
远程管理SSH服务
一、搭建SSH服务 1、关闭防火墙与SELinux # 关闭firewalld防火墙 # 临时关闭 systemctl stop firewalld # 关闭开机自启动 systemctl disable firewalld # 关闭selinux # 临时关闭 setenforce 0 # 修改配置文件 永久关闭 vim /etc/selinux/config SELINUXdisabled 2、配置…...
Linux 实现原理 — NUMA 多核架构中的多线程调度开销与性能优化
前言 NOTE:本文中所指 “线程” 均为可执行调度单元 Kernel Thread。 NUMA 体系结构 NUMA(Non-Uniform Memory Access,非一致性存储器访问)的设计理念是将 CPU 和 Main Memory 进行分区自治(Local NUMA node&#x…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
