主页

写在前面 刷力扣(415. 字符串相加)时候发现这样一个现象: 使用 s1 = static_cast<char>(c) + s1; 要比先push_back, 然后reverse慢很多: s2.push_back(static_cast<char>(c)); // .. reverse(s2.begin(), s2.end()); 那么问题出在哪呢? 猜测: 第一种方法应该是等号右边先通过重载的加法运算符创建了一份字符串的临时对象, 然后(调用拷贝赋值运算符)赋值给s1, 最后还要销毁临时对象, 这就导致每次都要进行赋值和销毁, 时间成本就上来了.. 而第二种都只是原地操作, 对内存的影响应该也只局限于动态扩容了. 测试 #inclu...

写在前面 最近看到了这样一个题: 静态数据成员定义之后，必须在类外进行初始化 看完了Effective系列之后, 我会给出答案: 错误. 为什么呢? 下面来深入分析一下. 非常量静态数据成员 看下面这个例子, 对于非常量静态成员来说, 必须在类内声明, 类外初始化. class P { public: static int cma; // 类内声明 }; int P::cma{}; // 必须类外初始化 void t1() { P p; cout << P::cma << endl; // 0 cout << p.cma << endl; // 0 } 这个没什么好说的, 因为...

写在前面 栈入门 主要用于深度优先搜索, 模拟递归过程, 以及一些特定解法的题目(例如单调栈, 括号匹配, 逆波兰表达式求值等), 基本实现 通过C风格数组很容易实现栈(但是固定了长度), 在C++STL中也有实现(通过deque), 不过基本的栈操作还是要用数组来完成, 要了解每一个API的实现过程. 基本题目 20. 有效的括号 - 力扣（LeetCode）; // 💩一样的代码 class Solution { public: bool isValid(string s) { if (s.size() & 1) return false; stack<char> st; ...

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;