Talk is cheap

Python之数据分析

发表于 2020-06-13 更新于 2025-01-23 分类于 Python ，数据分析

Numpy

Numpy是Python的一种开源的数值计算扩展。可以用来存储和处理大型矩阵，比Python自身的嵌套列表结构(nested list structure)要高效得多。在实际工作中直接使用情况较少。

快捷键

功能	快捷键
编辑单元格内容	【F2】
单元格内换行	【Alt】+【Enter】
设置单元格格式	【Ctrl】+【1】
Ctrl+E的众多效用（拼接单元格内容、拆分提取单元格内容、替换字符、去除空格和符号、自动换行…）	【Ctrl】+【 E】
筛选	【Ctrl】+【Shift】+【L】
输入当前日期	【Ctrl】+【;】
输入当前时间（不含日期）	【Ctrl】+【Shift】+【;】
切换sheet表	【Ctrl】+【PgUp/PgDn】
快速求和	【Alt】+【=】
数据透视表向导	【Alt+D】+【P】
隐藏行取消隐藏行	选定目标区域【Ctrl】 + 【9】【Ctrl】 + 【Shift】 + 【(】
隐藏列取消隐藏列	选定目标区域，【Ctrl】 + 【0】【Ctrl】 + 【Shift】 +【)】
展开或折叠单元格编辑栏	【Ctrl】+【Shift】+【U】
插入行删除行	【Ctrl】+【Shift】+【+】【Ctrl】+【-】
设置千位分隔符，并四舍五入为整数	【Ctrl】+【Shift】+【!】
设置百分数形式	【Ctrl】+【Shift】+【%】
设置外边框	【Ctrl】+【Shift】+【&】

绝对引用行/列

使用$符号即可绝对引用行或列

复制粘贴单元格

筛选的情况下

未被筛选的行不会被复制

隐藏的情况下

隐藏的行/列依然会被复制，想要不复制被隐藏的行/列，需要在选中指定区域后，使用【Alt】+【;】快捷键，再进行复制，即可顺利粘贴。

多个单元格中输入相同的数据

选中所有目标单元格
输入所需数据，按下【Ctrl】+【Enter】组合键即可。

多个单元格中有部分内容需要重复输入

如：邮箱后缀、电话区号、订单号前缀

希望达到效果：只需向单元格中输入不一样的内容部分，重复部分自动填充

操作：

选定需要设置的单元格范围，设置单元格格式(Ctrl + 1)
数字 - 分类 - 自定义 - 类型
输入框中填写需要的格式
1. 添加邮箱共同后缀
  
  输入@"@163.com"
2. 添加电话区号：
  
  输入"0755-"@
@用于在数字格式中包含文本，否则文本将不会显示出来

条件格式的设置

批量从身份证号中提取生日

编辑单元格：=TEXT(MID(身份证号所在单元格, 起始位数, 提取长度), "生日格式"(如0000-00-00))

筛选出重复值(唯一值)

选中需要筛选出重复值(唯一值)的范围
开始 - 样式 - 条件格式 - 突出显示单元格规则 - 重复值

去除重复值

选择需要去重的单元格区域
数据 - 数据工具 - 删除重复值

长数字输入

Excel单元格常规型数字的特殊机制
1. 输入的数字**＞11位时，自动采用科学计数法**
2. 数字的精度是15位

最佳解决方式：

设置单元格格式(Ctrl + 1) - 数字 - 分类 - 文本

冻结窗口

冻结指定的某行/列：选中需要冻结的行或列，选择视图 - 窗口 - 冻结窗格即可
冻结指定的多行以及多列：
1. 视图 - 窗口 - 拆分，会显示一个十字型的拆分参考线。
2. 移动拆分参考线至所需的行、列
3. 视图 - 窗口 - 冻结窗口

粘贴

粘贴值

文件 - 选项 - 快速访问工具栏 - 从下列位置选择命令 - 所有命令 - 粘贴值 - 添加至右侧，之后就可通过【Alt】+ 【提示的另一个键】即可实现快捷键操作。

选中整行/整列数据

选中整行数据：选定起始单元格，Ctrl + Shift + →
选中整列数据：选定起始单元格，Ctrl + Shift + ↓

数据透视表

数据透视表(Pivot Table) 是一种交互式的表，可以进行某些计算，如求和与计数等，所进行的计算与数据跟数据透视表中的排列有关。

之所以称为数据透视表，是因为可以动态地改变它们的版面布置，以便按照不同方式分析数据，也可以重新安排行号、列标和页字段。每一次改变版面布置时，数据透视表会立即按照新的布置重新计算数据。另外，如果原始数据发生更改，则可以更新数据透视表。

选择需要透视的表格区域
插入 - 表格 - 数据透视表

函数

VLOOKUP函数

按列查找，最终返回查询序列中所对应的值。

与之对应的HLOOKUP是按行查找的。

使用场景：
1. 两张表格
2. 两张表格中存在相同列
3. 表2中存在表1不具备的字段，想把表2中的字段关联到表1中
单元格中输入：=VLOOKUP(lookup_value，table_array，col_index_num，range_lookup)
1. lookup_value：查找的值
2. table_array：要查找的区域
3. col_index_num：需要返回的元素在区域中的第几列
4. range_lookup：精确匹配/近似匹配
  - 1/TRUE：近似匹配
  - 0/FALSE：精确匹配

INDEX + MATCH 函数

使用场景：

功能与VLOOKUP函数基本相同，但是能弥补VLOOKUP函数的局限性(想要关联的列在相同列的左侧时，无法匹配)。
MATCH(lookup_value, lookup_array, [match_type])
1. lookup_value：查找的值
2. lookup_array：查找区域(只能1列宽)
3. [match_type]：
  - 1：小于
  - 0：精确匹配
  - -1：大于
结果返回查找区域中的所在行数
INDEX(array, row_num, [column_num])
1. array：查找区域
2. row_num：所在行数(通过MATCH函数获取)
3. [column_num]：所在列数

AND 函数 / OR 函数

AND(logical1,[logical2],...)
OR(logical1,[logical2],...)

用于条件判断

IF 函数

IF(logical_test, [value_if_true], [value_if_false])：

logical_test：逻辑判断
[value_if_true]：结果为true时的值(字符串使用双引号标注)
[value_if_false]：结果为false时的值

例子：使用IF函数，判断业绩完成情况

单元格中输入：=IF(N4-M4>=0,"已完成", M4-N4)

IF 函数嵌套示例

=IF(AND(O4="已完成",R4="已完成"),"已完成",IF(AND(O4="已完成",R4<>"已完成"),"仅业绩完成",IF(AND(O4<>"已完成",R4="已完成"),"仅入会完成","均未完成")))

COUNTIFS 函数

COUNTIFS(criteria_range1, criteria1,...)

使用场景：

对区域中符合条件的单元格进行筛选计数。
参数：
- criteria_range1: 筛选区域
- criteria1：筛选条件
- criteria_range2
  
  …

SUMIFS 函数

SUMIFS(sum_range, criteria_range1, criteria1,...)

使用场景：

对区域中符合条件的单元格进行筛选求和。
参数：
- sum_range：求和区域
- criteria_range1：筛选区域
- criteria1：筛选条件
- criteria_range2
  
  …
求和区域和筛选区域，类似VLOOKUP函数中两张表的感觉。

LEFT、MID、RIGHT 函数

LEFT(text, [num_chars])
MID(text, start_num, num_chars)
RIGHT(text, [num_chars])
- text：文本所在单元格
- start_num：起始位置是第几个字符
- num_chars：截取的字符长度

参考

数据分析中常用的9个Excel函数 - 简书

算法题目分类

发表于 2020-02-16 更新于 2025-01-23 分类于算法

根据《算法笔记》一书，对PAT甲级、乙级真题和codeup部分试题进行分类。

1. C/C++快速入门

1.1 数组

codeup 杨辉三角

1.2 指针

codeup C语言10.16

1.3 结构体的使用

2. 入门模拟

2.1 简单模拟

不涉及算法，只是根据题目描述来编写代码，考察代码能力。

题目	解题关键
codeup 问题 B: A+B	\
B1001 害死人不偿命的(3n+1)猜想	\
B1010 一元多项式求导	\
B1011 A+B和C	\
B1012 数字分类	有条不紊地整理
B1016 部分A+B	\
B1018 锤子剪刀布	注意scanf留在缓冲区的换行符`\n`的处理
B1026 程序运行时间	\
B1032 挖掘机技术哪家强	统计各学校总分的方式
B1046 划拳	\
A1002 A+B for Polynomials	非零系数项个数的统计
A1009 Product of Polynomials	第二个多项式可边读边处理
A1042 Shuffling Machine	将扑克顺序号转为实际牌号的方式
A1046 Shortest Distance	便于计算距离的方式
A1065 A+B and C (64bit)	B1011 A+B 和 C 进阶版负数相加若溢出，可能得到0

2.2 查找元素

查找是学习写代码的一项基本功。

一般来说，如果需要在一个比较小范围的数据集内内进行查找，直接遍历即可。
如果需要查找的范围较大，可以用二分查找等算法进行更快速的查找

题目	解题关键
B1004 成绩排名	\
B1028 人口普查	1. 不合理年龄的判断方式 2. 需要考虑全不合理的情况
B1032 挖掘机技术哪家强	统计各学校总分的方式
B1041 考试座位号	\
A1011 World Cup Betting	\
A1006 Sign In and Sign Out	方法类似 B1028 人口普查
A1036 Boys vs Girls	\

2.3 图形输出

做法一般有两种：

通过规律，直接进行输出
定义一个二维字符数组，通过规律填充，然后输出整个二维数组

题目	解题关键
B1027 打印沙漏	沙漏高度和符号数量的关系
B1036 跟奥巴马一起编程	\
A1031 Hello World for U	根据 n1和n3为 $\leq$ n2，且满足 n1+n2+n3 = N+2 的最大值，求出n1，n2，n3

2.4 日期处理

需要处理好平年和闰年、大月和小月的问题，需要细心处理。

闰年的判断方法：

非整百年：能被4整除为闰年
整百年：能被400整除的是闰年（1900年不是闰年）

codeup 问题 A: 日期差值

2.5 进制转换

对一个P进制的数，如果要转换为Q进制，需要分两步：

将 P进制数x 转换为十进制数y

int y = 0, pro = 1;
while(x != 0) {
    y += (x % 10) * pro;
    x /= 10;
    pro *= p;
}

将十进制数y 转换为 Q进制数z

采用除基取余法
```
int z[40], num = 0; //数组z 存放 Q进制数y 的每一位，num为位数
do {
    z[num++] = y % Q; //除基取余
    y /= Q;
} while(y != 0);
```
使用do···while语句而不是while的原因是：如果十进制数y = 0，使用while语句将使循环直接跳出，导致结果出错。

题目	解题关键
B1022 D进制的A+B	除基取余法
B1037 在霍格沃茨找零钱	\
A1019 General Palindromic Number	\
A1027 Colors in Mars	\
A1058 A+B in Hogwarts	题型同乙级1037 在霍格沃茨找零钱单位转换过程可能会超过int范围

2.6 字符串处理

考察代码能力的题型。一般需要仔细分析清楚题目中的输入和输出格式才能顺利AC。

有些题目中，可能实现逻辑非常麻烦，有很多细节和边界情况，此类题目需要多做多想，积累经验。

题目	解题关键
B1002 写出这个数	数字转为字符串： C语言：`sprintf(str, "%d", num)` C++：`to_string(num)`
B1006 换个格式输出整数	\
B1009 说反话	句子颠倒，单词本身不颠倒 C++ 待更新
B1014 福尔摩斯的约会 A1061 Dating	正确归纳解码方式
B1021 个位数统计	\
B1024 科学计数法 A1073 Scientific Notation	1. 利用正则表达式，分开读取数字部分和指数部分 2. 指数 < 0：整数部分必然为 0 3. 指数 >= 0： - 仍有小数点，何时输出小数点 - 没有小数点，后续输出0
B1031 查验身份证	\
B1048 数字加密	1. 对齐两个整数 - 若加密正整数A 比 B 长，B高位补0后进行加密 - 若加密正整数A 比 B 短，B多余的部分正常输出，等同于A高位补0后进行加密 2. 结果从数字高位(字符串低位)开始输出
A1001 A+B Format	从数字高位(字符串低位)开始，需要添加`,`的位置满足`(i + 1) % 3 == len % 3` 且不是最后一位
A1005 Spell It Right	\
A1035 Password	(待优化)
A1077 Kuchiguse	1. 通过`reverse()`反转字符串，将后缀转换为前缀，便于比较 2. `getline()`之前注意读取换行符。
A1082 Read Number in Chinese	1. 四位数字分为一节，单位为个、万、亿 2. 一节中数字全为0，则不输出节的单位 3. 节中第一个非零数之前有0，则输出1个0

3. 算法初步

3.1 排序

3.1.1 简单选择排序（$O(n^2)$）

简单选择排序是指，对一个序列A中的元素A[0] ~ A[n-1]，令i从 0 到 n-1 枚举，进行 n 趟操作，每一趟从待排部分$[i, n-1]$中选择最小元素（记录下标），令其与待排部分的**第一个元素A[i]**进行交换，使得$[0, i]$区间有序。

void selectSort(int A[]) { //降序 简单选择排序
    for(int i = 0; i < n; i++) {
        int k = i;
        for(int j = i; j < n; j++) { //选出最小的元素
            if(A[j] < A[i])
                k = j; //记录更小元素的下标
        }
        int tmp = A[i]; //交换A[k]与A[i]
        A[i] = A[j];
        A[j] = tmp;
    }
}

3.1.2 直接插入排序（$O(n^2)$）

直接插入排序是指，对序列A的n个元素A[0]~A[n-1]，令 i **从 1 **到 n-1 枚举，进行 n - 1 趟操作。

某一趟时，序列A的前 i 个元素 A[0]~A[i-1]已经有序，则该趟在范围$[0, i - 1]$中，从后往前寻找某个位置j，使得A[i]插入后，范围$[0, i]$有序(A[j]~A[i]后移一位)。

void insertSort(int A[]) { //升序 直接插入排序
    for(int i = 1; i < n; i++) {
        int tmp = A[i], j = i;
        //从后往前遍历，便于编写代码
        while(j > 0 && tmp < A[j - 1]) {
            A[j] = A[j - 1];
            j--;
        }
        A[j] = tmp;
    }
}

3.1.3 冒泡排序（$O(n^2)$）

冒泡排序的本质在于交换，即每次通过交换的方式把当前剩余元素的最大值(升序)移动到一端，当剩余元素减少到0时，排序结束。整个过程执行 n-1 趟，每一趟从左到右依次比较相邻的元素，如果大的数在左边，则交换，该趟结束时，最大数被移动到当前剩余数的最右边。

void bubbleSort(int A[]) { //升序 冒泡排序
    for(int i = 1; i < n; i++) {//进行 n - 1 趟排序
        for(int j = 0; j < n - i; j++) {
            if(a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

3.1.4 排序题与sort函数的应用

PAT中的排序题，大部分只需要得到排序的最终结果，而不需要去写排序的完整过程(例如冒泡排序、快速排序等)，因此推荐直接使用C语言的库函数qsort或是C++的sort函数进行排序。qsort函数的使用需要运用指针，且写法上没有sort函数简洁。sort函数根据具体情形使用不同的排序方法，效率较高，在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到$O(n^2)$的极端情况。

因此更推荐使用C++的sort函数进行代码编写。

结构体数组的排序

struct node {
    int x;
    int y;
} ssd[10];

如果想先按x从大到小排序，在x相等的情况下，按y从小到大排序(即二级排序)，cmp的写法是：

bool cmp(node a, node b) { //返回值为true时，a排在b之前
    if(a.x != b.x) {
        return a.x > b.x; //降序
    } else {
        return a.y < b.y; //升序
    }
}

排名的实现

很多排序题要求在排序之后计算每个个体的排名，规则一般是：分数相同的排名相同，占用一个排位。例如有5个学生的分数分别为90、88、88、88、86，其排名分别为1、2、2、2、5。

方法：

将第一个个体排名记为1，遍历剩余个体，如果当前分数等于上一个个体的分数，则当前个体排名等于上一个个体的排名，否则当前个体的排名等于数组下标+1

题目	解题关键
B1015 德才论 A1062 Talent and Virtue	设置flag作为考生的分类，便于所有考生统一排序
A1012 The Best Rank	1. 利用全局变量设计cmp函数 2. 通过记录所有科目的排名，最后选出最好的排名以及对应科目 3. 相同分数者排名相同，下一不同分数者排名为数组下标+1
A1016 Phone Bills	（待优化） 1. 通话记录统一先排序后处理 2. 连续的两个通话记录，判断是否为同一用户且为先通话后挂断的状态 3. 通话时长的统计方法 4. 单位美分cents 要转换为美元$
A1025 PAT Ranking	\
A1028 List Sorting	\
A1055 The World’s Richest	超时问题。要求输出的人数$\leq$100，通过筛去每个年龄多余的人解决
A1075 PAT Judge	(待优化) 1. 不能编译的提交得分为0 2. 没有提交过的答案需要输出为`-`，利用`<cstring>`中的`memset`函数，为得分数组赋值 -1，表示没有提交过答案 3. 没有任何一题通过编译或没有提交过答案的人不记录排名，设置是否有通过编译的标识，进行筛选 4. 读取数据时，将用户数组下标看作id，便于统计 5. 排序以是否有通过编译为第一排序条件
A1080
A1083
A1095

3.2 散列

3.2.1 散列(hash)的定义与整数散列

例题:

给出$N$个正整数，再给出$M$个正整数，问这$M$个数中的每个数分别是否在$N$个数中出现过，其中 $N, M \leq10^5$，且所有正整数均不超过$10^5$。例如 $N = 5，M = 3$， $N$个正整数为 ${8， 3， 7， 6， 2}$，欲查询的$M$个正整数为 ${7， 4， 2}$。

对这个问题，最直观的思路是：对每个欲查询的正整数$x$，遍历所有$N$个数，看是否有一个数与$x$相等。这种做法的时间复杂度为$O(NM)$，显然不是好方法。可以采取用空间换时间的方式，用数组下标作为对应整数的标识，即设定一个bool型数组hashTable[100001]，其中hashTable[x] == true表示正整数$x$在$N$个整数中出现过。这样就可以在一开始读入$N$个正整数时进行预处理。于是，对$M$个欲查询的数，就能直接通过hashTable数组判断出每个数是否出现过，这种做法的时间复杂度为$O(N+M)$。直接把输入的数作为数组的下标来对这个数的性质进行统计的方法非常实用，务必掌握。

但是这个方法有一个问题：如果输入的整数可能是$10^9$大小，甚至是字符串，就不能将其直接作为数组下标了。因此我们寻找一种做法，将元素通过一个函数转换为一个在能接受范围内的整数，使得该整数尽可能唯一地代表这个元素。这样的方法称为散列(hash)，用于转换的函数称为散列函数H，也就是说，如果元素在转换前为key，那么转换后就是一个整数H(key)。

散列函数

对key是整数的情况来说，常用的散列函数有：

直接定址法
- 恒等变换，即 H(key) = key
- 线性变换，即 H(key) = a * key + b
除留余数法

把key除以一个数mod得到的余数作为 hash值的方法，即 H(key) = key % mod

通过这个散列函数，可以把很大的数转换为不超过 mod 的整数，这样就可以将它作为可用的数组下标。显然，当mod是一个素数时，H(key)能尽可能覆盖[0,mod]范围内的每一个数。
平方取中法(很少用)

取key的平方的中间若干位作为hash值

冲突

当两个不同的数key1和key2他们的hash值相同时，这样的情况称为冲突。解决冲突的常用方法：

开放定址法(获取新的hash值)
- 线性探查法 (Linear Probing)
  
  当表中下标为H(key)的位置已经被其他元素占用，则检查下一个位置H(key)+1，以此类推。如果检查过程中超过了表长m，那么就回到表的首位继续循环，直到找到一个可用的位置，或是所有位置都已经被使用。
  
  H = (H(key) + i) % m；(i = 0, 1, 2, …, m-1)
  
  缺点：容易导致大量元素在相邻的散列地址上“聚集”(堆积)，大大降低查找效率。
- 平方探查法 (Quadratic Probing)
  
  当表中下标为H(key)的位置已经被其他元素占用，则按如下顺序检查表中位置
  
  H = (H(key) + i) % m；i = $0, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2;(k \leq m/2)$
  
  可避免聚集问题。
  
  缺点：不能探测到散列表上所有单元(但至少能探测到一半单元)。
- 再散列法(双散列法)
  
  H = (H1(key) + i * H2(key)) % m；i 是冲突次数
链地址法 (拉链法)

不计算新的hash值，而是把 所有H(key)相同的key(称为同义词) 存储在一个线性链表中，由散列地址唯一标识。

一般来说，可以使用**标准库模板库中的map**来直接使用hash的功能（C++11以后可以用 unordered_map，速度更快），因此除非必须模拟这些方法或是对算法的效率要求比较高，一般不需要自己实现上面解决冲突的方法。

3.2.2 字符串hash初步

如果**key不是整数**，应该如何设计散列函数？

例题：

如何将一个二维整点$P$的坐标映射为一个整数，使得整点$P$可以由该整数唯一标识？

假设一个整点$P$的坐标是$(x,y)$，其中$0\leq x,y\leq Range$，那么可以令hash函数为H(P) = x * Range + y，这样对数据范围内的任意两个整点$P1$与$P2$，H(P1)都不会等于H(P2)，就可以用H(P)来唯一地标识该整点P，接着便可以通过整数hash的方法进一步映射到较小的范围。

字符串hash是指将一个字符串S映射为一个整数，使得该整数可以尽可能唯一地代表字符串S。

为了讨论问题方便，假设字符串均由大写字母A~Z构成，不妨把 A~~Z 视为 0~~25。接着按照26进制转换为10进制的思路，实现将字符串映射为整数的需求(转换成的整数最大为$26^{len}-1$，len为字符串长度)。

int hashFunc(char S[], int len) { //将字符串S转换为整数
    int id = 0;
    for(int i = 0; i < len; i++)
		id = id * 26 + (S[i] - 'A'); //将26进制转换为10进制
    return id;
}

为了避免转换成的整数过大，需要注意字符串长度len 不能太长。如果字符串中还有小写字母，可以把 A~~Z 作为 0~~25，把 a~~z 作为 26~~51，这样就变成了52进制转换为10进制的问题。

int hashFunc(char S[], int len) {
    int id = 0;
    for(int i = 0l i < len; i++) {
        if(isupper(S[i])) {
            id = id * 52 + (S[i] - 'A');
        } else if(islower(S[i])) {
            id = id * 52 + (S[i] - 'a');
        }
    }
    return id;
}

如果字符中还有数字，一般有两种处理方法：

按照小写字母的处理方法，增大进制数至62。

如果保证在字符串的末尾是个确定的数字，就可以把前面英文字母的部分按上面的思路转换成整数，再将末尾的数字直接拼接上去。

int hashFunc(char S[], int len) {
    int id = 0;
    for(int i = 0; i < len - 1; i++)
        id = id * 26 + (S[i] - 'A');
   	id = id * 10 + (S[len - 1] - '0');
    return id;
}

例题：

给出N个字符串(由三位大写字母组成)，再给出M个查询字符串，问每个查询字符串在N个字符串中出现的次数。

#include <iostream>
using namespace std;

int hashFunc(char S[], int len) { //将字符串S转换为整数
    int id = 0;
    for(int i = 0; i < len; i++)
		id = id * 26 + (S[i] - 'A'); //将26进制转换为10进制
    return id;
}

int main() {
    int N, M;
    int hashTable[26 * 26 * 26] = {0};
    cin >> N >> M;
    string S[N];
    for(int i = 0; i < N; i++) {
        cin >> S[i];
        int id = hashFunc(S[i], 3);
        hashTable[id]++; //字符串出现的次数+1
    }
    string tmp;
    for(int i = 0; i < M; i++) {
        cin >> tmp;
        int id = hashFunc(tmp, 3);
        cout << hashTable[id] << endl; //输出字符串出现的次数
    }
    return 0;
}

3.2.3 相关习题

题目	解题关键
B1005 继续(3n+1)猜想	奇数在判断过程中，可能大小会超过100
B1029 旧键盘 A1084 Broken Keyboard	待优化
B1033 旧键盘打字	不能用`scanf`或`cin`读取字符串，应采用`gets(str)`或`getline(cin, str)`，因为题目只保证第 2 行输入的文字串非空
B1038 统计同成绩学生	\
B1039 到底买不买 A1092 To Buy or Not to Buy	\
B1042 字符统计	\
B1043 输出PATest	\
B1047 编程团体赛	\
A1041
A1050
A1048

3.3 递归

3.3.1 分治

分治(divide and conquer)的全称为“分而治之”。分治法将原问题划分成若干个规模较小而结构与原问题相同或类似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解。分治法的三个步骤：

分解：将原问题分解为若干和原问题拥有相同或相似结构的子问题。
解决：递归求解所有子问题。如果存在子问题的规模小到可以直接解决，就直接解决它。
合并：将子问题的解合并为原问题的解。

分治法分解出的子问题应当是相互独立、没有交叉的。如果存在两个子问题有相交部分，就不应该使用分治法解决。分治法作为一种算法思想，既可以使用递归的手段实现，也可以通过非递归的手段实现。一般来说，使用递归实现较为容易。

3.3.2 递归

递归很适合用来实现分治思想。

递归的逻辑中一般有两个重要概念：

递归边界
递归调用

其中递归调用是将原问题分解为若干个子问题的手段，而递归边界则是分解的尽头。递归的代码结构中一定存在这两个该概念，它们支撑起了整个递归最关键的逻辑。

经典例子1：使用递归求解n的阶乘

#include <iostream>
using namespace std;

int F(int n) {
    if(n == 0) {
        return 1;
    } else {
        return n * F(n-1);
    }
}

int main() {
    int n;
    cin >> n;
    cout << F(n) << endl;
    return 0;
}

经典例子2：求 Fibonacci 数列的第n项

Fibonacci 数列(即斐波那契数列) 是满足 F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2) (n $\geq$ 2) 的数列，数列的前几项为 1, 1, 2, 3, 5, 8, 13, 21, … 。

从定义中可以获知递归边界为 F(0) = 1 和 F(1) = 1，且递归调用为 F(n) = F(n-1) + F(n-2) (n $\geq$ 2) ，因此可以仿照求解n的阶乘的写法。

#include <iostream>
using namespace std;

int F(int n) {
    if(n == 0 || n == 1) { //递归边界
        return 1;
    } else {
        return F(n-1) + F(n-2);
    }
}

int main() {
    int n;
    cin >> n;
    cout << F(n) << endl;
    return 0;
}

最后来看全排列(Full Permutation)。全排列指n个整数能形成的所有排列。

现在需要按字典序从小到大的顺序输出$1\sim n$的全排列，其中$(a_1, a_2, …, a_n)$的字典序小于$(b_1, b_2, …, b_n)$是指存在一个$i$，使得$a_1=b_1$、$a_2 = b_2$、…、$a_{i-1} = b_{i-1}$、$a_i < b_i$成立。

从递归的角度考虑，就可以分为若干个子问题：“输出以1开头的全排列”、“输出以2开头的全排列” … “输出以n开头的全排列”。不妨设定一个数组P，用来存放当前的排列；再设定一个散列数组hashTable，其中hashTable[x]，当整数x已经在数组P中时，为1。

按顺序往P的第1位到第n位中填入数字。不妨假设当前已经填好了P[1] ~ P[index-1]，正准备填P[index]。显然需要枚举 1 ~ n，如果当前枚举的数字x还没有在P[1] ~ P[index-1]中(即hashTable[x] == 0)，那么就把它填入P[index]，同时将hashTable[x]置为1，然后去处理P的第index + 1位(即进行递归)；当递归完成时，再将hashTable[x]还原为0，以便让P[index]填下一个数字。

那么递归边界是什么呢？显然，当index达到n + 1时，说明P的的第1 ~ n位都已经填好了，此时可以把数组P输出，表示生成了一个排列，然后直接return即可。下面给出n = 3时的代码：

#include <iostream>
using namespace std;

void generateP(int index, int n) {
    if(index == n + 1) { //递归边界，已经处理完排列的 1~n 位
		for(int i = 1; i <= n; i++)
            cout << P[i];
        cout << endl;
        return;
    }
    for(int x = 1; x <= n; x++) { //枚举 1~n，试图将 x 填入 P[index]
        if(hashTable[x] == 0) { //如果 x 不在 P[1] ~ P[index - 1] 中
            P[index] = x; //令 P 的第 index 位为 x，即把x加如当前排列
            hashTable[x] = 1; //记 x 已在 P 中
            generateP(index + 1, n); //处理排列的第 index + 1 号位
            hashTable[x] = 0; //已处理完 P[index] 为 x 的子问题，还原状态
        }
    }
}


int main() {
    int n = 3, P[11], hashTable[11] = {0};
	generateP(1); //从P[1]开始填
    return 0;
}

最后的最后来看**$n$皇后问题**。$n$皇后问题是指在一个$nn$的国际象棋棋盘上放置$n$个皇后，使得这$n$个皇后*两两均不在同一行、同一列、同一条对角线上，求合法的方案数。

对于这个问题，如果采用组合数的方式来枚举每一种情况(即从$n^2$个位置中选择$n$个位置)，那么需要$C_{n\times n}^n$的枚举量。但是换个思路，考虑到每行只能放置一个皇后、每列也只能放置一个皇后，如果把n列皇后所在的行号依次写出，那么就会是$1 \sim n$的一个排列。于是只需要枚举$1 \sim n$的所有排列，查看每个排列对应的放置方案是否合法，统计其中合法的方案即可。

于是可以在全排列的代码基础上进行求解。由于当达到递归边界时表示生成了一个排列，所以需要在起内部判断是否为合法方案，即遍历每两个皇后，判断它们是否在同一条对角线上(显然不在同一行和同一列)，若不是，则累计计数变量cnt即可。主要代码如下：

int cnt = 0;

void generateP(int index) {
    if(index == n + 1) { //递归边界，生成一个排列
        int flag = 1; //flag为true表示当前排列为一个合法方案
        for(int i = 1; i <= n; i++) { //遍历任意两个皇后
            for(int j = i + 1; j <= n; j++) {
                if(abs(i - j) == abs(P[i] - P[j])) //如果在一条对角线上
                    flag = 0;
            }
        }
        if(flag) //当前方案合法
            cnt++;
    	return;
    }
    for(int x = 1; x <= n; x++) {
        if(hashTable[x] == 0) {
            P[index] = x;
            hashTable[x] = 1;
            generateP(index + 1);
            hashTable[x] = 0;
        }
	}
}

这种枚举所有情况，然后判断每一种情况是否合法的朴素做法称为暴力法。

通过思考可以发现，当已经放置了一部分皇后时，可能剩余的皇后无论怎样放置都不可能合法，就不需要继续递归，直接返回上层即可。这种做法称为回溯法。

void generateP(int index) {
    if(index == n + 1) { //递归边界，生成一个 合法方案
        cnt++;
        return;
    }
    for(int x = 1; x <= n; x++) { //第 x 行
        if(hashTable[x] == 0) { //第 x 行还没有皇后
            int flag = 1; //flag 为 1 表示当前皇后不会和之前的皇后冲突
            for(int pre = 1; pre < index; pre++) { //遍历之前的皇后
				if(abs(index - pre) == abs(x - P[pre])) {
                    flag = 0; //与之前的皇后在一条对角线冲突
                    break;
                }
            }
            if(flag) { //如果可以把皇后放在第 x 行
                P[index] = x; //令第 index 列皇后的行号为 x
                hashTable[x] = 1; //第 x 行已被占用
                generateP(index + 1); //递归处理第 index + 1 行皇后
                hashTable[x] = 0; //递归完毕，还原第 x 行 为 为占用
            }
        }
	}
}

3.4 贪心

3.4.1 简单贪心

贪心法是求解一类最优化问题的方法，它总是考虑在当前状态下局部最优(或较优)的策略，来使全局的结果达到最优(或较优)。要获得最优结果，要求中间的每步策略都是最优的，因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法，即假设策略不能导致最优解，然后通过一系列推导来得到矛盾，以此证明策略是最优的，最后用数学归纳法保证全局最优。不过对平常使用来说，也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪心本身更难)，因此一般来说，如果在想到某个似乎可行的策略，并且自己无法举出反例，那么就勇敢的实现它。

3.4.2 区间贪心

区间不相交问题：给出$N$个开区间$(x, y)$，从中选择尽可能多的开区间，使得这些开区间两两没有交集。例如对开区间$(1, 3)$、$(2,4)$、$(3, 5)$、$(6, 7)$来说，可以选出最多三个区间$(1, 3)$、$(3, 5)$、$(6, 7)$，它们互相没有交集。

首先考虑最简单的情况，如果开区间$I_1$被开区间$I_2$包含(如图4-5a所示)，则选择$I_1$是最好的选择，因为这样就有更大的空间去容纳其他开区间。

接下来把所有开区间按左端点$x$从大到小排序，如果去掉区间包含的情况，那么一定有$y_1 > y_2 > … > y_n$成立(如图4-5b所示)。观察发现，$I_1$右边有一段一定不会和其他区间重叠，如果把它去掉，那么$I_1$的左边剩余部分就会被$I_2$包含，由图4-5a的情况可知，应当选择$I_1$。因此对这种情况，总是先选择左端点最大的区间。值得注意的是，总是先选择右端点最小的区间的策略也是可行的。

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 110;

struct Inteval {
    int x, y; //开区间左右端点
} I[maxn];

bool cmp(Inteval a, Inteval b) {
    if(a.x != b.x) { //先按左端点从大到小排序
        return a.x > b.x; 
    else { //左端点相同的 按右端点从小到大排序
        return a.y > b.y;
    }
}
    
int main() {
    int n;
    while(cin >> n, n != 0) {
        for(int i = 0; i < n; i++)
            cin >> I[i].x >> I[i].y;
    sort(I, I + n, cmp);
    int cnt = 1, lastX = I[0].x; //记录不相交区间的个数，上一个被选中区间的左端点
    for(int i = 1; i < n; i++) {
        if(I[i].y <= lastX) { //如果该区间右端点在 lastX 左边
            lastX = I[i].x; //以 I[i] 作为新选中的区间
            cnt++; //不相交区间个数加1
        }
        cout << cnt << endl;
    }
    return 0
}

与这个问题类似的是区间选点问题：给出$N$个闭区间$[x, y]$，求最少需要确定多少个点，才能使每个闭区间中都至少存在一个点。例如对闭区间$[1,4]$、$[2, 6]$、$[5, 7]$来说，需要两个点(例如3、5)才能保证每个闭区间内都有至少一个点。

事实上，这个问题和区间不相交问题的策略是一致的。首先，回到图4-5a，如果闭区间$I_1$被闭区间$I_2$包含，那么在$I_1$中取点可以保证这个点一定在$I_2$内。接着把所有区间按左端点从大到小排序，去除掉区间包含的情况，就可以得到图4-5b。由于每个闭区间中都需要存在一个点，因此对左端点最大的区间$I_1$来说，取左端点就能让它尽可能多地覆盖其他区间。区间选点问题的代码只需要把区间不想交问题代码中的I[i].y <= lastX改为I[i].y < lastX即可。

总的来说，不是所有问题都适合使用贪心法，但是这并不妨碍贪心算法称为一个简洁、实用、高效的算法。

3.4.3 相关习题

题目	解题关键
B1020 月饼 A1070 Mooncake	库存量和售价都应该定义为double类型
B1023 组个最小数	\
A1033 To Fill or Not to Fill	能到达的距离内，由近到远遍历，有三种情况： 1. 最近距离的加油站都到不了 2. 出现油价比目前低的加油站，就直接去 2.1 油不够，只加能刚好到达的油量 2.2 不用加油 3. 没有更低价的加油站，就加满油(能尽量少加更贵的油)，去价格相对最低的加油站
A1037
A1038
A1067

3.5 二分

3.5.1 二分查找

二分查找的高效之处在于，每一步都可以去除当前区间中的一半元素，因此其时间复杂度是$O(\log n)$，这是十分优秀的。

在严格递增序列中查找给定的数$x$的做法：

#include <iostream>
using namespace std;

int binarySearch(int A[], int left, int right, int x) {
    int mid;
    while(left <= right) {
        mid = (left + right) / 2;
        if(A[mid] == x) {
            return mid;
        } else if(A[mid] > x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1; //查找失败
}

int main() {
    int A[n] = {1, 3, 4, 6, 7, 8, 10, 11, 12, 15};
    printf("%d %d\n", binarySearch(A, 0, n - 1, 6), binarySearch(A, 0, n - 1, 9));
    return 0;
}

需要注意的是，如果过二分上界超过int型数据范围的一半，当欲查询元素在序列较靠后位置时，语句mid = (left + right) / 2中的left + right就有可能超过int而导致溢出，通常使用等价语句mid = left + (right - left) / 2作为代替，以避免溢出。另外，二分法可以使用递归进行实现，但在程序设计时，更多采用非递归的写法。

接下来探讨更进一步的问题：如果递增序列$A$中的元素可能重复，那么如何对给定的欲查询元素$x$，求出序列中第一个$\geq x$的元素位置$L$以及第一个$>x$的元素的位置$R$，这样元素$x$在序列中的存在区间就是$[L, R)$。

例如对下标从0开始、有5个元素的序列${1,3,3,3,6}$来说，如果要查询3，则应当得到$L = 1$、$R = 4$；如果查询 5，则应当得到$L = R = 4$。如果序列中没有$x$，$L$和$R$也可以理解为假设序列中存在$x$，则$x$应当在的位置。

先来考虑第一个小问：求序列中的第一个$\geq x$的元素位置。

若A[mid] >= x，说明第一个$\geq x$的元素的位置一定在**mid处或mid的左侧，应往左子区间[left, mid]继续查询，即令right = mid**
若A[mid] < x，说明第一个$\geq x$的元素的位置一定在**mid右侧，应往右子区间[mid+1, right]继续查询，即令left = mid + 1**

int lower_bound(int A[], int left, int right, int x) {
    int mid;
    while(left < right) {
        mid = (left + right) / 2;
        if(A[mid] >= x) { //中间值 >= x
            right = mid;
        } else { //中间值 < x
            left = mid + 1;
        }
    }
    return left; //返回夹出来的位置
}

上述代码有两个需要注意的地方：

循环条件为left < right，而不是之前的left <= right，这是由问题本身决定的。因为如果想要返回第一个>= x的元素的位置，就不需要判断元素x本身是否存在。
二分的初始区间应当能覆盖到所有可能返回的结果，考虑到欲查询元素可能比序列中所有元素都大，此时应当返回n，因此二分上界是n，故二分的初始区间为[left, right] = [0, n]。

接下来解决第二小问：求序列中第一个大于x的元素的位置。

int upper_bound(int A[], int left, itn right, int x) {
    int mid;
    while(left < right) {
        mid = (left + right) / 2;
        if(A[mid] > x) {
            right = mid;
        } else {
            left = mid + 1；
        }
    }
    return left; //返回夹出来的位置
}

lower_bound和upper_bound函数都在解决这样一个问题：寻找有序序列中第一个满足某条件的元素的位置。这是一个非常重要且经典的问题，平时能碰到的大部分二分法问题都可以归结于这个问题。

3.5.2 二分法拓展

首先介绍如何计算$\sqrt2$的近似值。

对$f(x) = x^2$来说，在$x \in [1, 2]$范围内，$f(x)$随着$x$的增大而增大，这就给使用二分法创造了条件。

以精确到$10^{-5}$为例，令浮点型left和right的初值分别是 1 和 2，然后根据中点mid处$f(x)$的值与 2 的大小来选择子区间进行逼近：

若f(mid) > 2，说明mid > $\sqrt2$，令right = mid
若f(mid) < 2，说明mid < $\sqrt2$，令left = mid

上面两个步骤当right - left < $10^{-5}$时结束，显然当left与right的距离 < $10^{-5}$ 时已满足精度要求，mid即为所求的近似值。

const double eps = 1e-5; //精度为 10^{-5}，科学计数法

double f(double x) {
    return x * x;
}

double calSqrt() {
	double left = 1, right = 2, mid;
    while(right - left > eps) {
        mid = (left + right) / 2;
        if(f(mid) > 2) { //即 mid > sqrt(2)
            right = mid;
        } else {
            left = mid;
        }
    }
    return mid;
}

事实上，计算$\sqrt2$的近似值的问题是这样一个问题的特例：给定一个定义在$[L, R]$上的单调函数$f(x)$，求方程f(x) = 0的根。

同样假设精度要求为eps = $10^{-5}$，函数$f(x)$在$[L,R]$上递增，令left与right的初值分别为$L$、$R$。根据中点mid的函数值f(mid) 与 0 的大小关系来判断往哪个子区间继续逼近f(x) = 0的根：

若f(mid) > 0，说明f(x) = 0的根在mid左侧，应往左子区间继续逼近，即令right = mid
若f(mid) < 0，说明f(x) = 0的根在mid右侧，应往右子区间继续逼近，即令left = mid

const double eps = 1e-5; //精度为 10^{-5}，科学计数法

double f(double x) {
    return ...;
}

double solve() {
	double left = L, right = R, mid;
    while(right - left > eps) {
        mid = (left + right) / 2;
        if(f(mid) > 0) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return mid; //f(x) = 0 的根
}

3.5.3 快速幂

3.5.4 相关习题

题目	解题关键
A1010 Radix	1. 基数上界为已确认数字的十进制大小 + 1 与下界中的较大值（确保不会出现多个解(而且基数不确定的数，只有一位数的时候才可能多个解) ) 2. 基数过大时，数值转换为十进制会发生上溢，存储结果为负数
A1044
A1048

3.6 tow pointers

3.6.1 什么是two pointers

3.6.2 归并排序

3.6.3 快速排序

3.6.4 相关习题

题目	解题关键
B1030 完美数列 A1085 Perfect Sequence	\
B1035 插入与归并 A1089 Insert or Merge	1. 插入排序：未排序部分和初始序列一定相同 2. 归并排序：末尾不足数量的子序列同样需要排序 3. 插入排序更容易判断，将其作为判断排序类型的切入点 4. 插入和归并排序的实际操作由排序函数`sort`/`qsort`代替
A1029
A1048

3.7 其他高效技巧与算法

3.7.1 打表

3.7.2 活用递推

3.7.3 随机选择法

3.7.4 相关习题

题目	解题关键
B1040 有几个PAT A1093 Count PAT’s	1. A前有P，后有T才能形成PAT； 2. 当前A能构成的PAT数量 = 之前P的数量 * 之后T的数量 3. 突破口：先遍历一遍，获取T的数量
B1045 快速排序 A1101 Quick Sort	1. 可能的主元：左侧的最大值比自身小；右侧的最小值比自身大 2. 输出即使没有主元，也得换行

4. 数学问题

4.1 简单数学

题目	解题关键
B1003
B1019 A1069
B1049 A1104
A1008
A1049

4.2 最大公约数与最小公倍数

题目	解题关键
B1008

4.3 分数的四则运算

题目	解题关键
B1034 A1088
A1081

4.4 素数

题目	解题关键
B1007
B1013
A1015
A1078

4.5 质因子分解

题目	解题关键
A1059
A1096

4.6 大整数运算

题目	解题关键
A1023
A1024

4.7 扩展欧几里得算法

4.8 组合数

5. C++标准模板库介绍

5.1 vector

题目	解题关键
A1039
A1047

5.2 set

题目	解题关键
A1063

5.3 string

题目	解题关键
A1060

5.4 map

题目	解题关键
B1044 A1100
A1022
A1054
A1071

5.5 queue

5.6 priority_queue

5.7 stack

5.8 pair

5.9 algorithm

6. 数据结构专题1

6.1 栈的应用

题目	解题关键
A1051 Pop Sequence	1. 可能会发生堆栈溢出 2. 栈顶元素和当前需要出栈的元素相同时，出栈。该判断之前必须先判断栈是否不为空(否则会报错) 3. 标记出栈序列中待出栈元素下标，最终标记只有超出序列下标，才可能是出栈序列

6.2 队列的应用

题目	解题关键
A1056 Mice and Rice	1. 输入的第二行是按老鼠的序号给出的重量。第三行给出的是老鼠的序号，而不是按序号给出的比赛序号 2. 用队列记录老鼠的序号(而不是记录老鼠的结构体，有利于减少内存的占用)，晋级的老鼠重新入队 3. 最后的分组中，老鼠数量可能不足(利用<cmath>中的`ceil`函数向上取整)

6.3 链表处理

题目	解题关键
B1025 反转链表 A1074 Reversing Linked List	1. 通过数组下标来表示地址，便于链接各个节点 2. 可能存在无效结点 3. 只根据链表顺序的地址进行反转，有利于节约开销
A1032 Sharing	\
A1052 Linked List Sorting	存在无有效结点的情况
A1097

7. 搜索专题

7.1 深度优先搜索DFS

题目解题关键

A1103 Integer Factorization 1. 利用vector(可根据size函数确认符合要求的元素个数)，预先存储所有 ≤ N的元素(整数的P次幂值)
2. 为了保证底数最大的序列被选中，从大到小遍历
3. DFS函数的参数：当前元素下标，已选元素数量，已选元素之和，已选元素的底数之和
4. DFS函数的递归边界：已选元素数量为K且和为N
5. DFS函数的递归调用：选择当前元素和不选择当前元素
6. 剪枝：和超过N 或已选元素数量超过K 或遍历完底数序列时，不必再递归

题目	解题关键
A1103 Integer Factorization	1. 利用`vector`(可根据`size`函数确认符合要求的元素个数)，预先存储所有 ≤ N的元素(整数的P次幂值) 2. 为了保证底数最大的序列被选中，从大到小遍历 3. DFS函数的参数：当前元素下标，已选元素数量，已选元素之和，已选元素的底数之和 4. DFS函数的递归边界：已选元素数量为K且和为N 5. DFS函数的递归调用：选择当前元素和不选择当前元素 6. 剪枝：和超过N 或已选元素数量超过K 或遍历完底数序列时，不必再递归

7.2 广度优先搜索BFS

题目解题关键

A1091 Acute Stroke 1. 设定相对当前位置的前后左右上下6个方向的增量，便于枚举
2. 设置数组inq记录当前位置是否入过队
3. 越界、当前位置为0、已入过队的位置无需再判断。
4. 在BFS函数中，利用队列进行BFS，使用STL的queue，push函数只将所选元素的副本入队，后续对原元素的操作不改变队列中的副本。

题目	解题关键
A1091 Acute Stroke	1. 设定相对当前位置的前后左右上下6个方向的增量，便于枚举 2. 设置数组`inq`记录当前位置是否入过队 3. 越界、当前位置为0、已入过队的位置无需再判断。 4. 在BFS函数中，利用队列进行BFS，使用STL的`queue`，`push`函数只将所选元素的副本入队，后续对原元素的操作不改变队列中的副本。

8. 数据结构专题2

8.1 树与交叉树

8.2 二叉树的遍历

题目	解题关键
A1020 Tree Traversals	\
A1086 Tree Traversals Again	先序序列相当于入栈次序；中序序列相当于出栈次序
A1102 Invert a Binary Tree	1. 题目给的是结点编号的关系，故采用静态链表存储二叉树 2. 反转二叉树即每个结点的左右子树对换，选择后序遍历

8.3 树的遍历

题目	解题关键
A1004 Counting Leaves	1. 利用数组存储每层的叶结点个数 2. 根据出队结点的层数，获取最大层数，遍历输出每层叶结点个数
A1053 Path of Equal Weight	1. 输出的路径序列要求降序，因此在读入结点时就将孩子节点按权重降序排序，这样，之后遍历时得到的路径即为降序 2. 利用`vector`的`begin`和`end`函数获得`vector`的首元素地址和尾后地址，用于`sort`函数排序 3. 利用`vector`存储路径，在递归子结点之前，用`push_back`函数将子结点加入路径，递归回溯后，用`pop_back`将先前加入的子结点移出路径
A1079 Total Sales of Supply Chain	1. 静态写法表示树，即用数组下标指代结点 2. 结点的结构体中设有货物量变量，用来判断是否为零售商（本题采用了BFS；也可DFS）
A1090 Highest Price in Supply Chain	由于不涉及结点的数据域，可以直接用`vector<int> child[maxn]`存放树
A1094
A1106

8.4 二叉查找树BST

题目	解题关键
A1043 Is It a Binary Search Tree	1. 静态写法(变长数组)表示二叉树 2. 根据BST左子树所有结点的数据域 < 根结点的数据域，右子树所有结点的数据域 ≥ 根结点的数据域(由输入样例得出大小关系，镜像则相反)，获取左右子树的边界，判断是否符合先序序列，若符合，则按照左右根的顺序递归，将符合的根结点存入`vector`(获取后序序列) 3. 若vecotr中元素数量 = 输入序列的元素数量(能顺利转换为BST的后序序列)，说明输入序列为先序序列
A1064 Complete Binary Search Tree	1. 输入的元素升序排序，即为二叉树的中序遍历序列。 2. 静态写法(变长数组)按照层序存储完全二叉排序树 3. 对二叉树进行中序遍历，依次填入中序遍历序列的元素即可得到层序存储的二叉树。注意：中序遍历时，二叉树数组根结点的下标：若设为1，则左右孩子结点下标为`root * 2`和`root * 2 + 1`；若设为0，则左右孩子结点下标为`root * 2 + 1`和`root * 2 + 2` 4. 顺序输出二叉树数组元素即为层序遍历序列
A1099 Build A Binary Search Tree	静态写法表示树，解题方法和 A1064 基本一致

8.5 平衡二叉树

题目	解题关键
A1066 Root of AVL Tree	即写出平衡二叉树的代码模板 1. 新建结点的初始高度为1 2. 获取树高时，注意递归到空结点时，返回0 3. 插入结点，递归过程中从系统栈出栈后： 1) 平衡因子为2时，树型可能为LR型或LL型，LR型需要先对当前结点的左子树进行右旋；之后，LR型和LL型都需要对当前结点进行右旋 2) 平衡因子为-2时，树型可能为RL型或RR型，RL型需要先对当前结点的右子树进行左旋；之后，RL型和RR型都需要对当前结点进行左旋 4. 左旋和右旋过程中要及时更新树高

题目

解题关键

A1066 Root of AVL Tree

即写出平衡二叉树的代码模板
1. 新建结点的初始高度为1
2. 获取树高时，注意递归到空结点时，返回0
3. 插入结点，递归过程中从系统栈出栈后：
1) 平衡因子为2时，树型可能为LR型或LL型，LR型需要先对当前结点的左子树进行右旋；之后，LR型和LL型都需要对当前结点进行右旋
2) 平衡因子为-2时，树型可能为RL型或RR型，RL型需要先对当前结点的右子树进行左旋；之后，RL型和RR型都需要对当前结点进行左旋
4. 左旋和右旋过程中要及时更新树高

8.6 并查集

题目	解题关键
A1107 Social Clusters	1. 根据共同(包括潜在的→有共同爱好的人另外的爱好)爱好来确定潜在朋友的集合，利用`hobby[1001]`记录任意一个拥有对应爱好的结点，便于合并操作 2. 遍历各用户，根据根结点统计各集合的人数 3. 将集合按包含人数降序排序，再遍历即可筛选统计出集合个数 4. 路径压缩可选

8.7 堆

题目解题关键

A1098 Insertion or Heap Sort 1. 用于表示树的数组，注意下标从 0或1 开始，孩子结点表示的区别
2. 插入排序：未排序部分和初始序列一定相同
3. 堆排序：后面的元素有序，前面无规律
4. 插入排序更容易判断，将其作为判断排序类型的切入点
4. 插入排序的实际操作可由排序函数sort实现

5. 要用堆排序得到递增序列，则需要建立大根堆
6. 堆排序从后往前找到第一个 $<$ 堆顶的元素，与堆顶元素交换，再对整个堆向下调整

题目	解题关键
A1098 Insertion or Heap Sort	1. 用于表示树的数组，注意下标从 0或1 开始，孩子结点表示的区别 2. 插入排序：未排序部分和初始序列一定相同 3. 堆排序：后面的元素有序，前面无规律 4. 插入排序更容易判断，将其作为判断排序类型的切入点 4. 插入排序的实际操作可由排序函数`sort`实现 5. 要用堆排序得到递增序列，则需要建立大根堆 6. 堆排序从后往前找到第一个 $<$ 堆顶的元素，与堆顶元素交换，再对整个堆向下调整

8.8 哈夫曼树

9. 图算法专题

9.1 图的定义和相关术语

9.2 图的存储

9.3 图的遍历

题目	解题关键
A1013 Battle Over Cities	1. 问题等价于求一个无向图去掉一个结点后，连通分量的数量，这种问题一般有两种方法：图的遍历和并查集 2. `cin`会超时，需要改为`scanf`，邻接矩阵和邻接表都可存储图 3. 每次输入被占领的城市之前，要重置城市的访问状态为未访问 4. 将失去的城市标记为已访问，即可达到失去的效果(没有公路可以到达)
A1021
A1034 Head of a Gang	1. 相同人员之间可能多次通话 2. `map<type1, type2>`自动按`type1`从小到大输出，使用`map<string, int>`建立头目姓名与成员数量的关系，便于输出结果 3. 图中可能有环，为了边权不被漏加，需要先累加边权再递归；同时为了防止边权被重复计算，累加后删除这条边，以免走回头路、重复计算边权
A1076 Forwards on Weibo	1. 转发是粉丝转发博主的信息，因此要根据用户的关注情况建立从博主到粉丝(即反向)的有向图 2. DFS记录访问过的结点数量比较麻烦，BFS比较方便 3. 可能形成环，必须控制每个用户只能转发一次(遍历时只能访问一次)

9.4 最短路径

题目	解题关键
A1003 Emergency
A1018
A1030 Travel Plan
A1072
A1087

9.5 最小生成树

9.6 拓扑排序

9.7 关键路径

10. 动态规划专题

黑盒测试

发表于 2020-02-03 更新于 2025-01-23 分类于算法

对黑盒测试来说，所有输入数据都放在一个文件里。

单点测试

PAT试题基本为单点测试（即一次运行一组数据，一组数据通过测试则获得这组数据的分值）。

多点测试

多点测试要求程序一次运行所有数据，并要求输出结果都正确，只要存在错误，即不得分。
大部分在线判题系统(Online Judge) 都采用了多点测试。
由于要求程序能运行所有数据，因此必须保证程序能反复执行代码的核心部分，这就要用到循环。

输入类型

题目一般有3中输入的格式，需要采用不同输入方式。

while··· EOF型

题目没有给定输入的结束条件，则默认读取到文件末尾。

EOF（End Of File)

可以通过printf("%d", EOF);读取EOF的数值，一般的设备上值是-1。
EOF操作：

windows：Ctrl + Z

unix：Ctrl + D

scanf 若成功读入一个值，返回1；若成功读入2个值，返回2；若读入失败，返回 -1，C/C++中，EOF即为 -1。

正常情况下，控制台中的输入不会失败，只有读取文件时到达文件末尾，导致无法读取时，才会产生读入失败。

//读取数字、字符、字符串
while (scanf("%d", &n) != EOF) {
    ···
}

//读取字符串
while (gets(str) != NULL) {
    ···
}

while··· break型

题目要求，当输入的数据满足某个条件时，停止输入。

while (scanf("%d%d", &a, &b) != EOF) {
    if (a == 0 && b == 0) {
        break;
    }
    printf("%d\n", a + b);
}

//更简洁的写法
while (scanf("%d%d", &a, &b), a || b) {// scanf()恒不为0
    printf("%d\n", a + b);
}

while (T--)型

题目给出测试数据的组数，然后才给出相应数量数组的输入数据。

int T;
scanf("%d", &T);
while (T--) {
    ···
}

输出

正常输出
每组数据输出之后，额外加一个空行
两组输出数据之间有一个空行，最后一组数据后面没有空行

一般在第三种输入类型while (T--)情况下出现，只需通过判断T是否为0选择是否输出额外的换行。

重置变量

在多点测试中，每一次循环都要重置变量和数组，否则在下一组数据来临时，变量和数组不是初始状态，将出错。重置数组一般使用memset函数或fill函数。

C/C++解题干货

发表于 2020-02-01 更新于 2025-01-23 分类于算法

数据类型选择

整型int取值范围：$-2^{31} \sim +(2^{31}-1)$，题目要求绝对值在$10^9$以内或 32位整数，则用int型表示
长整型long long取值范围：$-2^{63} \sim +(2^{63}-1)$，题目要求绝对值在$10^{18}$以内或 64位整数，则用long long型表示

注：如果 long long 型赋 $> 2^{31}-1$的初值，需要在初值后加上LL，否则编译错误。如long long num = 123456789012345LL;
浮点型数据一律用double存储，而不用float(精度低，6~7位)
字符常量使用**ASCII码(范围0~127)**统一编码。
- 0~9 的ASCII码值：48~57
- A~~Z 的ASCII码值：65~~90
- a~~z 的ASCII码值：97~~122 (比大写字母的ASCII码值大32)

强制类型转换

#include <cstdio>

int main() {
    double r = 12.56;
    int a = 3, b = 5;
    printf("%d\n", (int)r); //输出12
    printf("%.1f", (double)a / (double)b);//输出0.6
    return 0;
}

输入输出

C语言	C++	比较
#include <cstdio> scanf函数 printf函数	#include <iostream> using std::cin; using std::cout; cin cout	cin 和 cout 无需指定输入输出格式，但消耗的时间比 scanf 和 printf 多得多。故推荐使用C语言的 scanf 和 printf，只有在十分必要的时候使用 cin 和 cout

输入和输出格式

类型	输入	输出
long long	`scanf("%lld", &n);`	`printf("%lld", n);`
double	`scanf("%lf", &db);`	`printf("%f", db);`
字符串	`scanf("%s", str);` (无需取地址符&)	`printf("%s", str);`
char	`c1 = getchar();` 能读入换行符`\n`	`putchar(c1);`

实用的输出格式

%md

使不足m位的int型变量以m位进行右对齐输出，高位用空格补齐；若变量本身超过m位，则保持原样。
%0md

使不足m位的int型变量以m位进行右对齐输出，高位用0补齐；若变量本身超过m位，则保持原样。
%.mf

让浮点数保留m位小数(四舍六入五成双)输出。如果要四舍五入，需要用到round函数。
四舍六入五成双：
- 5后有数时：舍5入1
- 5后无数时：
  - 5前为奇数，舍5入1
  - 5前为偶数，舍5不进（0是偶数）

C++标准库头文件

C++标准库	包含内容
<iostream>	C++标准输入和输出函数的函数原型
<cstdio>	C风格标准输入和输出函数的函数原型
<iomanip>	格式化数据流的流操纵符的函数原型
<cmath>	数学库函数的函数原型
<ctime>	处理时间和日期的函数的函数原型
<cstdlib>	数与文本的转换、内存分配、随机数及其他各种工具函数的函数原型
<random>	产生非确定性的随机数的功能库
<cctype>	测试字符特定属性(如是否为数字、标点符号等)函数的函数原型转换大小写字母的函数的函数原型
<iterator>	访问 C++标准库容器中数据的类
<algorithm>	操作 C++标准库容器中数据的函数
<string>	C++标准库的 `string`类的定义
<cstring>	C风格字符串处理函数的函数原型

<cmath>

double fabs(double x)

浮点型取绝对值
double floor(double x)和ceil(double x)

向下取整和向上取整
double round(double x)
针对小数点后一位四舍五入

另，不使用函数进行四舍五入的方法：

num = num + 0.5
double pow(double r, double p)

求 r 的 p次方

$10^n$还有另外的表示方法，如
- $10^3$ 可写成 1e3
- $2\times10^6$可写成2e6
- $3\times10^{-6}$可写成3e-6
double sqrt(double x)

求 x 的算术平方根
double log(double x)和double log10(double x)

求 x 以 $e$ 为底的对数和 以10为底的对数

针对任意底数求对数的函数，必须用换底公式，即$\log_ab = \ln b/\ln a$
double exp(double x)

指数函数$e^x$
三角函数

x为弧度
- sin(double x)
- cos(double x)
- tan(double x)

<ctime>

time_t time(time_t *seconds)

返回自格林尼治标准时间的1970年1月1日0时起到现在的秒数。如果seconds不为空，返回值也存储在seconds中。

<cstdlib>

int rand()

rand函数生成 [0, RAND_MAX] 之间的一个整数

直接由rand函数生成的数的范围常常不能满足具体需要，可以通过比例缩放(scaling)方法得到所需的随机数。例如模拟投掷六面骰子，结果可以用rand() % 6 + 1表示。其中数字6称为比例缩放因子。
void srand(unsigned int seed)

rand函数实际上生成的是伪随机数。程序每次执行时产生的序列都是重复的，将其调整为每次执行时都产生不同的随机数序列的过程称为随机化，可以通过srand函数实现。srand函数接收一个unsigned int值，为 rand函数使用的随机数发生器 “播种”，从而产生不同的随机数序列。为了在随机化时不用每次都输入“种子”，可以使用如下语句：

srand(static_cast<unsigned int>(time(NULL) ) );

<cctype>

int isalnum(int c)

字符是否为数字或字母
int isalpha(int c)

字符是否是字母
int isdigit(int c)

字符是否是十进制数字
int islower(int c)

是否是小写字母
int isupper(int c)

是否是大写字母
int tolower(int c)

把大写字母 转换为小写字母

不会改变非字母字符的值
int toupper(int c)

把小写字母 转换为大写字母

不会改变非字母字符的值

<algorithm>

max(x, y)和min(x, y)
abs(x)：x必须是整数，因此更推荐使用<cmath>下的fabs(x)
swap(x, y)

reverse(it1, it2)

可以将数组指针在[it1, it2)之间的元素或容器的迭代器在[it1, it2)之间的元素进行反转。

int a[10] = {10, 11, 12, 13, 14, 15};
reverse(a, a + 4); //将 a[0] ~ a[3]反转
for(int i = 0; i < 6; i++)
    cout << a[i] << " ";
//输出结果：13 12 11 10 14 15

string str = "abcdefghi";
reverse(str.begin() + 2, str.begin() + 6); //对str[2] ~ str[5]反转
for(int i = 0; i < str.size(); i++) {
    cout << str[i];
}
//输出结果：abfedcghi

next_permutation函数

给出一个序列在全排列中的下一个序列。

int a[10] = {1, 2, 3};
do{
    cout << a[0] << a[1] << a[2] << endl;
} while(next_permutation(a, a + 3)); //a[0]~a[2]之间的序列求解下一个序列

fill函数

对数组或容器中某一段区间元素赋相同的值。和<cstring>的memset不同(基本只用于赋0或-1)，可以赋数组类型对应范围中的任意值。
```
int a[5] = {1, 2, 3, 4, 5}
fill(a, a + 5, 233); //a[0] ~ a[4] 均赋值为 233
for(int i = 0; i < 5; i++)
    cout << a[i] << " ";
//输出结果：233 233 233 233 233
```
sort函数

C语言的qsort函数的使用需要运用指针，且写法上没有C++的sort函数简洁。sort函数根据具体情形使用不同的排序方法，效率较高，在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到$O(n^2)$的极端情况。

因此更推荐使用C++的sort函数进行代码编写。

sort(首元素地址, 尾元素地址的下一个地址, 比较函数cmp(非必填))

如果不写比较函数cmp，则默认升序排序。如果想要降序排序，需要编写比较函数cmp：
```
bool cmp(int a, int b) { //返回值为true时，a被排在b之前
    return a > b; //降序
}
```
在STL标准容器中，只有vector、string、deque可以使用sort，因为像set、map这种容器是用红黑树实现的，元素本身有序，故不允许使用sort排序。
lower_bound和upper_bound

lower_bound(first, last, val)用来寻找在数组或容器中的[first, last)范围内第一个值$\geq$val的元素的位置。

upper_bound(first, last, val)用来寻找在数组或容器中的[first, last)范围内第一个值>val的元素的位置。

如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。如果没有找到相应元素，则返回可以插入该元素的位置的指针或迭代器。
max_element和min_element

max_element(first, last)用来寻找在数组或容器中的[first, last)范围内最大元素的位置。

min_element(first, last, val)用来寻找在数组或容器中的[first, last)范围内最小元素的位置。

如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

常用容器

<vector>

向量(“变长数组”的叫法更容易理解)，长度可以根据需要进行变化，比较节省空间。试题中，有时会碰到只用普通数组会超内存的情况，使用vector会让问题的解决便捷许多；另外，vector还可以用来以邻接表的方式存储图。

vector的定义

vector<typename> name

如果typename也是一个STL(Standard Template Library)容器，在C++11之前，定义的时候，在符号>>之间要加上空格。如：vector<vector<int> > name;，可以理解为两个维都可变长的二维数组。

而vector数组的定义，如：vector<typename> Arrayname[arraySize];，一维长度已固定，注意两者的区别。
vector常用函数
1. push_back(typename x)：在 vector 末尾添加一个元素 x
2. pop_back()：删除 vector 的末尾元素
3. begin()：取 vector 的首元素地址
4. end()：取 vector 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）
5. size()：获取 vector 中的元素个数
6. clear()：清空 vector 中所有元素
7. insert(vector<typename>::iterator it, typename x)：向vector的 任意迭代器 it 处 插入一个元素 x
  
  如vi.insert(vi.begin() + 2, -1); //将 -1 插入vi[2]
8. erase()
  - 删除迭代器为 it 处的元素：erase(it);
  - 删除 [firstIt, lastIt) 内所有元素：erase(firstIt, lastIt);

vector容器内元素的访问

通过下标访问

通过迭代器iterator访问

vector<typename>::iterator it;，这样就得到了迭代器it，可以通过***it来访问vector里的元素**。

例如：

#include <iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> vi;
    for(int i = 1; i <= 5; i++)
        vi.push_back(i); //在 vi 的 末尾 添加元素 i
    vector<int>::iterator it = vi.begin(); //vi.begin() 为取 vi 的首元素地址
    for(int i = 0; i < 5; i++)
        cout << *(it + i);
	return 0;
}

可以看出vi[i]和vi.begin() + i等价。在常用的STL容器中，只有vector和string中，才允许使用vi.begin() + 1这种迭代器加上整数的写法。

迭代器还实现了自增和自减的操作，于是还有一种遍历vector中元素的写法：

//vector 的迭代器不支持 it < vi.end() 写法
for(vector<int>::iterator it = vi.begin(); it != vi.end(); it++)
    cout << *it;

<set>

集合，是一个内部自动递增排序且不含重复元素的容器。试题中，可能出现需要去掉重复元素的情况，而且有可能因为这些元素比较大或者类型不是int型而不能直接开散列表，这种情况下就可以用set来保留元素本身而不考虑个数。虽然上述情况也可以通过再开一个数组进行下标和元素对应来解决，但set提供了更为直观的接口，并且可以实现自动排序，可以在做某些题时减少思维量。

set的定义

set<typename> name;

和vector相同，如果typename也是一个STL容器，在C++11之前，定义的时候，在符号>>之间要加上空格。如：set<vector<int> > name;，可以理解为两个维都可变长的二维数组。
set常用函数
1. begin()：取 set 的首元素地址
2. end()：取 set 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）
3. size()：获取 set 中的元素个数
4. clear()：清空 set 中所有元素
5. insert(typename x)：将 x 插入 set 容器中，并自动递增排序和去重，时间复杂度为$O(logN)$
6. find(typename value)：返回 set 中对应值为 value 的迭代器
  
  如：set<int>::iterator it = st.find(2); //在 set 中查找2，返回其迭代器
7. erase()
  - 删除单个元素
    - 删除迭代器为 it 处的元素：erase(it);
      
      可以结合find函数使用，如：st.erase(st.find(100))
    - 删除值为 value 的元素：erase(value);
  - 删除 [firstIt, lastIt) 内所有元素：erase(firstIt, lastIt)
set容器内元素的访问

set只能通过迭代器iterator 访问，因为只有vector和string中，才允许使用vi.begin() + 1这种迭代器加上整数的写法，因此只能按如下方式枚举：
```
#include <iostream>
#include <set>
using namespace std;

int main() {
	set<int> st;
	st.insert(3);
    st.insert(5);
    st.insert(2);
    st.insert(3);
    //set 的迭代器不支持 it < vi.end() 写法
	for(set<int>::iterator it = st.begin(); it != st.end(); it++)
		cout << *it;
	return 0;
}
```
输出为：2 3 5，可以发现，set内的元素自动递增排序，且自动去除了重复元素。
延伸

set中元素是唯一的，如果处理元素不唯一的情况，需要使用multiset。C++11 标准中还增加了unordered_set，以散列代替set内部的红黑树(一种自平衡二叉查找树)实现，使其可以用来去重但不排序的需求，速度比set快得多。

<string>

string中内容的访问
1. 通过下标访问
  
  一般来说，可以直接像字符数组那样去访问string，如果要读入和输出整个字符串，则只能用cin和cout。那么有办法用printf输出string吗？
  
  用string的函数c_str()可以将string类型转换为字符数组进行输出。示例：
```
string str = "abcd";
printf("%s\n", str.c_str());
```
2. 通过迭代器访问
  
  有些函数比如insert()与erase()要求以迭代器为参数进行访问。由于string不像其他STL容器那样需要参数，因此可以直接如下定义：
```
string::iterator it;
for(it = str.begin(); it != str.end(); i++)
    cout << *it;
```
  string和vector一样，允许使用vi.begin() + 1这种迭代器加上整数的写法
string常用函数
1. operator+=
  
  string的加法，可以将两个string直接拼接。
2. compare operator
  
  两个string类型可以直接使用比较符比较大小，比较规则是按字典序。
3. begin()：取 string 的首元素地址
4. end()：取 string 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）
5. size()/length()：返回 string 的长度
6. clear()：清空 string 中的数据
7. insert
  - 在 pos 位置插入字符串：insert(int pos, string str)，原来位置的字符串顺延。
  - 在迭代器it 位置插入字符串：
    
    insert(it, firstIt, lastIt)，firstIt和lastIt为待插字符串的首尾迭代器，用来表示串 [firstIt, lastIt) 将被插在 it 位置上
8. string::npos：是一个常数，本身值为**-1**，但由于是unsigned_int类型，因此实际上可以认为是最大值。用于作为find函数失配时的返回值。
9. find()
  - str.find(string str1)：当 str1 是子串时，返回在 str 中第一次出现的位置；如果不是字串，则返回string::npos
  - str.find(string str1, int pos)：从 pos 位置开始匹配 str1
10. erase()
  - 删除单个元素：erase(it)，目标字符之后的字符字串前移。
  - 删除一个区间内的所有元素，目标区间之后的字符字串前移。
    - erase(firstIt, lastIt)，删除 [firstIt, lastIt) 间的所有字符
    - erase(int pos, int length)，pos 是删除的起始位置
11. substr(int pos, int length)：返回从 pos 位置开始，长度为 length 的字串。
12. replace()
  - str.replace(int pos, int lenth, str1)：把 str 从 pos 位置开始，长度为 length 的字串替换为 str1，替换位置之后的字符串不变。
  - str.replace(it1, it2, str1)：把 str 的迭代器 [it1, it2) 范围的字串替换为 str1，替换位置之后的字符串不变。

<map>

映射，map可以将任何基本类型(包括STL容器) 映射到任何基本类型(包括STL容器)。

来看一个情况：判定给的一些数字在某个文件中是否出现过。如果数字很大，那么就不便建立散列的数组。这时，可以通过map，将这些数字当成字符串，建立string至int的映射。

map的定义

map<typename1, typename2> mp;：< >内第一个是键(key) 的类型，第二个是值(value) 的类型。map 会以键从小到大的顺序自动排序(因为 map 内部是使用红黑树实现的，set也是如此)。map 的一个键只能对应一个值。如果是 int 型映射到 int 型，就相当于普通的 int 型数组。

如果是字符串到整型的映射，必须使用 string 而不能使用 char数组：map<string, int> mp;，因为数组不能作为键值。
map常用函数
1. begin()：取 map 的首元素地址
2. end()：取 map 的 尾后(尾元素地址的下一个)地址（美国人思维比较习惯左闭右开）
3. find(key)：返回键key的对应映射值的迭代器
  
  map<char int>::iterator it = mp.find('b');
4. erase()
  - 删除单个元素：
    - erase(it)：it 为待删除映射的迭代器
    - erase(key)：key 为待删除映射的键
  - 删除一个区间内的所有映射：erase(firstIt, lastIt)
5. size()：获取映射的对数
6. clear()：清空 map 中的所有映射
map容器内元素的访问
1. 通过下标访问
  
  例如定义为map<char, int> mp的map来说，可以直接使用mp['c']的方式来访问对应的整数。
2. 通过迭代器访问
  
  map<typename1, typename2>::iterator it;，因为 map 的每一对映射都有两个 typename，这决定了必须能通过一个 it 来同时访问键和值。事实上，map可以使用it->first来访问键，it->second来访问值。
延伸

map 的键和值是唯一的(一对一)，而如果需要一个键对应多个值(一对多)，就只能用multimap。C++11 标准中还增加了unordered_map，以散列代替 map 内部的红黑树实现，使其可以只处理映射而不按key值排序，速度比 map 快得多。

<queue>

队列，先进先出。

queue的定义

queue<typename> name;
queue常用函数
1. push(x)：将 x 进行入队尾
2. front()、back()：分别获得队首和队尾元素
3. pop()：令队首元素出队
4. empty()：检测 queue 是否为空
5. size()：返回队列内元素个数
queue容器内元素的访问

由于队列是一种先进先出的限制性数据结构，因此只能通过front()来访问队首元素，back()访问队尾元素。
queue的常见用途

当需要实现**广度优先搜索(BFS)**时，可以不用手动实现一个队列，以提高程序的准确性。需要注意的时是，使用front()和pop()函数之前，必须用empty()判断队列是否为空，否则可能因为队空而出现错误。

延伸：STL的容器中还有两种跟队列有关：
- 双端队列deque：首尾皆可插入和删除的队列。
- 优先队列priority_queue：使用堆实现的默认当前队列最大元素置于队首的容器。

`priority_queue`

priority_queue的定义

priority_queue<typename> name;
priority_queue常用函数
1. push(x)：将 x入队，时间复杂度为O(logN)
2. top()：获得队首(即堆顶)元素
3. pop()：令队首元素(即堆顶)元素出队，时间复杂度为O(logN)
4. empty()：检测优先队列是否为空
5. size()：返回优先队列内元素个数
priority_queue容器内元素的访问

只能通过top()函数访问队首元素(优先级最高的元素)。
priority_queue内元素优先级的设置
1. 基本数据类型的优先级设置
  
  下列两种优先队列的定义是等价的(以int型为例)
```
priority_queue<int> q;
priority_queue<int, vector<int>, less<int> > q;
```
  - vector<int>：用来承载底层数据结构—堆的容器
  - less<int>：表示数字大的优先级越大(默认优先级)；greater<int>即为数字小的优先级越大。
  因此，如果想让最小的元素放在队首，需要如下定义：
  
  priority_queue<int, vector<int>, greater<int> > q;
2. 结构体的优先级设置
  
  比如定义水果的结构体：
```
struct fruit {
	string name;
    int price;
}
```
  现在希望按水果价格高的为优先级高，就需要重载小于号<：
  - 方式一：
```
struct fruit {
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2) {
        return f1.price < f2.price; //水果价格高的为优先级高
        // return f1.price > f2.price; //水果价格低的为优先级高
    }
};
```
    其中，friend为友元。bool operator < (fruit f1, fruit f2)对<进行了重载。此时就可以直接定义fruit类型的优先队列，其内部就是以水果价格高的为优先级高：priority_queue<fruit> q;
  - 方式二：将重载的函数写在结构体外
```
struct cmp {
    bool operator () (fruit f1, fruit f2) {
        return f1.price > f2.price;
    }
}

priority_queue<fruit, vector<fruit>, cmp> q;
```
  即便是基本数据类型或者其他STL容器(如 set)，也可以通过同样的方式来定义优先级。如果结构体内的数据较为庞大，建议使用引用来提高效率：
```
friend bool operate < (const fruit &f1, const fruit &f2) {
    reutrn f1.price > f2.price;
}
//或如下
bool operator () (const fruit &f1, const fruit &f2) {
    return f1.price > f2.price;
}
```
priority_queue的常见用途

可以解决一些贪心问题，也可以对 Dijkstra 算法进行优化(因为优先队列的本质是堆)。需要注意的时是，使用top()函数之前，必须用empty()判断队列是否为空，否则可能因为队空而出现错误。

<stack>

栈

stack的定义

stack<typename> name;
stack常用函数
1. push(x)：将 x 压入栈
2. top()：获得栈顶元素
3. pop()：弹出栈顶元素
4. empty()：检测 stack 是否为空
5. size()：返回 stack 内元素的个数
stack容器内元素的访问

只能通过top()函数访问栈顶元素。
stack的常见用途

stack 用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行出错。对有些题目来说，如果用普通的函数进行递归，一旦递归层数过深，则会导致程序运行崩溃。如果用栈来模拟递归算法的实现，则可以避免这一方面的问题。

<utility>

`pair`

当想要将两个元素绑在一起作为一个合成元素，又不想因此定义结构体时，使用pair可以很方便地作为一个替代品，即 pair 可以看作内部有两个元素的结构体。

pair的定义

注意：因为映射map 的内部实现中涉及 pair，因此添加 map头文件时会自动添加 utility头文件，因此，记不住 utility头文件，则可以用 map头文件来代替。

pair 有两个参数：pair<typeName1, typeName2> name;
- 如果想在定义 pair 时进行初始化，只需要跟上一个小括号，填写两个初始化元素即可：
  
  pair <string, int> p("haha", 5);
- 如果想临时构建一个 pair：
  - pair<string, int>("haha", 5)
  - 使用自带的make_pair函数：make_pair("haha", 5)
pair中元素的访问

pair 中只有两个元素，分别是first和second，只需要按正常结构体的方式访问即可。
pair常用函数

比较操作数：

两个 pair 类型数据可以直接使用比较符比较大小，比较规则是先以first的大小作为标准，first相等时去比较second的大小。
pair的常见用途
- 代替二元结构体及其构造函数，节省编码时间
- 作为map的键值对来进行插入：
```
map<string, int> mp;
mp.insert(make_pair("heihei", 5));
mp.insert(pair<string, int>("haha", 10));
```

数组

一维数组初始化

如果数组没有初始化，数组中每个元素为随机数。一维数组的初始化，未被赋初始值的元素将默认初始化为0，因此，如果想要给整个数组初始化为0，只需第一个元素初始化为0即可。int a[10] = {0};(不适用C语言)
二维数组初始化

二维数组初始化需要按第一维的顺序，依次用大括号给出第二维初始化的情况，未被赋初始值的元素将默认初始化为0
```
int a[4][2] = {{3}, {}, {8, 4}}; //第二行使用大括号跳过
/**
数组初始化为：
3 0
0 0
8 4
0 0
*/
```
如果数组大小较大(大概$10^6$级别)，需要定义在主函数外(即全局变量)

否则程序会异常退出（局部变量来自系统栈，允许申请空间较小；全局变量来自静态存储区，允许申请的空间较大）
对数组中每一个元素赋相同的值

需要#include <cstring>

void* memset(数组名, 值, sizeof(数组名));

memset 按字节赋值，即对每个字节赋同样的值，组成int型的4个字节就会被赋成相同的值。故建议只用于赋 0或 -1(0的二进制补码为全0，-1的二进制补码为全1)，不易出错。

如果要对数组赋其他数字(如 1)，则使用 fill函数（执行速度比 memset 慢）。

字符串

字符数组

输入

#include <cstdio>

  - `scanf("%s", str);` 识别**空格或换行**作为输入结束，且**空格或回车符会留在缓冲区**

  - `char c = getchar();` 能够读入**空格和换行符**

  - `gets(char* str);` 识别**换行**作为输入结束，且**回车符会被舍弃，不在缓冲区**

    因此，**scanf一个输入后，如果要使用gets，需要先用 getchar 接收scanf后的空格或换行符**。
  
    另外，**PAT使用C++提交时**，使用`gets()`函数会出现**编译错误**，建议使用C++函数。
  
- ```c++
  #include <iostream>
  using std::cin;

- `cin >>`

- `cin.getline(数组名称, 数组大小)`

  char str[100];
/*
指定最多读入 9 个字符，超出即报错
（实际数组最多能存放99个字符，空字符\0 占用一个字符位）
*/
cin.getline(str, 10);

输出

#include <cstdio>

  - `printf(str);` 
  - `putchar(char c);`
  - `puts(char* str);` 输出数组内容后，**紧跟一个换行**

- ```c++
  #include <iostream>
  using std::cout;

- `cout <<`

字符数组的存放方式

字符数组的末尾都有一个空字符\0(即NULL)，表示存放的字符串的结尾。空字符\0 在gets和scanf输入字符串时，会自动添加在输入的字符串后面，并占用一个字符位。puts和printf就是通过识别\0作为字符串的结尾进行输出。
- 空字符\0占用一个字符位，因此字符数组的长度一定要比实际存储字符串的长度至少多1。
- 如果使用getchar()输入字符串，一定要在每个字符串后加入\0，否则printf和puts输出字符串会因无法识别字符串末尾而输出一大堆乱码。

C++ 的标准库类 string

#include <string>
using std::string;

若引用了<iostream>头文件，创建string对象时，无须引用<string>，因为<iostream>有对std::string的间接引用。但时要对string对象运用相关的函数操作，仍须引用<string>。

输入一整行

getline(cin, str)
比较字符串大小
- str1.compare(str2)
  
  按字典顺序(顺序越靠后，越大)，返回两个字符串大小的比较

<cstring>

strlen(str)

得到字符数组中第一个\0前的字符个数
strcmp(str1, str2)

按字典顺序(顺序越靠后，越大)，返回两个字符串大小的比较结果：
- str1 < str2，返回一个负整数(不同编译器处理不同，不一定是 -1)
- str1 == str2，返回一个0
- str1 > str2，返回一个正整数(不同编译器处理不同，不一定是 +1)
strcpy(str1, str2)

把 str2 复制给 str1，包括结束符\0
strcat(str1, str2)

把 str2 拼接到 str1 后面

字符串与数字的相互转换

C语言

方法一：

#include <cstdlib>

字符串 转为数字

atoi(str)：将字符串转为 int型
atol(str)：将字符串转为 long long型
atof(str)：将字符串转为 double型

方法二： sscanf 与 sprintf

如果想从屏幕输入 int型变量n 并将 n 输出到屏幕：

scanf("%d", &n);
printf("%d", n);
//其实可以表示成如下
scanf(screen, "%d", &n);
printf(screen, "%d", n);

sscanf与sprintf的格式如出一辙，只是把screen换成了字符数组

sscanf(str, "%d", &n); //将字符数组str中的内容以"%d"格式写到n中
sprintf(str, "%d", n); //把n以"%d"的格式写到str数组中

例：

#include <cstdio>

int main() {
    int n;
    double db;
    char str[100] = "2048:3.14,hello", str2[100];
    /*
    从字符串读取格式化输入
    使得 n = 2048, db = 3.14, str2 = hello
    */
    sscanf(str, "%d:%lf,%s", &n, &db, str2);
    n = 12;
    db = 3.1415;
    str2[100] = "good";
    /*
    发送格式化输出到字符串
    使得 str = "12:3.14,good"
    */
    sprintf(str, "%d:%.2f,%s", n, db, str2);
    return 0;
}

C++：

数字 转为字符串

#include <string>
using namespace std;

string str = to_string(num);
len = str.length();

数组作为函数参数

参数中数组的第一维不需要填写长度(如果是二维数组，第二维需要填写长度)
在函数中对数组元素的修改等同于对原数组元素的修改(与普通局部变量不同)

例：

#include <cstdio>

void change(int a[], int b[][5]) {//参数数组 第一维不需要填写长度，第二维需要填写长度
    a[0] = 1;
    a[1] = 3;
    a[2] = 5;
    b[0][0] = 1;
}

int main() {
    int a[3] = {0}; //不适用C语言
    int b[5][5] = {0}; //不适用C语言
    change(a, b);
    for (int i = 0; i < 3; i++) {
        printf("%d\n", a[i]);
    }
    /*
    输出结果为：
    1
    3
    5
    */
    return 0;
}

数组不允许作为返回类型出现，想要返回数组，只能通过参数返回

指针

C语言习惯于把*放在变量名之前：int *p;(声明多个指针时，易统一)
C++习惯把*放在数据类型之后：int* p;

地址赋给p而不是*p

int a;
int* p;
p = &a; //等价于 int* p = &a;

指针的加减法
- 两个指针相减，得到两个地址的距离
- p + 1指 p所指的int型变量的下一个int型变量地址
- 指针支持自增和自减操作

指针变量作为函数参数

例子：交换两个数

只有在获取地址的情况下对元素进行操作，才能真正修改变量

#include <cstdio>

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int a = 1, b = 2;
    int *p1 = &a, *p2 = &b;
    swap(p1, p2);
    return 0;
}

错误写法：

void swap1(int* a, int* b) {
    int* tmp;
    *tmp = *a;
    *a = *b;
    *b = *tmp;   
}
/*
tmp未初始化，存放的地址很大概率指向系统工作区间，不能修改，故后续报错
初始化tmp即可
*/
void swap2(int* a, int* b) {
    int x;
    int* tmp = &x;
    *a = *b;
    *b = *tmp;
}

引用

引用的含义

引用是C++的语法，在编程时极为实用。如果要修改传入函数的参数，且不使用指针，可以通过C++的引用。引用不产生副本，只是给原变量起个别名。

引用的方法：在函数的参数变量名前加个&即可。要将**引用&与取地址运算符&**区分开来，引用并不是取地址的意思。

#include <cstdio>

void change(int &x) {
    x = 1;
}

int main() {
    int x = 10;
    change(x);
    printf("%d\n", x); //输出1
    return 0;
}

指针的引用

例子：交换两个数

//错误写法
void swap(int* a, int* b) {
    int* tmp = a;
    a = b; //交换的地址 是 值传递，不会修改原指针的地址
    b = tmp;
}

通过引用实现交换

#include <cstdio>

void  swap(int* &a, int* &b) { //通过引用实现交换
    int* tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int a = 1, b = 2;
    int *p1 = &a, *p2 = &b;
    swap(p1, p2); //不能写成 swap(&a, &b);
    return 0;
}

引用是产生变量的别名，常量不可使用引用。故上述

swap(p1, p2); //不能写成 swap(&a, &b);

结构体（struct）的使用

访问结构体内的元素

假设p是一个指向结构的指针，可以用**p->结构成员的形式（等价于(*p).结构成员）**，引用相应的结构成员。

申请动态内存空间

如需要定义链表的结点时。

C语言有malloc和free函数用于内存的申请和释放，C++有new和delete运算符用于内存的申请和释放。推荐使用C++进行内存的申请和释放(用法更简洁)。

申请内存空间 — new运算符：

使用new + 类型名即可分配一块该类型的内存空间，返回申请的同变量类型的指针：typename* p = new typename;

示例：
```
int* p = new int;
node* p = new node;
```
通常情况下，内存空间的申请不会失败。失败一般发生在使用new申请了较大的动态数组，如：int* p = new int[1000000];。申请失败会发生异常。
释放内存 — delete运算符：

以需要释放的内存空间的指针变量为参数：delete(p);，执行之后，指针变量p没有消失，只是指向了空地址NULL。

C语言和C++的比较

发表于 2020-02-01 更新于 2025-01-23 分类于算法

输入输出

C语言	C++	比较
scanf函数 printf函数	cin cout	cin 和 cout 无需指定输入输出格式，但消耗的时间比 scanf 和 printf 多得多

头文件

内容	C语言	C++
输入输出库	#include <stdio.h>	#include <cstdio> #include <iostream>
数学函数	#include <math.h>	#include <cmath>
字符串有关函数	#include <string.h>	#include <cstring>

变量类型

布尔型变量

C语言	C++	比较
#include <stdbool.h>	可直接使用	true(存储时为1) false(存储时为0)

字符串

内容	C语言	C++
表示方法	通过字符数组表示	通过 string类表示
字符串长度的表示	#include <string.h> strlen(str)	#include <string> str.length()
字符串拼接	#include <string.h> strcat(str1, str2); //把str2拼接到str1之后	str1 += str2;

排序函数

C语言 — qsort

#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b; //升序
}

qsort(排序数组, 元素数量, 每个元素的大小(可用sizeof获得), 比较函数cmp);

C++ — sort

#include <algorithm>

bool cmp(int a, int b) {
    return a > b; //降序
}

sort(首元素地址, 尾元素地址的下一个地址, 比较函数cmp(非必填));

cmp函数的区别	C语言	C++
返回值类型	int	bool
排序的判断	返回值 > 0, a 将被排在b后面; 返回值 < 0, a 将被排在b前面;	默认升序返回值为true时，a将被排在b前面
比较方式	元素相减不能用$>$、$<$比较符（返回无负值）	$>$、$<$比较符

qsort函数的使用需要运用指针，且写法上没有sort函数简洁。sort函数根据具体情形使用不同的排序方法，效率较高，在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到$O(n^2)$的极端情况。

因此更推荐使用C++的sort函数进行代码编写。

申请动态内存空间

内存泄露是指申请到的内存空间在使用过后没有释放，导致一些程序内存消耗过快，最后无内存可分配的情况。一般考试中，分配的内存空间在程序结束时即被释放，因此即便不是放空间，也不会产生什么影响，并且内存大小一般也足够一道题的使用。但是从编程习惯上，需要养成即时释放空间的习惯。

C语言

<stdlib.h>
- 申请内存空间 — malloc函数：
  
  以需要申请的内存空间为参数，返回指向这块空间的指针，因为返回的指针是void*型，因此需要强制转换为对应类型：typename* p = (typename*)malloc(sizeof(typename));
  
  示例：
```
int* p = (int*)malloc(sizeof(int));
node* p = (node*)malloc(sizeof(node));
```
  通常情况下，内存空间的申请不会失败。失败一般发生在使用malloc申请了较大的动态数组，如：int* p = (int*)malloc(1000000 * sizeof(int));。申请失败会返回空指针NULL。
- 释放内存 — free函数：
  
  以需要释放的内存空间的指针变量为参数：free(p);，执行之后，指针变量p没有消失，只是指向了空地址NULL。
C++
- 申请内存空间 — new运算符：
  
  使用new + 类型名即可分配一块该类型的内存空间，返回申请的同变量类型的指针：typename* p = new typename;
  
  示例：
```
int* p = new int;
node* p = new node;
```
  通常情况下，内存空间的申请不会失败。失败一般发生在使用new申请了较大的动态数组，如：int* p = new int[1000000];。申请失败会发生异常。
- 释放内存 — delete运算符：
  
  以需要释放的内存空间的指针变量为参数：delete(p);，执行之后，指针变量p没有消失，只是指向了空地址NULL。

启动U盘安装Ubuntu(单系统)

发表于 2020-01-17 更新于 2025-01-23 分类于操作系统与软件

准备

由于PE方式只适用于安装windows，因此选择常规的制作启动U盘进行Ubuntu的安装。

操作系统镜像下载（桌面版，文件名后缀 .iso.torrent）

方式一：Ubuntu官网直接下载镜像
方式二：Ubuntu官网下载镜像种子 + 迅雷下载镜像（速度快，推荐）

3G及以上空间的U盘/移动硬盘(用于装载系统镜像)

制作启动U盘

方式一：Windows 10 可以直接打开 iso镜像文件，不用下载任何工具
1. 格式化U盘
2. 双击ISO文件，然后选中打开的所有文件，复制到U盘即可
方式二：下载U盘制作制作工具Rufus(无需安装，可直接运行)
1. 选择设备(需要被制作的U盘/移动硬盘)
  - 只有一个外接设备时会自动读取
  - 如果外接设备是移动硬盘，需要显示高级设备选项 — 显示USB外置硬盘
2. 选择操作系统镜像
3. 分区类型（理论上（联想Y480不知道为什么无法通过UEFI成功安装））
  
  硬盘格式与引导方式、MBR与GPT、UEFI 与LEGACY bios的区别
  - 若选择GPT，之后系统安装时选择UEFI启动（推荐）
  - 若选择MBR，之后系统安装时选择BIOS启动，否则报错（该模式一定能够安装成功）
4. 其余选项默认，点击开始，即可制作启动U盘

安装系统

重启电脑，进入选择启动方式界面（联想笔记本：F12；惠普笔记本：F9）
选择启动U盘
- 想要安装系统的硬盘的格式为GPT，选择UEFI启动，即 EFI USB Device
- 启动U盘分区类型为MBR，选择BIOS启动，即选择对应的U盘
欢迎 — 中文 — 安装Ubuntu
键盘布局 — 汉语
无线 — 不连接
更新和其他软件 — 最小安装

安装类型 — 其他选项 — 进行分区

硬盘大小110GB

UEFI启动：

空间大小	主分区/逻辑分区	类型
200MB	逻辑分区	EFI
8GB （和内存大小一致）	主分区	swap(交换)
40GB	逻辑分区	ext4 挂载至 “/”
剩余空间	逻辑分区	ext4 挂载至 “/home”

BIOS启动：

空间大小	主分区/逻辑分区	类型
200MB	主分区	biosxx
8GB （和内存大小一致）	主分区	swap(交换)
40GB	逻辑分区	ext4 挂载至 “/”
剩余空间	逻辑分区	ext4 挂载至 “/home”

完成安装，根据提示重启即可(可拔去启动U盘/硬盘，避免再次从启动U盘启动)

将从主服务器下载更换为国内镜像站点下载

显示应用程序 - 软件和更新 - Ubuntu软件 - 下载自 - 其他站点 - 选择最佳服务器（自动选择最合适的站点）

更新系统文件

打开终端的快捷键：Ctrl+Alt+T

sudo apt update
sudo apt upgrade

获得各种开发工具

sudo apt-get install build-essential

安装文字编辑器vim和浏览器chromium

sudo apt-get install vim
sudo apt-get install chromium-browser

树视图

sudo apt-get install tree

Cmder

发表于 2019-04-16 更新于 2025-01-23 分类于操作系统与软件

下载

官网下载Cmder（压缩包，解压即用），有两种不同的版本可供选择：

Mini
Full（附带msysgit工具）

可根据设备是否已安装git自行选择

配置

添加系统环境变量

我的电脑 - 右键属性 - 高级系统设置 - 环境变量 - 系统变量，在Path中添加Cmder路径

添加Cmder到右键菜单

Win + R - 输入Cmder，确认，打开Cmder
点击右下方的Create new console
Startup command or {Task} name - {bash::bash}
Run as administrator
Start，即打开一个管理员权限的控制台
输入 Cmder.exe /REGISTER ALL，回车。即可在每个文件夹中鼠标右键右键 - Cmder here，打开Cmder

默认开启设置

Cmder窗口右下角右键Show system menu - General - Choose your startup task or even a shell with arguments: - {bash::bash} - Save settings

关闭Tab不提示

Cmder窗口右下角右键Show system menu - General - Confirm - Close confirmations下的复选框全不勾选 - Save settings

参考：Cmder 使用笔记

Dev-C++

发表于 2019-04-16 更新于 2025-01-23 分类于操作系统与软件

简介

Dev-C++是一个SourceForge的项目，早已停止更新。

缺点：

分辨率低，脱节于屏幕素质的提升，使用感官不佳
中文注释容易乱码，且没有明显的选项用来修改编码格式

下载安装

安装过程中的语言没有中文选项，选择English即可，按照默认选项安装。首次运行时，选择使用软件时的语言为简体中文即可，按照默认选项完成初运行配置。

主题

菜单栏 - 工具 - 编辑器选项 - 语法 - 预设 - Obsidian 黑曜石主题

工具 - 编辑器选项

语法 - 预设 - Obsidian 黑曜石主题

菜单栏 - 工具 - 编辑器选项 - 基本
- 显示编辑器提示
- 显示函数提示
- 高亮显示当前行 - 色彩 - Black

字体

菜单栏 - 工具 - 编辑器选项 - 显示 - 字体 - YaHei Consolas Hybrid

字体下载： Consolas和微软雅黑混合字体

快捷键

功能	快捷键
自动整理代码	Ctrl + Shift + A
代码补全	Ctrl + Space(和输入法切换快捷键冲突)

自定义快捷键：工具 - 快捷键选项 - 菜单项的底部 - Show Code Completion(代码补全)，自定义即可。

添加 C99/C++11 标准

工具 - 编译选项 - 编译时加入以下命令 - -std=c99或-std=C++11

调试

初次启用调试，出现“项目没有调试信息，您想打开项目调试选项并重新生成吗”

菜单栏 - 工具 - 编译选项 - 代码生成/优化 - 连接器 - 产生调试信息 - Yes

调试窗口查看变量的实时数据

开启调试后，有三种方式可以查看变量的实时数据：

左侧调试窗口 - 空白处鼠标右键 - 添加查看
下侧调试窗口 - 添加查看
代码界面鼠标在变量名处停留，会显示当前变量值

参考：

香港两日半 | 不妨长作岭南人

发表于 2019-03-25 更新于 2025-02-13 分类于游记

情之所起

说起香港，脑海中闪过的第一个念头就是《重庆森林》——重庆大厦里奔走的林青霞、趴在半山扶梯上窥看编号633住处的王菲和她哼唱的《California Dreamin’》。终于要去见识这个憧憬太久的目的地了啊。

阅读全文 »

Numpy

快捷键

绝对引用行/列

复制粘贴单元格

筛选的情况下

隐藏的情况下

多个单元格中输入相同的数据

多个单元格中有部分内容需要重复输入

条件格式的设置

批量从身份证号中提取生日

筛选出重复值(唯一值)

去除重复值

长数字输入

冻结窗口

粘贴

粘贴值

选中整行/整列 数据

数据透视表

函数

VLOOKUP函数

INDEX + MATCH 函数

AND 函数 / OR 函数

IF 函数

IF 函数嵌套 示例

COUNTIFS 函数

SUMIFS 函数

LEFT、MID、RIGHT 函数

参考

1. C/C++快速入门

1.1 数组

1.2 指针

1.3 结构体的使用

2. 入门模拟

2.1 简单模拟

2.2 查找元素

2.3 图形输出

2.4 日期处理

2.5 进制转换

2.6 字符串处理

3. 算法初步

3.1 排序

3.1.1 简单选择排序（$O(n^2)$）

3.1.2 直接插入排序（$O(n^2)$）

3.1.3 冒泡排序（$O(n^2)$）

3.1.4 排序题与sort函数的应用

3.2 散列

3.2.1 散列(hash)的定义与整数散列

散列函数

冲突

3.2.2 字符串hash初步

3.2.3 相关习题

3.3 递归

3.3.1 分治

3.3.2 递归

3.4 贪心

3.4.1 简单贪心

3.4.2 区间贪心

3.4.3 相关习题

3.5 二分

3.5.1 二分查找

3.5.2 二分法拓展

3.5.3 快速幂

3.5.4 相关习题

3.6 tow pointers

3.6.1 什么是two pointers

3.6.2 归并排序

3.6.3 快速排序

3.6.4 相关习题

3.7 其他高效技巧与算法

3.7.1 打表

3.7.2 活用递推

3.7.3 随机选择法

3.7.4 相关习题

4. 数学问题

4.1 简单数学

4.2 最大公约数与最小公倍数

4.3 分数的四则运算

4.4 素数

4.5 质因子分解

4.6 大整数运算

选中整行/整列数据

IF 函数嵌套示例

`priority_queue`

`pair`