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

数据结构(面试)

目录

    • 线索二叉树
    • 哈夫曼树
    • 并查集
    • 最小生成树
    • 最短路径
    • 拓扑排序
    • 二叉排序树
    • 平衡二叉树
    • 红黑树
    • 折半查找
    • 散列表
    • 堆排序
    • 归并排序

线索二叉树

原理:利用树节点的n+1个左右空指针指向其遍历序列的前驱和后继(线索)
优点:简化遍历,不需要额外的栈空间,快速访问前驱的后继
在这里插入图片描述

哈夫曼树

哈夫曼树定义:在含有n个带权叶节点的二叉树中,其中带权路径(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树
带权路径长度:叶子节点×路径长度 的总和
构建方法:每次选取根节点最小的集合进行两两组合
在这里插入图片描述

并查集

用法:判断图中是否有环,判断是否在一个集合中
思想:使用一个parent[]数组存储集合关系,对集合进行并查操作
:找x所属集合(返回x所属根节点)
:将两个集合合并为一个
在这里插入图片描述
在这里插入图片描述
为了优化,出现最坏的情况,在合并集合的时候可以按秩合并

if(rank[x_root]>rank[y_root]){//将x作为根节点合并parent[y_root]=x_root;
}else{//将y作为根节点合并 rank[x_root]=y_root;if(rank[x_root]==rank[y_root]){//当秩相等时 rank[y_root]++;} 
} 

进一步优化,路径压缩,查找过程中将一个集合路径下的所有节点都挂到集合根节点下面

int find(int x){//找根节点if(x==parent[x])return x;//返回根节点 return parent[x]=find(parent[x]);//路径压缩 
} 

并查集模板代码:

#include<bits/stdc++.h>
using namespace std;
int parent[10005],rank[10005];
//找根节点 
int find(int x){if(x==parent[x])return x;//返回根节点 return parent[x]=find(parent[x]);//路径压缩 
}
//集合合并
void unionset(int x,int y){int x_root=find(x);int y_root=find(y);if(x_root==y_root)return;//在同一个集合中//按秩合并 if(rank[x_root]>rank[y_root]){parent[y_root]=x_root;	}else{parent[x_root]=y_root;if(rank[x_root]=rank[y_root]){rank[y_root]++;}}
}
//打印关系函数
void selectdots(){for(int i=1;i<=5;i++){printf("%d的根节点=%d\n",i,parent[i]);}
}int main(){//初始化 for(int i=0;i<100;i++){parent[i]=i;rank[i]=0;}//初始化两个集合 A{1 ←2 ←3}  B{4 ←5} ;int con[3][2]={{2,1},{3,2},{5,4}};for(int i=0;i<3;i++){unionset(con[i][0],con[i][1]);//建立集合 } printf("A{1 ←2 ←3}  B{4 ←5}两个集合没有合并:\n"); selectdots();printf("2和4点是否有关系:");if(find(2)==find(4)){cout<<true<<endl;;}else{cout<<false<<endl;}printf("\n\n增加3 ←5关系:\n");unionset(5,3);selectdots();printf("2和4点是否有关系:");if(find(2)==find(4)){cout<<true<<endl;;}else{cout<<false<<endl;}printf("\n\n查询一次5的根节点:\n");find(5);selectdots(); return 0;
}

最小生成树

生成树:包含图中全部顶点的一个极小联通子图
在这里插入图片描述
最小生成树:边权值之和最小的生成树
在这里插入图片描述
普利姆算法(选点,适合边稠密):
在这里插入图片描述
克鲁斯卡尔(选边,适合边稀疏):
在这里插入图片描述

最短路径

在这里插入图片描述
Dijkstra算法(带权图,无权图,不适用有负权值的图)
时间复杂度:O(|V|^2)
思想:
1.每次从未标记节点中选择距离出发点最近的节点,标记,收录到最优路径集合中。
2.计算刚加入节点A的邻近节点B的距离(不包含标记的节点),若(节点A的距离+节点A到节点B的边长)<节点B的距离,就进行松弛操作,更新节点B的距离

if((dis[A]+e[A][B])<dis[B]) dis[B] = dis[A] + e[A][B];

Floyd算法(带权图,无权图,负权图,不能解决负权回路的图)
时间复杂度:O(|V|^3)
算法思想:最开始允许经过1号中转,求任意两点最短距离中转,接下来只允许经过2号顶点中转…允许经过1~n号顶点中转
一句话概括:从i号顶点到j号顶点只经过前k号顶点的最短路径

for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(e[i][k]+e[k][j]<e[i][j]){e[i][j]=e[i][k]+e[k][j];}}}} 

拓扑排序

思想,每次选择入度为0的顶点,加入排序序列,并删除所有出边
下面拓扑排序为:1,2,3,4,5
在这里插入图片描述

二叉排序树

定义:左子树节点值<根节点<右子树节点值
查找效率:最好O(logn) 最坏O(n)
在这里插入图片描述

在这里插入图片描述

平衡二叉树

定义:二叉排序树上任一节点的左子树和右子树的高度之差不超过1
缺点:插入/删除 很容易破坏“平衡”特性,需要频繁调整树的形态。如:插入操作导致不平衡,则需要先计算平衡因子,找到最小不平衡子树(时间开销大),再进行LL/RR/LR/RL调整
在这里插入图片描述

红黑树

在这里插入图片描述
**红黑树**:插入/删除 很多时候不会破坏“红黑特性”,无需频繁调整树的形态。即便需要调整,一般可以在常量级时间内完成

在这里插入图片描述
平衡二叉树:适用于以查为主,很少插入/删除的场景
红黑树:适用于频繁插入、删除的场景,实用性更强

折半查找

折半查找时间复杂度:O(log2n)
又称二分查找,仅适用于有序的顺序表,链表不具备随机访问特性,不能使用二分查找

大部分情况下折半查找更优,但是有的情况顺序查找更优(比如待查找元素在第一个位置)
思想:
1.使用双指针lowhigh分别指向有序表头和尾
2.计算 mid = (low+high)/2 将有序表一分为二,判断mid位置元素和待查找元素temp的大小关系,通过移动lowhigh保留temp可能的区间
3.重复第二步,直到low=high且此时指针指向的值等于temp查找成功(当low>high查找失败)
在这里插入图片描述

散列表

定义:一直数据结构,特点是数据元素的关键字与其存储地址直接相关,通过散列函数(哈希函数):Addr=H(key)建立关键字与存储地址的联系
散列查找是一种空间换时间的方法
增删改时间复杂度:O(1)

散列函数:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
处理冲突的方法:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

堆排序

空间复杂度:O(1)
时间复杂度:O(nlogn)
物理结构:使用顺序存储
逻辑结构:大根堆根节点大于左子树和右子树,小根堆根节点小于左子树和右子树
在这里插入图片描述
1.建立大根堆:
**思路:**把所有非终端节点都检查一遍,是否满足大根堆的要求,如果不满足,则进行调整
调整方式:检查当前节点是否满足 根>=左、右 若不满足,将当前节点与更大的一个孩子互换,若元素互换破坏了下一级的堆,则采用相同的方法继续向下调整(小元素不断“下坠”)

2.基于大根堆排序
方法:每一趟将堆顶元素加入有序子序列(与待排序序列中的最后一个元素交换),并将待排序元素序列再次调整为大根堆(小元素不断下坠)

归并排序

在这里插入图片描述

相关文章:

数据结构(面试)

目录 线索二叉树哈夫曼树并查集最小生成树最短路径拓扑排序二叉排序树平衡二叉树红黑树折半查找散列表堆排序归并排序 线索二叉树 原理&#xff1a;利用树节点的n1个左右空指针指向其遍历序列的前驱和后继&#xff08;线索&#xff09; 优点&#xff1a;简化遍历&#xff0c;不…...

从“人巡”到“智控”:EasyCVR智能视频监控技术变革河道违建监测模式

一、背景分析 随着城市化进程的加快&#xff0c;河道作为城市生态系统的重要组成部分&#xff0c;其保护与管理日益受到重视。然而&#xff0c;非法侵占河道、违规建设等行为时有发生&#xff0c;不仅破坏了河道的自然生态&#xff0c;还严重威胁到防洪安全和水质安全。为了有…...

JAVA基础 - 反射

目录 一. 简介 二. java.lang.Class类 三. java.lang.reflect包 四. 创建对象 五. 调用方法 六. 调用成员变量 一. 简介 反射是 Java 语言中的一种强大机制&#xff0c;允许程序在运行时动态地获取类的信息、访问类的成员&#xff08;包括字段、方法和构造函数&#xff…...

【系统架构设计师】二十二、嵌入式系统架构设计理论与实践③

目录 一、鸿蒙操作系统架构案例分析 1.1 鸿蒙操作系统定义 1.2 鸿蒙的层次化分析 1.2.1 内核层 1.2.2 系统服务层 1.2.3 框架层 1.2.4 应用层 1.3 鸿蒙操作系统的架构分析 1.3.1 鸿蒙操作系统架构具有4个技术特性 1.3.2 分布式架构所带来的优势 1.3.3 HarmonyOS 架构…...

【轨物推荐】经济长波:创新周期的历史

原创 丑丑姐姐 专利分析可视化 2021年08月01日 21:18 图片来源&#xff1a;Visual Capitalist 在开始本文之前&#xff0c;我们先来学习两个概念&#xff1a; 经济长波&#xff08;Long Waves&#xff09;&#xff0c;亦称“大循环理论”、“康德拉季耶夫周期”。经济长波理论…...

springboot高校勤工俭学平台-计算机毕业设计源码66824

摘 要 本研究基于Spring Boot企业框架&#xff0c;设计并实现了一款高校勤工俭学平台&#xff0c;包括首页、通知公告、新闻通知和岗位信息等功能模块。该平台旨在为高校学生提供便捷的勤工俭学信息发布与查询服务&#xff0c;促进校园内部劳动力资源的充分利用和高效管理。在研…...

CRM是什么?如何用CRM管理好客户?

在企业的销售运营中&#xff0c;客户是是贯穿始终的主体。客户的需求、偏好与满意度&#xff0c;指引着企业未来改变、优化的方向。而企业销售运营的核心&#xff0c;就是“客户至上”。 面对庞杂的客户信息&#xff0c;如何快速高效的进行客户管理呢&#xff1f;那就是要有一…...

编程入门:大学新生的指南与策略

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

Spring Cloud中怎么使用Resilience4j Retry对OpenFeign进行重试

在微服务架构中&#xff0c;服务之间的通信是非常频繁的。而使用OpenFeign可以极大简化微服务之间的HTTP通信。但在复杂的分布式系统中&#xff0c;服务之间的调用可能会因为网络问题、服务故障等原因而失败。因此&#xff0c;实现服务调用的重试机制显得尤为重要。Resilience4…...

【Redis 进阶】事务

Redis 的事务和 MySQL 的事务概念上是类似的&#xff0c;都是把一系列操作绑定成一组&#xff0c;让这一组能够批量执行。 一、Redis 的事务和 MySQL 事务的区别 1、MySQL 事务 原子性&#xff1a;把多个操作打包成一个整体。&#xff08;要么全都做&#xff0c;要么都不做&am…...

Linux的防火墙

一、防火墙概述 防火墙是一种计算机硬件和软件的结合&#xff0c;使internet和intranet之间建立一个安全网关&#xff08;Security Gateway&#xff09;&#xff0c;从而保护内网免受非法用户侵入的技术。 防火墙主要由服务访问规则、验证工具、包过滤和应用网关4个部分组成。…...

跟张良均老师学大数据人工智能-批量集训营开班中

随着我国大数据和人工智能产业的飞速发展&#xff0c;未来社会对高素质科技人才的需求日益旺盛。为助力广大青少年提前掌握前沿技术&#xff0c;实现自我价值&#xff0c;泰迪智能科技多名优秀老师联合打造暑期大数据人工智能集训营&#xff0c;旨在培养具备创新精神和实战能力…...

2024年音频剪辑必备:五大最佳音频编辑软件精选!

在数字时代&#xff0c;音频剪辑已成为创意表达的重要工具。无论是音乐制作、播客编辑还是视频后期&#xff0c;一款优秀的音频剪辑软件都是不可或缺的。推荐五款备受推崇的音频剪辑工具。 福昕音频剪辑 链接&#xff1a;https://www.foxitsoftware.cn/audio-clip/ 福昕音频…...

Native Programs(本机程序)

Native Programs System Program&#xff08;系统程序&#xff09;Config ProgramStake ProgramVote ProgramAddress Lookup Table ProgramBPF LoaderEd25519 ProgramSecp256k1 Program Solana contains a small handful of native programs that are part of the validator im…...

RisingWave 1.10 发布!新增用户自定义聚合函数

我们非常高兴地宣布&#xff1a;RisingWave 1.10 版本正式发布&#xff01;新版本为大家带来了许多重要更新&#xff0c;例如&#xff1a;新增用户自定义聚合函数 (UDAF)、支持从游标获取多个更新、支持可溢出哈希 Join、增强 CDC 连接器、新增 Sink 连接器等。一起来了解本次更…...

Modbus通讯协议

Modbus通讯协议 Modbus协议是一种用于电子控制器之间的通信协议&#xff0c;‌它允许不同类型的设备之间进行通信&#xff0c;‌以便进行数据交换和控制。‌Modbus协议最初为可编程逻辑控制器&#xff08;‌PLC&#xff09;‌通信开发&#xff0c;‌现已广泛应用于工业自动化领…...

fal.ai发布超分辨率模型——AuraSR V2

今天&#xff0c;我们发布了单步 GAN 升频器的第二个版本&#xff1a; AuraSR。 我们在上个月发布了 AuraSR v1&#xff0c;社区的反响让我们深受鼓舞&#xff0c;因此我们立即开始了新版本的训练。 AuraSR 基于 Adobe Gigagan 论文&#xff0c;以 lucidrain 的实现为起点。Gi…...

SYD88xx代码复位不成功和解决办法

原来的复位代码如下: void ota_manage(void){#ifdef _OTA_if(ota_state){switch(ota_state){case 1 : #if defined(_DEBUG_) || defined(_SYD_RTT_DEBUG_)dbg_printf("start FwErase\r\n");#endifCmdFwErase();#if defined(_DEBUG_) || defined(_SYD_RTT_DEBUG_)db…...

加油,为Vue3提供一个可媲美Angular的ioc容器

为什么要为Vue3提供ioc容器 Vue3因其出色的响应式系统&#xff0c;以及便利的功能特性&#xff0c;完全胜任大型业务系统的开发。但是&#xff0c;我们不仅要能做到&#xff0c;而且要做得更好。大型业务系统的关键就是解耦合&#xff0c;从而减缓shi山代码的生长。而ioc容器是…...

RS485 CAN SPI IIC UART RS232这些通信协议传输距离、传输速度对比给出比较顺序-笔记(面试必备)

各类通信协议&#xff08;RS485、CAN、SPI、I2C、UART、RS232&#xff09;的传输距离和传输速度各有不同&#xff0c;适用于不同的应用场景。以下是这些通信协议的传输距离和传输速度的对比及排序&#xff1a; 传输距离比较&#xff08;从长到短&#xff09; RS485 最大传输距…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...