快速排序的变种——快速选择算法

给出一个数组，例如[1,4,2,6,8,3]，现在要求出第 k 大的数字，即将数组从大到小排列，选择第k个数。用什么算法更快找到这个数？

最容易想到的就是先将数组排序，就可以很容易找到第 k 大的数字。就算用快速排序，时间复杂度为 O(nlgn)。有没有更快的算法？

C++11提供了三种智能指针：std::shared_ptr, std::unique_ptr, std::weak_ptr，使用时需添加头<memory>。

智能指针与普通指针混用

什么是拓扑排序？

拓扑排序就是对有向无环图的顶点进行线性排列，使得从顶点 u 到顶点 v 的每个有向边，u 在排序中都在 v 的前面。一个有向无环图的拓扑排序可能有多种。

列表

insert、remove、sort 等方法只修改列表，不输出返回值——返回的默认值为 None 。这是所有 Python 可变数据结构的设计原则。

不是所有数据都可以排序或比较。例如，[None, 'hello', 10] 就不可排序，因为整数不能与字符串对比，而 None 不能与其他类型对比。

单例设计模式的两种实现

单例模式的定义

保证一个类仅有一个实例，并提供一个它的全局访问点，该实例被所有程序模块所共享。

那么就必须保证：

• 该类不能被实例化
• 该类不能被复制。

对于 C++，意味着：它的构造函数，拷贝构造函数和拷贝赋值运算符不能被公开调用。

前缀和与二分查找的应用

题目链接：考试的最大困扰度

给出一个只有’F’ 和 ‘T’ 的字符串，和一个整数 k，可以对字符串种的字符进行两种修改：1. 把 ‘T’ 变为 ‘F’ ，2. 把 ‘F’ 变为 ‘T’。最多能修改 k 次，求由相同字符组成的连续子串长度的最大值。

什么是库

库文件是计算机上的一类文件，提供给使用者一些开箱即用的变量、函数或类。静态库和动态库，静态库和动态库的区别体现在程序的链接阶段：静态库在程序的链接阶段被复制到了程序中；动态库在链接阶段没有被复制到程序中，而是程序在运行时由系统动态加载到内存中供程序调用。

假设当前目录下有以下文件

├── main.c

├── tools.c

└── tools.h

STL 的组成部分

模版是C++程序设计语言的一个重要特征，STL 正是基于这一特征，STL 具有强大的功能，同时兼具良好的可扩展性。

STL 分为 3 类：Algorithm（算法）、Container（容器）和Iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。

STL 由 6 部分组成：容器(Container)、算法（Algorithm）、 迭代器（Iterator）、仿函数（Function object）、适配器（Adaptor）、空间配制器（Allocator）。

并查集原理

（1）并查集用于解决以下问题

用于处理没有重复元素的集合(不交集)的查询和合并。可以快速判断一个元素是否在一个集合中，或者两个元素是否属于同一个集合。

（2）并查集支持以下操作：

B树的性质

（1）B树的每个节点 x 都具有以下属性：

• x.n 存储在节点 x 中的关键字个数。

• x.n 个关键字本身 x.key₀, x.key₁,…, x.key_n-1，以升序排列，注编程语言数组下标从 0 开始。

• x.leaf 布尔值，表示节点 x 是否是叶节点。