redbook 笔试记录 2026.9.17

问题	简要总结
MySQL dump	`mysqldump` 是 MySQL 的逻辑备份工具，把数据库的表结构和数据导出为 SQL 文件；可通过 `mysql < backup.sql` 恢复。
Linux 硬链接 / 软链接	硬链接是多个文件名指向同一个 inode，删除原文件不影响其他硬链接；软链接是保存目标文件路径的独立文件，原文件删除后链接失效。
M:N 关系模型	数据库的多对多关系，通常增加一张中间表，把 M:N 拆成两个 1:N，例如 `学生—选课表—课程`。
进程不能进入临界区时等待	对应同步机制的让权等待：不能进入临界区时应阻塞并释放 CPU，而不是一直忙等。
192.168.1.200/26	子网掩码 `255.255.255.192`，所在网段 `192.168.1.192/26`；可用主机范围 192.168.1.193～192.168.1.254，广播地址 `.255`。
4,5,6,7,8,9,10 建 BST	按顺序插入二叉排序树，由于严格递增，所有节点都成为右孩子，最终形成右向单支树/右斜树，查找最坏退化到 $O(n)$ 。
A、B、C 交换题	`(a[i],b[i])` 绑定；满足二维偏序即可交换。转化为二维点连通分量问题；按 A 排序，用 B 的前缀最小值和后缀最大值找分量，再判断每个分量中 B、C 多重集合是否一致。总体 $O(n\log n)$ 。

给定长度为 $n$ （ $n\le10^6$ ）的数组 $A,B,C$ 。每个 (a[i], b[i]) 绑定在一起。

任取两个位置 $i,j$ （不要求 $i<j$ ），若：

a_i\le a_j,\quad b_i\le b_j

则可以同时交换 a[i],a[j] 和 b[i],b[j]。问能否经过若干次交换使 $B=C$ 。元素允许重复。

把 (a[i],b[i]) 看成二维点，两个点只要二维上可比较就能交换。同一连通分量内的元素可以任意排列。

无需 $O(n^2)$ 建图：

a_i<a_{i+1} \quad\text{且}\quad prefixMin_i>suffixMax_{i+1}

则这里是两个连通分量的分界。

复杂度： $O(n\log n)$ ，空间 $O(n)$ 。

评论