LeetCode 1137. 第 N 个泰波那契数
原题链接
题目描述
泰波那契序列 TnT_nTn 定义如下：
T0=0,T1=1,T2=1T_0 = 0, T_1 = 1, T_2 = 1T0=0,T1=1,T2=1，且在 n≥0n \ge 0n≥0 的条件下 Tn+3=Tn+Tn+1+Tn+2Tn+3 = T_n + T_n+1 + T_n+2Tn+3=Tn+Tn+1+Tn+2。
给你整数 nnn，请返回第 nnn 个泰波那契数 TnT_nTn 的值。
数据范围
0<=n<=370 <= n <= 370<=n<=37
答案保证是一个 323232 位整数，即 answer≤231−1answer \le 2^{31} - 1answer≤231−1。
样例
输入样例1：
n = 4
输出样例1：
4
样例1解释：
T3=0+1+1=2T_3 = 0 + 1 + 1 = 2T3=0+1+1=2。
T4=1+1+2=4T_4 = 1 + 1 + 2 = 4T4=1+1+2=4。
输入样例2：
n = 25
输出样例2：
1389537
题意
T0=0,T1=1 ...
试除法判断质数
质数
什么是质数：存在一个数 n (n>1)n \, (n > 1)n(n>1) ，若 nnn 只能被 111 和 nnn 整除，不再有其他的因数，称为质数（素数），否则称为合数。若 n≤1n \le 1n≤1 ，nnn 既不是质数，也不是合数。
判定质数——试除法
从定义出发，枚举每个 i (3≤i≤n−1)i \ (3 \le i \le n - 1)i (3≤i≤n−1) ，若 i∣ni|ni∣n（ nnn 能被 iii 整除 n % i=0n \ \% \ i = 0n % i=0），则 nnn 不是质数。时间复杂度是 O(n)O(n)O(n) 的。
如果 d∣nd|nd∣n （ ddd 整除 nnn ） ，那么 nd∣n\frac{n}d|ndn∣n （ nnn 除 ddd 的商也能整除 nnn ）的。比如 d=3,n=13d = 3, n = 13d=3,n=13 的时候，333 可以整除 121212 ，123\frac{12}3312 也可以整除 121212 。可以发现 nnn 的约数都是成对出现的，我们在枚举的时候，可以只枚举每一对中较小的那 ...
AcWing 3794. 构造字符串
原题链接
题目描述
给定一个整数 nnn，请你构造一个长度为 nnn 的字符串，要求：
字符串中不含 a,b,c 以外的字符。
字符串中不含长度为 333 的回文子串。
字符串中 c 的数量尽可能少（最好没有）。
输入格式
一个整数 nnn。
输出格式
一个满足条件的字符串。
如果答案不唯一，则输出任意合理方案均可。
数据范围
1≤n≤2×1051≤n≤2×10^51≤n≤2×105。
样例
输入样例1：
2
输出样例1：
aa
输入样例2：
3
输出样例2：
bba
思路
构造一个长度不超过 333 的回文子串，只用 aaa 和 bbb 构建，只要重复 abbaabbaabba 或者 aabbaabbaabb 即可。
代码
C++
#include <iostream>
using namespace std;
int main()
{
string temp = "aabb";
// string temp = 'abba'
int n;
c ...
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 = ...