【左程云算法全讲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…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...
2.2.2 ASPICE的需求分析
ASPICE的需求分析是汽车软件开发过程中至关重要的一环,它涉及到对需求进行详细分析、验证和确认,以确保软件产品能够满足客户和用户的需求。在ASPICE中,需求分析的关键步骤包括: 需求细化:将从需求收集阶段获得的高层需…...
react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
【QT控件】显示类控件
目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏:QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...
记一次spark在docker本地启动报错
1,背景 在docker中部署spark服务和调用spark服务的微服务,微服务之间通过fegin调用 2,问题,docker容器中服务器来后,注册中心都有,调用服务也正常,但是调用spark启动任务后报错,报错…...
