笑枕晚风の小站

计算机网络97问 1. TCP报文格式及首部含义？ 头部长度：通常为20字节，有选项时更长 这里头部长度的1指代的是32位，即4个字节长度 因此4位的首部长度能够表示60字节 报文序号 标识报文中的第一个数据字节的序号 到达2^32-1后，重新回到0开始计数 初始连接请求报文中，SYN标志位也占1，因此第一字节序号为ISN+1 确认序号 接收方期望接收的下一个数据字节的序号 ACK为1时有效 校验和 由首部和数据一起运算得到，用来校验报文数据是否丢失 紧急指针 紧急数据字节号(urgSeq)=TCP报文序号(seq)+紧急指针(urgpoint)−1 正偏移量 选项 常见的是MSS(最大报文大小)，指明本端能够接收的最大长度的报文段 窗口大小 16位的窗口大小最多能放65536字节 如果想要使用更大的窗口，可以在选项中添加窗口的缩放比例因子来进行扩大，比例为0-14 2. IP报文格式及首部含义？ 头部长度：通常20字节，有选项时更长，总共不超过60字节 校验和 仅对IP首部计算校验和 TCP、UDP、ICMP等协议均 ...

Top K 1、智能指针的特点 简略 C++中的智能指针有4种，分别为：shared_ptr、unique_ptr、weak_ptr、auto_ptr，其中auto_ptr被C++11弃用。 为什么要使用智能指针：智能指针的作用是管理一个指针，因为存在申请的空间在函数结束时忘记释放，造成内存泄漏的情况。使用智能指针可以很大程度上避免这个问题，因为智能指针就是一个类，当超出了类的作用域时，类会自动调用析构函数，自动释放资源。 四种指针各自特性 （1）auto_ptr auto指针存在的问题是，两个智能指针同时指向一块内存，就会两次释放同一块资源，自然报错。 （2）unique_ptr unique指针规定一个智能指针独占一块内存资源。当两个智能指针同时指向一块内存，编译报错。 实现原理： 将拷贝构造函数和赋值拷贝构造函数申明为 private 或 delete 。不允许拷贝构造函数和赋值操作符，但是支持移动构造函数，通过 std:move 把一个对象指针变成右值之后可以移动给另一个 unique_ptr （3）shared_ptr 共享指针可以实现多个智能指针指向相同对象，该 ...

质数 定义 若一个正整数无法被除了 1 和它自身之外的任何自然数整除, 则称该数为质数 (或素数), 否则称该正整数为合数。 在整个自然数集合中, 质数的数量不多, 分布比较稀疏, 对于一个足够大的整数 NNN, 不超过 NNN 的质数大约有 N/ln⁡NN / \ln NN/lnN 个, 即每 ln⁡N\ln NlnN 个数中大约有 1 个质数。 质数的判定 试除法 若一个正整数 NNN 为合数, 则存在一个能整除 NNN 的数 TTT, 其中 2≤T≤N2 \leq T \leq \sqrt{N}2≤T≤N​ 。 证明: 由定义得, 因为 NNN 是合数, 所以存在一个能整除 NNN 的数 MMM, 其中 2≤M≤N−12 \leq M \leq N-12≤M≤N−1。 反证法： 假设命题不成立, 那么这样的数 MMM 一定满足 N+1≤M≤N−1\sqrt{N}+1 \leq M \leq N-1N​+1≤M≤N−1 。因为 MMM 能整除 NNN, 所以它们的商 N/MN / MN/M 也能整除 NNN 。而 2≤N/M≤N2 \leq N / M \leq \sqrt{N} ...

参考《算法竞赛进阶指南》、AcWing题库 基环树 众所周知, NNN 个点的树有 N−1N-1N−1 条边。若在树上任意添加一条边, 则会形成一个环。除了环之外, 其余部分由若干棵子树构成。 我们把这种 NNN 个点 NNN 条边的连通无向图, 即在树上加一条边构成的恰好包含一个环的图, 称为 “基环树” 。如果不保证连通, 那么 NNN 个点 NNN 条边的无向图也可能是若干棵基环树组成的森林, 简称为 “基环树森林”。 在有向图中, 我们也有类似的概念。NNN 个点、NNN 条边、每个节点有且仅有一条入边的有向图就好像以 “基环” 为中心, 有向外扩展的趋势, 故称为 “外向树”。NNN 个点、NNN 条边、每个节点有且仅有一条出边的有向连通图就好像以 “基环” 为中心, 有向内收缩的趋势, 故称为 “内向树”。外向树和内向树也经常统称为 “基环树” 。如果不保证连通, 那么 NNN 个点、NNN 条边、每个节点有且仅有一条出 (入) 边的有向图也可能是 “内 (外) 向树森林” 的形态。 基环树的结构仍然很简单, 但比树要复杂些, 因此常作为一些经典模型的扩展, 以适当增 ...

操作系统知识点总结 TopK 1、进程和线程之间有什么区别？ （1）进程 进程是程序的一次执行过程，是一个动态概念，是程序在执行过程中分配和管理资源的基本单位，每一个进程都有一个自己的地址空间，至少有 5 种基本状态，它们是：初始态，执行态，等待状态，就绪状态，终止状态。 （2）线程 线程是CPU调度和分派的基本单位，它可与同属一个进程的其他的线程共享进程所拥有的全部资源。 （3）联系 线程是进程的一部分，一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。 （4）区别：理解它们的差别，我从资源使用的角度出发。（所谓的资源就是计算机里的中央处理器，内存，文件，网络等等） 根本区别：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位 在开销方面：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。 所处环境：在操作系统中能同时运行多个进程（程序）；而在同一个进程（程序）中有多个线程同时执行（通过CPU调 ...

参考《算法竞赛进阶指南》、AcWing题库 Trie 字典树 Trie (字典树) 是一种用于实现字符串快速检索的多叉树结构。Trie 的每个节点都拥有若干个字符指针, 若在插入或检索字符串时扫描到一个字符 ccc, 就沿着当前节点的 ccc 字符指针, 走向该指针指向的节点。下面我们来详细讨论 Trie 的基本操作过程。 初始化 一棵空 Trie 仅包含一个根节点, 该点的字符指针均指向空。 插入 当需要插入一个字符串 SSS 时, 我们令一个指针 PPP 起初指向根节点。然后, 依次扫描 SSS 中的每个字符 ccc : 若 PPP 的 ccc 字符指针指向一个已经存在的节点 QQQ, 则令 P=QP=QP=Q 。 若 PPP 的 ccc 字符指针指向空, 则新建一个节点 QQQ, 令 PPP 的 ccc 字符指针指向 QQQ, 然后令 P=QP=QP=Q 。 当 SSS 中的字符扫描完毕时, 在当前节点 PPP 上标记它是一个字符串的末尾。 检索 当需要检索一个字符串 SSS 在 Trie 中是否存在时, 我们令一个指针 PPP 起初指向根节 点, 然后依次扫描 SSS ...

参考《算法竞赛进阶指南》、AcWing题库 树的直径与最近公共祖先 树的直径 给定一棵树, 树中每条边都有一个权值, 树中两点之间的距离定义为连接两点的路径上的边权之和。树中最远的两个节点之间的距离被称为树的直径, 连接这两点的路径被称为树的最长链。后者通常也可称为直径, 即直径既是一个数值概念, 也可代指一条 路径。 树的直径一般有两种求法, 时间复杂度都是 O(N)O(N)O(N) 。我们假设树以 NNN 个点 N−1N-1N−1 条边的无向图的形式给出, 并存储在邻接表中。 树形 DP 求树的直径 不妨设 1 号节点为根, “ NNN 个点 N−1N-1N−1 条边的无向图” 就可以看作 “有根树” 。 设 D[x]D[x]D[x] 表示从节点 xxx 出发走向以 xxx 为根的子树, 能够到达的最远节点的距离。设 xxx 的子节点为 y1,y2,⋯ ,yty_{1}, y_{2}, \cdots, y_{t}y1​,y2​,⋯,yt​ , edge(x,y)edge(x, y)edge(x,y) 表示边权, 显然有: D[x]=max⁡1≤i≤t{D[yi]+edge⁡(x ...

参考《算法竞赛进阶指南》、AcWing题库 最小生成树 给定一张边带权的无向图 G=(V,E),n=∣V∣,m=∣E∣G=(V, E), n=|V|, m=|E|G=(V,E),n=∣V∣,m=∣E∣ 。由 VVV 中全部 nnn 个顶点 和 EEE 中 n−1n-1n−1 条边构成的无向连通子图被称为 GGG 的一棵生成树。边的权值之和最小 的生成树被称为无向图 GGG 的最小生成树 (Minimum Spanning Tree, MST)。 定理 任意一棵最小生成树一定包含无向图中权值最小的边。 反证法。假设无向图 G=(V,E)G=(V, E)G=(V,E) 存在一棵最小生成树不包含权值最小的边。设 e=(x,y,z)e=(x, y, z)e=(x,y,z) 是无向图中权值最小的边。把 eee 添加到树中, eee 会和树上从 xxx 到 yyy 的 路径一起构成一个环, 并且环上其他边的权值都比 zzz 大。因此, 用 eee 代替环上的其他 任意一条边, 会形成一棵权值和更小的生成树, 与假设矛盾。故假设不成立, 原命题成 立。 推论 给定一张无向图 G=(V,E), ...

参考《算法竞赛进阶指南》、AcWing题库 链表与邻接表 数组是一种支持随机访问, 但不支持在任意位置插入或删除元素的数据结构。与之相对应, 链表支持在任意位置插入或删除, 但只能按顺序依次访问其中的元素。我们可以用一个 struct 表示链表的节点, 其中可以存储任意数据。另外用 prev 和 next 两个指针指向前后相邻的两个节点, 构成一个常见的双向链表结构。为了避免在左右两端或者空链表中访问越界, 我们通常建立额外的两个节点 head 与 tail 代表链表头尾, 把实际数据节点存储在 head 与 tail 之间, 来减少链表边界处的判断, 降低编程复杂度。 链表的正规形式一般通过动态分配内存、指针等实现, 为了避免内存泄露、方便调试, 使用数组模拟链表、下标模拟指针也是常见的做法。读者对于链表应该已经有所了解, 这里就不再赘述。两种实现形式的参考程序: 双向链表 123456789101112131415161718192021222324252627282930313233struct Node { int value; // data Node *pre ...

参考《算法竞赛进阶指南》、AcWing题库 最短路 对于一张有向图 ^{\mathbb{}}, 我们一般有邻接矩阵和邻接表两种存储方式。对于无向图, 可以把无向边看作两条方向相反的有向边, 从而采用与有向图一样的存储方式。因此, 在讨论最短路问题时, 我们都以有向图为例。 设有向图 G=(V,E),VG=(V, E), VG=(V,E),V 是点集, EEE 是边集, (x,y)(x, y)(x,y) 表示一条从 xxx 到 yyy 的有向边, 其边权 (或称长度) 为 w(x,y)w(x, y)w(x,y) 。设 n=∣V∣,m=∣E∣n=|V|, m=|E|n=∣V∣,m=∣E∣, 邻接矩阵 AAA 是一个 n∗nn * nn∗n 的矩阵, 我们把它定义为: A[i,j]={0i=jw(i,j)(i,j)∈E+∞(i,j)∉EA[i, j]= \begin{cases}0 & i=j \\ w(i, j) & (i, j) \in E \\ +\infty & (i, j) \notin E\end{cases} A[i,j]=⎩⎨⎧​0w(i,j)+∞ ...