虚拟内存

虚拟内存的存在是为了运行比物理内存还大的程序，可以让系统看上去比实际物理空间大小大得多，并为多道程序的执行创造了条件。

明确一个概念：内存中的每一个存储单元都必须有确切的地址，而例如对32位机来说，能发出的地址数目就是2^32=4G，这也被称为处理器的寻址能力。因此机器内存的大小也应该是和处理器的最大寻址能力对应的。

但现实往往不是这样的，导致了大量寻址能力的浪费。但我们可以明确一点：程序总是被逐断运行的，一段时间内会稳定运行在某一段程序中。

因此一种做法是：把要运行的那一段程序从辅存（磁盘等外部存储设备）中复制出来，其余仍然留在辅存。当要运行下一段程序时，就把内存中的上一段程序换回到磁盘中。这也就让内存看起来变大了，这个存储空间也被叫做虚拟内存空间。这个虚拟内存空间是右寻址能力决定的。

这也就是说，一个程序被执行，需要执行两次映射，第一次映射到虚拟内存，第二次映射到物理内存。负责这个任务的硬件部分被称为存储管理单元（MMU），软件部分被称为内存管理模块。

内存管理模块记录着一个虚拟地址/物理地址映射表，作为MMU转换的依据。

首先抛出一个问题：为什么需要二级配置器？
因为当我们动态分配内存的时候，分配的内存往往不仅仅是我们需要的那些，还会产生一些额外的开销，比如首尾的cookies，debug模式下产生的额外开销，和内存对齐所产生的pad。这些附加信息，降低了空间的利用率。

于是就设置了二级空间配置器，当开辟小等于128bytes内存时，就视为开辟小块内存，调用二级空间配置器。否则调用一级空间配置器。

一级空间配置器

在一级空间配置器中，最重要的函数有：

• allocate：用于分配空间，申请失败，调用oom_alloc尝试重新申请
• deallocate：用于释放空间
• reallocate：调整已经存在的空间大小，如果调整失败，调用oom_alloc尝试重新申请

其实对应的标准库函数就是malloc，free和realloc。

继承 with virtual function

构造由内而外：首先调用父类的构造函数，然后再调用自己。
析构由外而内：首先执行自己的析构函数，然后调用父类的析构函数。

non-virtual: 你不希望重新定义（重写）它。
virtual: 你希望子类重新定义它，且它有默认定义。
pure virtual: 你希望子类一定要重新定义它，你对它没有默认定义。

1
2
3
4
5
6
7
8
9

class Shape {
  public:
    virtual void draw() const = 0;   // 纯虚函数
    virtual void error(const std::string& msg);   // 虚函数 
    int objectID() const;   // 一般成员函数
};

class Rectangle: public Shape {...};
class Ellipse: public Shape {...};

题意

给你一个 $a$ 数组，其中 $a[i] = [startDay_i, endDay_i, value_i]$ ，表示第 $i$ 个会议在 $startDay_i$ 天开始，第 $endDay_i$ 天结束，如果你参加这个会议，你能得到价值 $value_i$ 。同时给你一个整数 $k$ 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和。$(k \in [1, n], k * n \in [1, 1e6], startDay_i, endDay_i \in [1, 1e9], value_i \in[1, 1e6])$

Solution

题意

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。$(n, k \in [1, 100000])$

Solution

用优先队列+延迟删除有点麻烦，可以考虑直接用 multiset 做，本质都是一样的，维护两个大小相同或差一的集合（自动排序）$l 和 r$，$l$ 维护小于等于中位数的值，$r$ 维护大于等于中位数的值，$multiset$ 的优秀特性可以在 $log$ 时间复杂度内进行增删操作。具体细节较多，时间复杂度 $O(nlog(k))$。

主机字节序和网络字节序

字节在内存中的排列影响它实际的值，字节序分为大端序和小端序。大端序指一个整数的高位存储在内存的低地址处，小端序指一个整数的高位存储在内存的高地址处。

现代PC大多采用小端序，因此小端序又被称为主机字节序。

由于数据在两台使用不同字节序的主机之间进行传递是，接收到必然错误的解释了数据。解决的方法是：发送端总是把要发送的数据转化成大端序然后再发送，接受端明白对方传过来的数据总是采用大端序，所以接受端可以根据自身使用的字节序来决定是否对该数据进行转化。因此大端序也称为网络字节序。

题意

给定一个 $nm$ 的权值矩阵，求从左上角走到右下角。$(n, m \in [1, 100], w \in [1, 1e6])$

一条路径耗费的体力值是路径上相邻格子之间 高度差绝对值的最大值 决定的。

Solution

1. 二分答案：由于答案具有单调性，所以可以二分答案，然后通过 $bfs$ 进行验证。
2. 并查集：类似于最小生成树，将所有的边都建出来，然后贪心的将当前权值最小的边加入集合，判断起点和终点是否联通即可。
3. 最短路：将所有的边建出来，做一次起点到终点的最短路径即可。

题意

给你一个整数数组 $g$，它是前 $n$ 个正整数的排列，且 $n$ 是个 奇数 。

它被加密成另一个长度为 $n - 1$ 的整数数组 $a$ ，满足 $a[i] = g[i]$ ^ $g[i + 1]$。比方说，如果 $g = [1,3,2]$，那么 $a = [2,1]$。

给你 $a$ 数组，请你返回原始数组 $g$。题目保证答案存在且唯一。

Solution

题意

给你一个字符串 $s$，以及该字符串中的一些「索引对」数组 $pairs$，其中 $pairs[i] = [a, b]$ 表示字符串中的两个索引（编号从 $0$ 开始）。

你可以 任意多次交换 在 $pairs$ 中任意一对索引处的字符。

返回在经过若干次交换后，$s$ 可以变成的按字典序最小的字符串。

Solution