SCHNIE:BLOG

一、经典数据结构 1. 并查集并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 优化方法： 1.按秩合并：秩是当前树的最大高度，按秩合并即将高度小的树合并到高度大的树上，以尽可能压低最终树高。2.路径压缩：每次查询时，将查询路径上的点的父亲，设置为该树的根节点，以压低树高。 综合使用两种策略，能将 find 和 union 的均摊复杂度压到**O(1)**。 12345678910111213141516171819inline void init_set(int n) //初始化并查集{ for (int i = 1; i <= n; i++) s[i] = i;}int find_set(int x) //查找{ if (x != s[x]) s[x] = find_set(s[x]); return s[x];}void union_set(int x, int y) //原始合并{ x = find ...

变量与对象 Python 变量只存储对象的引用（内存地址），只能被重新绑定，变量名在变量名表中独立存储。对象是 Python 对数据的抽象，代表一块内存，里面有身份、值、类型等信息。变量名（比如 x、func）只是代码中的标识符，本身不是对象。 变量名被存储为命名空间字典中的字符串键。命名空间（如 globals() 返回的字典）是一个 dict 对象，它的键是字符串对象（str 实例）。 C++ 变量对应内存中的某块空间，变量名是内存位置的别名；引用就是变量的别名，无独立存储，操作引用即操作原变量。变量持有值本身，变量与存储空间捆绑在一起，而不是指向值的指针（指针类型除外）。 “一切皆对象”是指程序中用到的任何数据（包括数字、字符串、函数、类等）都被视为一个”对象”。在 Python 里，任何东西都可以像操作一个普通变量一样去操作。 数字运算 123import numpy as npprint(15/3, 15//3, -5/3, 3**4, pow(2, 512, 998244353), sep=',', end='') 字符串 1 ...

保研资料：计算机基础知识 malloc 和 newnew从堆区和自由存储区上分配内存，malloc从堆上分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。malloc只负责分配一块指定大小的内存空间，返回一个指向该空间的void*类型指针。new无须指定内存块的大小，它会在分配内存的同时调用构造函数初始化对象，并返回一个指向该对象的指针。new 可以调用对象的构造函数，对应的 delete 调用相应的析构函数；malloc 仅仅分配内存，free 仅仅回收内存，并不执行构造和析构函数。new在遇到内存分配失败时会抛出std::bad_alloc异常，而malloc则返回NULL指针表示分配失败。 函数名，函数指针，函数的入口地址：函数名：c语言中，函数名就是一个函数指针。入口地址：函数时执行的第一条指令的地址，通过这个地址可以找到该函数。函数指针：指向入口地址，就可以通过该指针调用函数了。 数组名，数组首地址，数组指针：数组名不是指针，是数组首地址。但 sizeof 时返回整个数组地址大小。编译器会自动将 数组名 a ...

保研资料：高等数学 可微、连续、可导可微：设函数在P的领域内有定义，如果全增量deitaZ=Adeitax+Bdeitay+o(p),其中A,B是不依赖deitax，deitay的常数，则称呼z在P点可微，Adeitax+Bdeitay为P点的全微分。导数：描述的是某点切线的斜率。极限：去心领域内有定义微分：描述的是一点的函数值的增量，且该增量是自变量与一个和自变量无关的常数的乘积，含义为用一条线性函数在某点逼近原函数。相较于导数，微分更具有直接的形式，能够更方便地解决微分方程、进行积分，并扩展到多元的情况。连续：一元函数：可微和可导等价；可导必连续，连续不一定可导（狄利克雷函数，处处连续，处处不可导）；连续必可积，可积不一定连续 多元函数：偏导连续一定可微，可微一定连续、偏导存在；连续不一定可微；连续必可积，可积不一定连续有四则运算法则、求导/偏导/微分的链式法则（需要分清哪些是自变量、中间变量）。一阶导数/全微分的形式不变性：无论被求导/全微分的变量是自变量还是中间变量，最后的形式相同。 中值定理条件：闭区间连续，开区间可导。（1 ...

保研资料：计算机网络 基本知识计算机网络：计算机技术和通信技术相结合的产物，独立自治、相互连接的计算机集合。分为硬件、软件、协议；广域网城域网局域网；广播、点对点；资源子网、通信子网。电路交换、报文交换、分组交换。拓扑结构：总线型（信息传输不存在路由和转发的问题，总线长度和连接的设备数受到限制，容易冲突）、星形、环形、网状，树状，混合型。（分析点：拓扑结构简单、健壮性好、便于管理、成本低）指标：速率、带宽、吞吐量、时延。计算机网络的体系结构：计算机网络的各个层次及其协议的集合。码元：数字信号的计量单位。奎纳斯定理：理想低通信道中，为了避免码间串扰（高频分量不能通过信道），极限码元传输速率为2W波特。香农定理：带宽受限且有噪声干扰时的极限数据传输数率。Wlog（1+信噪比）。无线介质：无线电波（WLAN）、微波、红外线、激光。ALOHA协议：发送前不进行监听。路由转发算法：1.检查特定主机路由；2.进行按位与，找到下一跳；3.转发给默认路由。RIP使用UDP的520号端口；OSPF：网络层协议，仅链路状态变化时，才洪泛；OSPF划分区域、OSPF 对于不同类型的业务可计算出不同的路由； ...

保研资料：算法设计与分析 算法有限条指令构成，规定了解决特定问题的一系列操作。 算法分析确定运算+确定数据集、分析时间复杂度（事前分析）、作时空性能分布图（事后测试） 分治法缺点：子问题过多（治：反复使用分治策略，直到可以直接求解子问题）、递归工作量过多（分合）。 多阶段决策过程（组合问题）前后关联的有链状结构的过程。在每一个阶段都有很多选择。多阶段决策问题的解决：贪心、动态规划，分支限界、回溯法。 贪心和动态规划贪心-寻找最优量度标准解决寻找一个输入的子集的问题，满足约束条件（可行解）和目标函数（最优解）的解。一旦证明成立后，是简单易行的高效算法。同时对许多不一定能产生最优解的问题都能产生近似最优解。 动态规划-最优子结构、无后效性、子问题重叠最优子结构：问题的最优解所包含的子问题的解也是最优的。反例：求一系列数的异或最大值无后效性：当前阶段的求解只与之前阶段有关，而与之后的阶段无关。反例：带负权边的最短路决策并不是线性的，而需要全面考虑不同情况，分别决策。步骤：寻找子问题、定义状态、导出状态转移方程、确定边界条件。 回溯法和分支限界法-搜索和剪枝回溯法-多米诺性质（如果部分解向量 ...

保研资料：离散数学 关系笛卡尔积：设A,B是两个集合，所有有序对（x，y）做成的集合称为笛卡尔积。其中x来自A，y来自B。关系：集合ABC的一个子集F称为A,B,C上的一个n元关系。存储：关系矩阵、关系图。传递性：等价于R²包含于R。空关系：反自反、对称性、反对称性、传递性；空集合上的额外多出自反性。可用谓词、蕴含式证明。商集：以R的所有不同等价类为元素构成的集合。商集是集合的一个划分。最大元是最小上界；在集合中的上界必是最大元。（最大元、极大元在集合中；上界未必在集合中）。极大元对有限部分序集必存在，但未必唯一。完备的偏序集：有最小元、每一个链有上确界（或仅含有穷链）。一个偏序集是一个全序集，如果它本身是一条链。A包含于B，当且仅当A的幂集包含于B的幂集。 范式G与其stolen范式S的可满足性、恒假性等价。主合取范式（存在且唯一）、主析取范式（存在且唯一）；前束范式、skolem范式（首标中无存在量词、母式为合取范式）。有限个短语的析取式：析取范式。主析取范式由极小项组成：一个短语包含所有原子，且排列顺序与原始顺序一致。利用主合取范式、主析取范式可求解判定问题：判断命题公式是否等 ...

保研资料：计算机组成原理 基础知识计算机体系结构：概念性的结构与功能特性；计算机组成：实现计算机体系结构所体现的属性。 各种周期一个指令周期包含多个机器周期（CPU周期），一个机器周期包含多个时钟周期，一个时钟周期为一个微指令周期。时钟周期是计算机内部时钟震荡器发出一个完整的周期所需的时间。它是CPU工作的最小时间单位。 计算机的性能指标？总线宽度、吞吐量、CPU主频、利用率、CPI、IPS、处理机字长。CPU执行时间=CPU时钟周期数/主频=(指令条数×CPI)÷主频。 什么是总线？总线有什么好处？总线有什么功能？总线：总线是指计算机系统中连接各个硬件组件的物理通道或逻辑通道。系统总线：单总线结构、双总线结构（主存总线连接CPU、主存、通道；IO总线。优点：分离了低速IO）、三总线结构（主存总线、IO总线、DMA总线。优点：进一步提高了吞吐量）。内部总线：单总线（所有组件挂载一组总线上）、多总线、专用线好处：不同的设备可以通过总线发送和接收数据，实现彼此之间的通信和协作；使用总线可以减少硬件的复杂性和成本。通信总线（I/O总线）。功能：（1） ...

保研资料：数据结构 数据结构按某种逻辑关系将一批数据元素组织起来，按一定的存储方式将它们存储起来，并在这些数据元素上定义一个操作集合,就得到了一个特定的数据结构。 数据的逻辑结构逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。线性结构：线性表。只有一个始末，每个内节点只有一个前驱和后继。线性表：数组，链表，栈，队列非线性结构：层次结构（树，叶节点可能有多个）、网状结构（图）、集合。节点可能有0、多个前驱和后继。 数据的存储结构数据结构在计算机中的表示，也称物理结构。分为：顺序存储、链接存储、散列存储、索引存储。邻接表：顺序存储的顶点表+链接存储的边链表。邻接表利于找邻接顶点。 数据结构的使用跳表：logn层有序链表，最底层包含所有元素。插入后以1/2递减的概率向上插入，适合动态查找场景。实现方式：四联表。拉链法很长时，使用红黑树。哈希表用途：bool过滤器。树是分层结构，图是网络模型结构；树有根节点，图没有根节点的概念；树的边数为节点数减一，图的边数没有限制；树不能有环，图可以有。红黑树中的每一个结点的颜色不是黑色就是红色。根结点和所有外部结点（NULL节点、叶 ...