- select select 系统调用的定义如下: select(int nfds, fd_set* readfds, fd_set* writefds, fd_set* exceptfds, struct time_val* timeout); select 系统调用时，向操作系统内核空间会拷贝 3 个 fd_set，分别表示要监控读事件，写事件以及异常事件的 fd 集合，之后内核会对这些 fd 进行轮询，并将相应事件就绪的 fd 拷贝至对应的 fd_set 并在调用结束后将写好的 fd_set 返回至用户空间。 fd_set 内部采用 bitmask 方式进行实现，因此打开的最大 fd 的数目受到一定的限制，由 FD_SETSIZE 常量表示，可以采用如下的 API 进行设置。 #include <sys/select.h> void FD_ZERO(fdset* fds); /* 将 fdset 置空 / void FD_SET(int fd, fdset fds); /* fdset 添加 fd / void FD_CLR(int fd, fdset fds);....
- 红黑树的性质 红黑树是一种自平衡的二叉搜索树，有如下一些性质： 红黑树是一棵平衡二叉搜索树，其中序遍历单调不减。 节点是红色或黑色。 根节点是黑色。 每个叶节点(也有称外部节点的，目的是将红黑树变为真二叉树，即 NULL 节点，空节点)是黑色的。 每个红色节点的两个子节点都是黑色。(换句话说，从每个叶子到根的所有路径上不能有两个连续的 红色节点) 从根节点到每个叶子的所有路径都包含相同数目的黑色节点（这个数值叫做黑高度）。 由于每个叶子节点黑高相同且不存在相邻红节点，所以每个叶节点的高度都不会超过其他叶节点高度的两倍，所以可以认为它是相对平衡的。 红黑树主要通过染色和旋转两种方式实现自平衡。 染色： 不解释，就是把红的变成黑的，黑的变成红的。 旋转： 分为左旋和右旋。 左旋的操作如下图所示，右旋类似，旋转操作不破坏二叉搜索树的性质，只是改变了树的结构，让被旋转的孩子节点成为新的根节点。 2.红黑树插入 首先对于红黑树的插入，插入的节点必须为红节点。 插入之后，若插入节点的父节点为黑节点，则红黑树本身的性质并不改变（每个叶子结点黑高相等且不包含相邻红节点），直接插入即可。 若插入节....
- 问题描述 KMP 算法解决的主要是字符串匹配问题，如在字符串 Str 中找寻子串 Pattern 是否存在，如果存在，输出 Pattern 在 Str 中出现的位置，否则输出 -1 ； Str:abcxababx \ Pattern:aba 因为 abcx[aba]bx 包含了子串 aba ，所以算法返回 aba 出现的位置 4 。 2. KMP 算法 2.1 时间空间复杂度 若采用暴力搜索的方式解决这个问题，则每次找寻以 Str[i] 开头的子串是否为 Pattern ，时间复杂度为 O(MN) 其中 M 为 Str 长度， N 为 Pattern 长度。 KMP 算法可以用 O(M+N) 的时间复杂度和 O(N) 的空间复杂度来解决这个问题。 2.2 算法基本介绍 算法的关键是对于子串构造一个 Next 数组用于解决每次子串不匹配时，都要返回子串开头重新匹配的问题。 解决方式是在匹配一个字符时，若以该字符前一个字符为结尾的后缀串与子串 Pattern 的前缀相同时，该（后缀/前缀）串无需在目标字符串中重新比较。 例如： Str： abcabcabddef Pattern:....
- 简介 rsa 是一种非对称密码算法，由三位数学家 Rivest、Shamir 和 Adleman 设计。其原理基于大数因式分解的复杂性。通常使用时，生成一对公私钥对，主要应用于以下两个场景。 加解密: 使用公钥加密，只有持有私钥的人可以解密。 签名和验签：使用私钥进行签名，公钥进行验签，用于一些数据签名，校验的场景。 2. 数学背景 2.1 欧拉函数 假设有正整数 n，欧拉函数\phi(n)的值等于小于 n 的正整数里有多少个与 n 互为质数。 欧拉函数有以下几个性质： \phi(1) = 1 因为 1 与任何数都保持了互质关系。 如果 n 为质数，\phi(n)=\phi(n-1) 如果 n 为质数的某一次方，即 n = p^k: \phi(p^k) = p^k - p^{k-1} = p^k\cdot (1- \frac{1}{p} ) 这是因为当 m < n 时，当且仅当 m 不为 p 的倍数，m 才与 n 互质，而这样的数共有 p^{k-1}个(1\cdot p, 2\cdot p, ..., p^{k-1}\cdot p)。 例如： 对 n = 7^3 求 \phi(n) ，需要枚举所....
- 基本命令及使用方法 1.1 设置断点 命令格式 例子 解释 break(b) + 行号 break n 在第 n 行设置断点 break(b) + 函数名 break func 在 func 函数前设置断点 tbreak + 行号/函数名 tbreak n/func 设置临时断点，到达后自动删除 break + filename: 行号/函数名 break main.c:10 在指定文件设置断点 break + 行号 + if + 条件 break 10 if i == 3 根据指定条件设置断点 ，多用于循环 awatch/watch + 变量 watch i 变量被读出或写入时暂停 clear + 行号 clear n 删除第 n 行对应的断点 info breakpoints/watchpoints - 查看断点/观察点信息 delete + 断点编号 delete 2 删除断点编号为 2 的断点 enable /disable + 断点编号 enable/disable 1 改变对应编号断点状态是否可用 1.2 查看/改变变量信息 命令格式 例子 解释 display + ....
