算法思考
0.前言经常有人把学习CS比作“仓鼠轮”，暗指这是一个单调重复的记忆过程。我自认还是付出了一些努力，但大多数都只是机械的记忆。随着学习的深入，我逐渐发现自己真正的短板在于“思考的深度”。最典型的例子就是算法。 1.时间复杂度考察在实际业务（和刷题）中，评估一个算法必须同时权衡**平均（典型）和最劣（极端）**两种复杂度。 第一步：基于“数据量级”，估算“性能天花板”首先，我们要根据输入的数据量 $N$ 来估算一个“可接受”的时间复杂度上限。这是对“典型情况”的粗略评估。 以算法题中常见的 $10^8$ 次操作为性能瓶颈为例： 若 $N = 10^4$，$N^2 = 10^8$。这意味着 $O(n^2)$ 的算法已经逼近性能红线，非常危险，很可能超时。 若 $N = 10^5$，$N \log N \approx 1.7 \times 10^6$。此时 $O(n \log n)$ 绰绰有余。 若 $N = 10^8$，你甚至都不能用 $O(n)$，可能需要 $O(\log n)$ 或 $O(1)$。 第二步：基于“数据构造”，考察“最劣退...
灵神题单-动态规划
1. 子数组和dp此类题目的目标一般为找到数组中最大的子数组和。 递推公式：dp[i] = max(dp[i - 1], 0) + n[i];这里dp[i]表示以i结尾的子数组最大和，公式含义为，要使子数组和最大，如果以以i-1结尾的子数组和小于0，那么直接舍弃，从i开始拼接新的子数组，否则将i-1结尾的子数组拼上元素i将会更大。因为dp元素没有直接指向目标，所以在递推的过程中，需要使用mx = max(mx, dp[i])来确认当前子数组的和是否为最大值。 此类题目也可以应用前缀和进行求解。 参考题目 2. 网格图dp此类题目的目标一般为在一个网格图中找到从起点到终点的最小cost。 由于是网格图，所以在递推前要先对边界进行初始化（根据题目要求，可能是第一行，第一列…）。 递推公式：dp[i][j] = min(foreach(dp[i - m][j - n] + cost[i - m][j - n]), dp[i][j]);dp[i][j]表示到达当前位置的cost。对于每一个可能存在前一个状态的位置都应用此公式。前一个状态可能从上边，左边等方向推过来。注意dp[i][j]在...
CPP资源管理摘要
1. 引用和指针的取舍引用和指针是什么无需赘述。要解决实际应用时如何在二者中进行取舍，主要关注可空性和可重定向性这两个特性。 可空性在CPP11引入nullptr以后，空指针就有了唯一的指代值。使用指针时，可以使该指针指向某个特定的地址，或者为nullptr，而使用引用，则在创建该引用时就必须指定明确的引用目标。 可重定向性指针指向的地址可以任意修改，而引用则无法修改。 2. 访问堆上变量堆上的数据都是匿名的，所以如果想访问堆上数据，起点一定在其他的内存分配区域。一般有三种形式来开辟堆上内存区域：直接调用new关键字，构造自定义或标准容器类，调用智能指针工厂函数。（后两种底层上也调用了new关键字，但它们支持RAII自动析构，不用手动delete。） 3. 是否取用智能指针引入智能指针的目的是为了自动管理堆上变量的生命周期，也就是说，当你需要使变量获得与函数作用域解绑的生命周期时，则引入智能指针。 4. 借用机制如果程序承诺：观察者的生命周期永远被包含在所有者以内，那么所有者可以向观察者借出数据。表现为，在观察者的程序流中尝试用裸指针获取智能指针中的内容。auto *ta...
一个程序的生命周期：当我们运行它时，究竟发生了什么？
从我们双击可执行文件开始，一场由操作系统精心编排、CPU奋力执行的复杂“戏剧”也随之上演了。那么，一个静态的二进制文件，是如何变为一个动态的、正在执行的进程的呢？ 1.内存加载 一切始于操作系统的加载器（Loader）。当你执行一个程序时，加载器会读取这个二进制文件（如Linux的ELF格式），并依据其内部的“地图”，为进程构建一个独立、完整的虚拟地址空间。这个构建过程严格遵循着上图所示的自下而上的结构： 加载静态区域（Read from program file）加载器首先处理程序在编译时就已经确定的静态部分。它通过**内存映射（Memory Mapping）**的方式，高效地将文件内容与虚拟内存关联起来： Text段（代码段）：位于地址空间的最底部，包含了程序的机器指令。这部分区域是只读的，直接从可执行文件中映射而来。 Initialized Data段（数据段）：紧邻Text段之上，存放已初始化的全局变量和静态变量。这部分数据同样从可执行文件中读取。 Uninitialized Data段（BSS段）：用于存放未初始化的全局变量和静态变量。如图标注所示，加...
