LeetCode 802. 找到最终的安全状态
原题链接
题目描述
在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。
对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。
返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。
该有向图有 nnn 个节点，按 000 到 n−1n - 1n−1 编号，其中 nnn 是 graphgraphgraph 的节点数。图以下述形式给出：graph[i]graph[i]graph[i] 是编号 jjj 节点的一个列表，满足 (i,j)(i, j)(i,j) 是图的一条有向边。
数据范围
n==graph.lengthn == graph.lengthn==graph.length
1≤n≤1041 \le n \le 10^41≤n≤104
0≤graph[i].length≤n0 \le graph[i].length \le n0≤graph[i].length≤n
graph[i]graph[ ...
拓扑序列
拓扑序列是针对有向图的。
什么是拓扑序列
若一个由图中所有点构成的序列 AAA 满足：对于图中的每条边 (x,y)(x,y)(x,y) ，xxx 在 AAA 中都出现在 yyy 之前，则称 AAA 是该图的一个拓扑序列。
1 -> 2; 2 -> 3; 1 -> 3;
如果图中存在环，无论如何都构成不了拓扑序列。
一个有向无环图至少存在一个入度为0的点。
有向无环图被称为拓扑图。
度
入度
对于一个点，有多少条边指向自己。
出度
对于一个点，有多少条边指向别的点。
对于上图来说
点
入度
出度
1
0
2
2
1
1
3
2
0
所有入度为0点，可以排在当前最前面的位置。
大概思路：
queue <- 所有入度为0的点
while queue
{
t <- 队头
枚举t的所有出边（假设t的某个出边是j） t -> j
删除 t -> j，d[j]--
（只要将j这个点的入度减1，就可以认为删除了 t ->j 这条边。用d ...
C++智能指针
智能指针（Smart Point）
传统指针存在的问题
需要手段管理内存。
容易发生内存泄漏（忘记释放或出现异常等）。
释放之后产生野指针。
智能指针
智能指针就是为了解决传统指针存在的问题。
auto_ptr：属于C98标准，在C 11中已经不推荐使用（有缺陷，比如不能用于数组）。
shared_ptr：属于C++ 11标准。
unique_ptr：属于C++ 11标准。
注意：要包含#include <memory>。
auto_ptr
已弃用。
shared_ptr
class Person
{
private:
int age;
public:
Person(int age = 0) : age(age) { cout << "Person()" << endl; }
~Person() { cout << "~Person()" << endl; }
void run() { ...
C++中的异常
异常是一种在程序运行过程中可能会发生的错误。
异常没有被处理，会导致程序终止。
抛出异常
throw 异常信息
捕获异常
try
{
// 可能会发送异常的代码
}
catch ( 异常类型 变量名 )
{
// 处理代码
}
catch ( 异常类型 变量名 )
{
// 处理代码
}
int func(int a, int b)
{
if ( b == 0 ) throw "除数不能为0";
return a / b;
}
int main()
{
int a = 10, b = 0;
int c;
try
{
c = func(a, b);
}
catch ( const char *msg )
{
cout << "异常信息：" << msg << e ...
分解质因数
从小到大枚举所有数。
for ( int i = 2; i <= n; i ++ )
if ( n % i == 0 ) // i 一定是质数
{
// 求i的次数
int s = 0;
while ( n % i == 0 ) n /= i, s ++;
printf("%d %d\n", i, s);
}
puts("");
nnn 中，最多只会包含一个大于 n\sqrt{n}n 的质因子。分解完成后，单独处理一下 nnn 即可。
for ( int i = 2; i <= n / i; i ++ )
if ( n % i == 0 ) // i 一定是质数
{
// 求i的次数
int s = 0;
while ( n % i == 0 ) n /= i, s ++;
printf("%d %d\n", i, s ...
C++11、C++14与C++17
C++11
auto
可以从初始化表达式中推断出变量的类型，大大简化编程工作。
auto a = 10; a++; cout << a << endl; a = 11;
属于编译器特性，不影响最终的机器码质量，不影响运行效率。
decltype
可以获取变量的类型。
int a = 10; decltype(a) b = 20; // int b = 20;
nullptr
可以解决NULL二义性问题。
void func(int v)
{
cout << "func(int v)" << v << endl;
}
void func(int *v)
{
cout << "func(int *v)" << v << endl;
}
int main()
{
func(0);
// func(NULL); // 会报错，因为两个函数都匹配。
func(n ...
Markdown 数学公式
不完整，可能有错！！！
在Hexo中写公式一般是用LaTex写然后利用MathJax进行翻译来显示的。
我这个是用 LateX 进行翻译来显示的。
公式使用参考
使用公式
有两种使用方式，一种是行内公式，一种是单行公式
行内公式
$数学公式$
如：$x = 2$
如：x=2x = 2x=2
单行公式
$$
数学公式
$$
如：
$$
x = 2
$$
如：
x=2x = 2
x=2
上下标
^ 上标，_ 下标。如果上下标的内容多于一个字符，要用 {} 将这些内容括成一个整体。上下标可以嵌套，也可以同时使用。
$$2^0 = 1$$
$$2^{10} = 1024$$
$$a_0 = 0$$
$$a_{10} = 10$$
$$a^0_0 = 1$$
$$a^{10}_{9} = 100$$
如：
$$2^0 = 1$$
$$2^{10} = 1024$$
$$a_0 = 0$$
$$a_{10} = 10$$
$$a^0_0 = ...
C++类型转换
C语言风格的类型转换符号
(type)expression或type(expression)。
int main()
{
double a = 1.1;
int b = (int) a;
int c = int(a);
return 0;
}
C++中有4个类型转换符号
static_cast。
dynamic_cast。
reinterpret_cast。
const_cast。
使用格式：xx_cast<type>(expression)。
const_cast
一般用于去除const属性，将const转换成非const。
class Point{};
int main()
{
const Point *p = new Point();
// Point *p2 = p; 不被允许
Point *p2 = const_cast<Point *>(p);
// 等于下面的
// Point *p2 = (Point *)p;
...
LeetCode 881. 救生艇
原题链接
题目描述
第 iii 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
数据范围
1≤people.length≤500001 \le people.length \le 500001≤people.length≤50000
1≤people[i]≤limit≤300001 \le people[i] \le limit \le 300001≤people[i]≤limit≤30000
样例
输入样例1：
people = [1,2], limit = 3
输出样例1：
1
样例1解释：
111 艘船载 (1,2)(1, 2)(1,2)
输入样例2：
people = [3,2,2,1], limit = 3
输出样例2：
3
样例2解释：
333 艘船分别载 (1,2),(2)(1, 2), (2)(1,2),(2) 和 (3)(3)(3)
输入样例3：
people = [3,5,3,4], lim ...
C++模板
泛型
泛型，是一种将类型参数化以达到代码复用的技术，C+ +中使用模板来实现泛型。
模板（template）
格式：template <typename/class T>。
也可以指定多个类型，template <typename A, typename B, typename C> C add(A a, B b)，在调用的时候，指定参数类型即可。
如果有调用模板，编译器会根据参数类型，生成不同的函数。没有调用就不会生成。
typename和class是等价的。
模板的声明和实现如果分离到.h和.cpp中，会导致链接错误。
template <typename T>
T add(T a, T b)
{
return a + b;
}
int main()
{
cout << add<int>(1, 2) << endl;
cout << add<double>(1.1, 2.1) << endl;
c ...