主页

KMP算法 目的: 字符串匹配 思想: 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。 基本问题 28. 找出字符串中第一个匹配项的下标; class Solution { public: void getNext(int* nxt, const string& s) { int j{-1}; // j有两重含义, 前缀终止位置, 以及i之前最长相等前后缀长度 nxt[0] = j; for (int i{1}; i < s.size(); ++i) { // 前后缀不同: 一直回退, j>=0保证回退索引正常 ...

写在前面 记录一下二叉堆和堆排序, 堆(二叉堆)作为一种基本数据结构, 常在lc周赛三题位置出现, 遇到了我只能干着急, 必须好好学一下了. 参考算法导论(第三版). 这里说的堆指的是数据结构(抽象概念), 而不是程序执行时候的堆区(内存实体) 二叉堆介绍 二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆1。 当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。 当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。 实际使用时, 二叉堆表示为一个数组...

写在前面 学习Linux系统, 首先就要了解其系统的基本调用接口, 这里主要就是Shell命令了, top就是其中几个最重要也最常用的命令之一, 下面讲讲在Archlinux(x86_64)上使用top命令的一些参数与详解. 参考了man top1以及一些博客文章2. 基本界面 top - 04:37:41 up 2 min, 1 user, load average: 0.75, 0.65, 0.28 Tasks: 108 total, 1 running, 107 sleeping, 0 stopped, 0 zombie %Cpu(s): 0.1 us, 1.2 sy, 0.0 ni, 98.7 id, 0.0 wa, 0.0 hi, 0.0 s...

写在前面 select: 选择 用途: 在一段指定时间内, 监听用户感兴趣的文件描述符上的可读可写和异常事件. #include <sys/select.h> int select(int nfds, fd_set* readfds, fd_set* write_fds, fd_set* exceptfds, struct timeval* timeout); poll: 轮询 select和poll的缺点 epoll: 基于事件的轮询 水平触发和边缘触发 水平触发通知(LT, Level Trigger): 如果文件描述符上可以非阻塞地执行I/O系统调用, 此时认为它已经就绪. 边缘触发通知(ET, Edge Trigger): ...

写在前面 去重 while (i && nums[i] == nums[i - 1]) ++i; 去除前导零 while (r - l > 1 && word[l] == '0') ++l;

写在前面 在线编译工具链与反汇编工具: https://godbolt.org/; 使用的编译器: x86_64-clang16.0. 内置类型 i = i + 1 int main() { int i = 0; i = i + 1; } 对应的汇编代码: mov dword ptr [rbp - 4], 0 ;; i = 0 ;;-------------- i = i + 1; ------------------- mov dword ptr [rbp - 8], 0 ;; new_i = 0 mov eax, dword ptr [rbp - 8] ;...

写在前面 写一下内存映射/虚拟内存方面的内容总结, 主要参考了Linux/Unix系统编程手册. 内存映射可以用于进程间通信(IPC)和其他很多方面. 内存映射 mmap() 系统调用, 在调用进程的虚拟地址空间中创建一个新的内存映射. 分类 文件映射: 将一个文件的一部分直接映射到调用进程的虚拟内存中. 一旦一个文件被映射之后, 就可以通过在相应的内存区域中操作字节来访问文件内容了. 映射的分页会在需要的时候从文件中加载(也被称为基于文件的映射或者内存映射文件). 匿名映射: 没有对应的文件, 这种映射的分页会被初始化为0. 发生文件映射共享的情况 两个进程映射了一个文件的同一个区域, 此时这两个进程会共享物理内存的相同分页 通...

写在前面