PAT手册
考纲
官方的介绍网站：https://www.patest.cn/introduction
甲级的考察内容
乙级要求：1. 基本的C/C++的代码设计能力，以及相关开发环境的基本调试技巧；
2. 理解并掌握最基本的数据存储结构，即：数组、链表；
3. 理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找等；
4. 能够分析算法的时间复杂度、空间复杂度和算法稳定性；
5. 具备问题抽象和建模的初步能力，并能够用所学方法解决实际问题。
在达到乙级要求的基础上，还要求：1. 具有充分的英文阅读理解能力；
2. 理解并掌握基础数据结构，包括：线性表、树、图；
3. 理解并熟练编程实现经典高级算法，包括哈希映射、并查集、最短路径、拓扑排序、关键路径、贪心、深度优先搜索、广度优先搜索、回溯剪枝等；
4. 具备较强的问题抽象和建模能力，能实现对复杂实际问题的模拟求解。
近几年的考察题型汇总
PAT甲级考试总共有4道题，考察的类型分别如下(参考自浒鱼鱼的文章)：
链表
甲级题目中大部分考察的静态链表，也就是使用数组的index作为指针。
考察题目：
第2道题参考了柳神的做法，用了一个取巧的办法，实际并没有对链表进行实质意义上的排序，而是记录了每个节点的自身的地址，实际上并没有对节点的地址进行调整。
树
对于二叉树的遍历方式有三种分别是：
前序(先序)：根左右（根节点，左孩子，右孩子）
中序：左根右（左孩子，根节点，右孩子），如果是二叉搜索树，这个访问结果序列为有序序列
后序：左右根（左孩子，右孩子，根节点）
不加证明地给出，已知前序中序，或者中序后序可以唯一确定一颗二叉树，给定前序后序则不一定可以唯一确定一颗二叉树。
struct node {
int val;
node *left, *right;
};
// 三个遍历方式的递归实现是很容易记的，按照访问顺序依次写即可
void preOrder(node *root) {
if (root == NULL) return;
printf("%d", root->val);
preOrder(root->left);
preOrder(root->right);
}
void inOrder(node *root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d", root->val);
inOrder(root->right);
}
void postOrder(node *root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
printf("%d", root->val);
}
// 层序遍历
void layerOrder(node *root){
if (root == NULL) return;
queue<node*> q;
q.push(root);
while(!q.empty()) {
node *u = q.front();
q.pop();
printf("%d", u->val);
if (root->left != NULL)
q.push(root->left);
if (root->right != NULL)
q.push(root->right);
}
}
// 怎么求一个树节点的高度(层)？
// 需要增加一个变量layer来记录结点所在的层次
struct node {
int data;
int layer;
node *left;
node *right;
};
void layerOrder(node *root) {
if (root == NULL) return;
queue<node*> q;
root->layer = 1;
q.push(root);
while(!q.empty()) {
node *u = q.front();
q.pop();
if (u->left != NULL) {
u->left->layer = u->layer + 1;
q.push(u->left);
}
if (u->right != NULL) {
u->right->layer = u->layer + 1;
q.push(u->right);
}
}
}利用遍历序列重构二叉树
考察题目：
第3道题比较“含蓄”地给出前序和中序，前序是其PUSH的序列，而中序是POP的序列。
代码实例：
/**
* 依据前序中序构建二叉树
* 前序区间[preL, preR]，中序区间[inL, inR]
* 前序访问顺序：根左右，中序访问顺序：左根右
*/
node *create(int preL, int preR, int inL, int inR) {
if (preL > preR) return NULL;
node *root = new node;
root->data = pre[preL]; // 前序根左右的根节点
int k;
for (k = inL; k <= inR; ++k) { // 找到中序左根右的根位置
if (in[k] == pre[preL])
break;
}
int numLeft = k - inL;
// 依据中序根节点的位置分割序列构建左右子树
root->left = create(preL + 1, preL + numLeft, inL, k - 1);
root->right = create(preL + numLeft + 1, preR, k + 1, inR);
return root;
}
/* 依葫芦画瓢，可以写出给定中序后序构建二叉树的过程 */
node *create(int inL, int inR, int postL, int postR){
if (postL > postR) return NULL;
node *root = new node;
root->val = post[postR];
int k;
for (k = inL; k <= inR; ++k) {
if (in[k] == post[postR])
break;
}
int numLeft = k - inL;
root->left = create(inL, k - 1, postL, postL + numLeft - 1);
root->right = create(k + 1, inR, postL + numLeft, postR - 1);
return root;
}考察题目：
这道题的要求是输出后序访问中的第一个元素，参考柳神的代码中，我们可以得到不需要构建二叉树，直接输出这颗二叉树的后序思路，具体如下：
void postOrder(int preL, int inL, int inR) {
if (inL > inR) return;
int i = inL;
while(in[i] != pre[preL]) i++;
postOrder(preL + 1, inL, i - 1); // 相当于遍历左子树
postOrder(preL + i - inL + 1, i + 1, inR); // 相当于遍历右子树
printf("%d ", in[i]);
}
// 同样的，可以得到给定中序后序输出前序
void preOrder(int postR, int inL, int inR) {
if (inL > inR || postR < 0) return;
printf("%d ", post[postR]);
int i = inL;
while(in[i] != post[postR]) i++;
preOrder(postR - inR + i - 1, inL, i - 1); // inR - i是右子树的结点数量
preOrder(postR - 1, i + 1, inR);
}
平衡二叉树
考察题目：
这道题的本质就是构建一颗平衡二叉树，然后输出它的根节点即可，具体的代码解释，请查看这里。
struct node {
int val;
struct node *left, *right;
};
node *rotateLeft(node *root) {
node *t = root->right;
root->right = t->left;
t->left = root;
return t;
}
node *rotateRight(node *root) {
node *t = root->left;
root->left = t->right;
t->right = root;
return t;
}
node *rotateLeftRight(node *root) {
root->left = rotateLeft(root->left);
return rotateRight(root);
}
node *rotateRightLeft(node *root) {
root->right = rotateRight(root->right);
return rotateLeft(root);
}
int getHeight(node *root) {
if(root == NULL) return 0;
return max(getHeight(root->left), getHeight(root->right)) + 1;
}
node *insert(node *root, int val) {
if (root == NULL) {
root = new node();
root->val = val;
root->left = root->right = NULL;
}
else if (val < root->val){
root->left = insert(root->left, val);
if (getHeight(root->left) - getHeight(root->right) == 2)
root = val < root->left->val ? rotateRight(root):
rotateLeftRight(root);
}
else {
root->right = insert(root->right, val);
if (getHeight(root->left) - getHeight(root->right) == -2)
root = val > root->right->val ? rotateLeft(root):rotateRightLeft(root);
}
return root;
}完全二叉树判断
bool judge(int root) {
if ( == -1) return true;
queue<int> q;
q.push(root);
while (!q.empty()) {
int tmp = q.front();
q.pop();
if (tmp != -1) {
q.push(node[tmp].left);
q.push(node[tmp].right);
}
else {
while (!q.empty()) {
tmp = q.front();
q.pop();
if (tmp != -1)
return false;
}
}
}
return true;
}
bool judge(node *root) {
queue<node*> q;
q.push(root);
while(!q.empty()) {
node *u = q.front();
q.pop();
if (u != NULL) {
q.push(u->left);
q.push(u->right);
}
else {
while(!q.empty()) {
u = q.front();
q.pop();
if (u != NULL)
return false;
}
}
}
return true;
}并查集
考察的题目有：
// 并查集主要就是两个操作，一个查找，一个合并
// 需要的数据结构为数组，存储自己的parent
int fa[maxn] = {0};
// find为algorithm中的函数，所以这里的Find首字母大写
int Find(int i) {
int root = i;
while(root != fa[root])
root = fa[root];
// 路径压缩
int t = i;
int p;
while (t != root) {
p = fa[t];
fa[t] = root;
t = p;
}
return root;
}
// union为关键字，写的时候要注意
void Union(int i, int j) {
int ri = find(i);
int rj = find(j);
if (ri != rj)
fa[ri] = rj;
}寻找公共祖先
首先对于“传统”思路建树，找结点路径，判断公共祖先，这个方法是肯定要会的，但是对于具体的题目，会有一些更为优化的算法。
这两道题中，第一道题采用，构建树，寻找两个节点的路径，在比较路径中的结点得到最近公共祖先会导致后面三个测试点超时，而第二道题使用上面这个思路则不会超时。
针对这两道题的解法都很巧妙，具体参考柳神的博客：1143和1151。
补充得到树的root节点到叶子节点路径的方法：（下面这个查找到指定节点的路径）
bool flag = false;
void preorder(node *root, int x, vector<int> &path, vector<int> &ans) {
if (root == NULL||flag == true) return ;
path.push_back(root->val);
if (root->val == x) {
ans = path;
flag = true;
}
preorder(root->left, x, path, ans);
preorder(root->right, x, path, ans);
path.pop_back();
}中缀&后缀表达式
struct node {
double num;
char op;
bool flag; // true表示操作数， false 表示操作符
};
string str; // 中缀表达式
queue<node> q; // 后缀表达式序列
void infixToPostfix() {
node temp;
stack<node> s; // 操作符栈
map<char, int> op; // 记录操作符的优先级
// 乘除法的优先级大于加减法
op['+'] = op['-'] = 1;
op['*'] = op['/'] = 2;
for (int i = 0; i < str.length(); ) {
// 如果是操作数，直接入队
if (str[i] >= '0' && str[i] <='9') {
temp.flag = true;
temp.num = str[i++] - '0';
while(i < str.length() && str[i] >= '0' && str[i] <= '9') {
temp.num = temp.num * 10 + (str[i] - '0');
i++;
}
q.push(temp);
}
else {
temp.flag = false;
// 操作符的话，需要判断栈顶的操作符优先级
// 如果操作符的优先级小于等于栈顶优先级，则入队出栈
while(!s.empty() && op[str[i]] <= op[s.top().op]) {
q.push(s.top());
s.pop();
}
temp.op = str[i];
s.push(temp);
i++;
}
}
// 栈中可能还有其他操作符
while(!s.empty()) {
q.push(s.top());
s.pop();
}
}
double calPostfix() {
double temp1, temp2;
node cur, temp;
stack<node> s; // 操作数栈
while(!q.empty()) {
cur = q.front();
q.pop();
if (cur.flag == true) s.push(cur); // 如果是操作数，压栈
else {
// 遇到操作符则出栈操作数进行运算
temp2 = s.top().num;
s.pop();
temp1 = s.top().num;
s.pop();
temp.flag = true;
if (cur.op == '+') temp.num = temp1 + temp2;
else if(cur.op == '-') temp.num = temp1 - temp2;
else if (cur.op == '*') temp.num = temp1 * temp2;
else temp.num = temp1 / temp2;
s.push(temp);
}
}
return s.top().num;
}二叉查找树的结点删除
node *findMax(node *root){
while(root->right != NULL) {
root = root->right;
}
return root;
}
node* findMin(node *root) {
while(root->left != NULL) {
root = root->left;
}
return root;
}
void deleteNode(node *&root, int x) {
if (root == NULL) return;
if (root->data == x) {
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
}
else if (root->left != NULL) {
node *pre = findMax(root->left);
root->data = pre->data;
deleteNode(root->left, pre->data);
}
else {
node *next = findMin(root->right);
root->data = next->data;
deleteNode(root->right, next->data);
}
}
else if (root->data > x) {
deleteNode(root->left, x);
}
else {
deleteNode(root->right, x);
}
}哈夫曼树
#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long, vector<long long>, greater<long long> > q;
int main()
{
int n;
long long temp, x, y, ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%lld", &temp);
q.push(temp);
}
while(q.size() > 1) {
x = q.top();
q.pop();
y = q.top();
q.pop();
q.push(x + y);
ans += (x + y);
}
printf("%lld", ans);
}图
dfs+dijkstra 1087.All Roads Lead to Rome (30分)
Dijkstra算法
// 代码来自《算法笔记》和柳神的Github
// 调整了大写字母，在比赛或者考试中尽量选择好打的字母，大写字符输入较慢
// 邻接矩阵版本
// 这里为了注释的方便，一个变量写成一行，运用时直接写到一行即可
// n为顶点数目
int e[maxv][maxv]; // e为记录边的邻接矩阵, maxv为最大顶点数
int dis[maxv]; // 顶点的距离数组
bool visit[maxv]; // 访问数组
const int inf = 99999999;
fill(e[0], e[0] + maxv * maxv, inf);
fill(dis, dis + maxv, inf);
dis[0] = 0;
for (int i = 0; i < n; ++i) {
int u = -1, minn = inf;
// 这里的查找可以用堆排序来实现降低时间复杂度
// 但是比赛过程再去实现一个堆排序不是我们的目的，直接遍历查找就好
for (int j = 0; j < n; ++j) {
if (visit[j] == false && dis[j] < minn) {
u = j;
minn = dis[j];
}
}
if (u == -1) break;
visit[u] = true;
for (int v = 0; v < n; v++) {
if (visit[v] == false && e[u][v] != inf && dis[v] > dis[u] + e[u][v])
dis[v] = dis[u] + e[u][v];
}
}
// 邻接表版本
struct Node {
int v, dis;
};
vector<Node> Adj[maxv];
int n;
int d[maxv];
bool vis[maxv] = {false};
void Dijkstra(int s) {
fill(d, d + maxv, inf);
d[s] = 0;
for (int i = 0; i < n; ++i) {
int u = -1, minn = inf;
for (int j = 0; j < n; ++j) {
if (vis[j] == false && d[j] < minn) {
u = j;
minn = d[j];
}
}
if (u == -1) return;
vis[u] = true;
for (int j = 0; j < Adj[u].size(); j++) {
int v = Adj[u][j].v;
if (vis[v] == false && d[u] + Adj[u][v].dis < d[v]) {
d[v] = Adj[u][v].dis + d[v];
}
}
}
}
Floyd算法
const int inf = 99999999;
const int maxv = 200;
int n, m;
int dis[maxv][maxv];
void Floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dis[i][k] != inf && dis[k][j] != inf && dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}拓扑排序
考察题型：
vector<int> G[maxv];
int n, m, indegree[maxv];
bool topologicalSort() {
int num = 0;
queue<int> q;
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0)
q.push(i);
}
while(!q.empty()) {
int u = q.front();
printf("%d", u);
q.pop();
for (int i = 0; i < G[u].size(); ++i) {
int v = G[u][i];
indegree[v]--;
if (indegree[v] == 0)
q.push(v);
}
num++;
}
if (num == n) return true; // 拓扑排序成功
else return false;
}
算术运算
这两道题的核心是最大公约数的求法，使用辗转相除法
最大公约数
/*
例子：求1071 和462的最大公约数
使用的方法是：辗转相除法
1071 = 2 X 462 + 147 a = 1071, b = 462
462 = 3 X 147 + 21 a = 462 , b = 147
147 = 7 X 21 + 0 a = 147 , b = 21
a = 21 , b = 0
*/
long long gcd (long long a, long long b) {
return (b == 0)? abs(a) : gcd(b, a % b);
}最小公倍数
long long lcm(long long a, long long b) {
long long d = gcd(a, b);
return (a/d)*b;
}素数判断
考察题目：
bool isPrime(int n) {
if (n <= 1) return false;
int sqr = int(sqrt(n * 1.0));
for (int i = 2; i <= sqr; i++) {
if (n % i == 0)
return false;
}
return true;
}
// 素数表, 找到从[2~maxn)中的所有素数
const int maxn = 101;
int prime[maxn];
int pNum = 0; // 素数表的下标
bool p[maxn] = {0}; // 记录[2, maxn)中每个数是否访问过
void Find_Prime() {
for (int i = 2; i < maxn; ++i) {
if (p[i] == false) {
prime[pNum++] = i;
// 存在i的倍数的数值一定不是素数, 2i, 3i ....
for (int j = i +i; j < maxn; j += i) {
p[j] = true;
}
}
}
}闰年判断
bool isLeap(int year) {
// 能被4整除但不能被100整除，或者是能被400整除的
return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}进制转换
// 将sum转换成d进制
int ans[31], num = 0;
do {
ans[num++] = sum % d;
sum /= d;
} while(sum!= 0);
// d进制转换成十进制
int ans, product = 1;
while(x != 0) {
y = y + (x % 10)*product;
x = x/10;
product = product * d;
}分数
struct Fraction {
int up, down;
}
Fraction reduction(Fraction result) {
if (result.down < 0) {
result.down = -result.down;
result.up = -reuslt.up;
}
if (result.up == 0) {
result.down = 1
}
else {
int d = gcd(abs(result.up, result.down));
result.up /= g;
result.down /= g;
}
return result;
}
Fraction add(Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up * f2.down + f1.down * f2.up;
result.down = f1.down * f2.down;
return reduction(result);
}
Fraction minus(Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up * f2.down - f1.down * f2.up;
result.down = f1.down * f2.down;
return reduction(result);
}
Fraction mul(Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up*f2.up;
result.down = f1.down*f2.down;
return reduction(result);
}
Fraction divide(Fraction f1, Fraction f2) {
Fraction result;
result.up = f1.up * f2.down;
result.down = f1.down * f2.up;
return reduction(result);
}
void showFraction(Fraction r) {
r = reduction(r);
if (r.down == 1) printf("%lld", r.up);
else if (abs(r.up) > r.down) {
pritnf("%d %d/%d", r.up / r.down, abs(r.up) % r.down, r.down);
}
else {
pritnf("%d/%d", r.up, r.down);
}
}大数计算
// 摘录自《算法笔记》P171
// 注意！这里的计算仅限于正数，负数的话需要改造
struct bign {
int d[1000];
int len;
bign() {
memset(d, 0, 1000);
len = 0;
}
};
// 逆向赋值的原因是当我们读取一个字符类型的数值比如123，那么最低位是放在字符串最高位的位置
bign change(char str[]) {
bign a;
a.len = strlen(str);
for (int i = 0; i < a.len; ++i) {
a.d[i] = str[a.len - i - 1] - '0'; // 注意这里是逆向赋值
}
return a;
}
// @param return: 0相等， 1大数a大，-1大数b大
int compare(bign a, bign b) {
if (a.len > b.len) return 1;
else if (a.len < b.len) return -1;
else {
for (int i = a.len - 1; i >= 0; --i) {
if (a.d[i] > b.d[i]) return 1;
else if (a.d[i] < b.d[i]) return -1;
}
return 0;
}
}
bign add(bign a, bign b) {
bign c;
int carry = 0;
// 注意！假定a的位数比较长，那么要保证从[b.len, a.len)这个区间中b.d[]中的数值为0
// 否则会出错
for (int i = 0; i < a.len || i < b.len; ++i) {
int temp = a.d[i] + b.d[i] + carry;
c.d[c.len++] = temp % 10;
carry = temp / 10;
}
if (carry != 0)
c.d[c.len++] = carry;
return c;
}
// 这个实现只能计算大数减去小数，也就是a>b，否则会出错
// 如果是 a < b得到的结果是负数，则需要改造这个函数
// 可以改造的思路是判断二者大小，转化成大数减去小数
// 然后需要在bign结构体中加入负数的标志位
bign sub(bign a, bign b) {
bign c;
for (int i = 0; i < a.len || i < b.len; ++i) {
if (a.d[i] < b.d[i]) {
a.d[i + 1]--;
a.d[i] += 10;
}
c.d[c.len++] = a.d[i] - b.d[i];
}
while (c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
c.len--;
}
return c;
}
// 这里稍微有点差别，比如说147 × 35，其中147看成是大数，35看成是int
bign multi(bign a, int b) {
bign c;
int carry = 0;
for (int i = 0; i < a.len; ++i) {
int temp = a.d[i] * b + carry;
c.d[c.len++] = temp % 10;
carry = temp / 10;
}
while(carry != 0) {
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
// 传入的初值要设置为0
bign divide(bign a, int b, int &r) {
bign c;
c.len = a.len;
for (int i = a.len - 1; i >= 0; --i) {
r = r * 10 + a.d[i];
if (r < b) c.d[i] = 0; // 不够除
else {
c.d[i] = r / b;
r = r % b;
}
}
while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
c.len --;
}
return c;
}
哈希表构建-平方探测法
注意的要点是，当H(key)被占用的时候，下一次的探测位置的计算公式为H(key) + k^2，和H(key) - k^2的平方，如果超过了哈希表的长度，那么就需要对表长取模。那么探测的次数要几次呢，如果一直没找到什么时候退出？这里的判断标准是k落在[0, tsize]内，如果k大于ksize时，一定无法找到了。
注意：这里查找的判断的范围是闭区间，[0, tsize]，插入是[0, tsize)
考察题目：
int tsize, n, m, a;
cin >> tsize >> n >> m;
while(!isPrime(tsize)) tsize++;
vector<int> v(tsize);
for (int i = 0; i < n; ++i) {
scanf("%d", &a);
int flag = 0;
for (int j = 0; j < tsize; j++) {// 这里j的取值范围只要[0, tsize)
int pos = (a + j * j ) % tsize;
if (v[pos] == 0) {
v[pos] = a;
flag = 1;
break;
}
}
if (!flag) printf("%d cannot be inserted.\n", a);
}
int ans = 0;
for (int i = 0; i < m; ++i) {
scanf("%d", &a);
// find a
for (int j = 0; j <= tsize; j++) {
ans ++;
int pos = (a + j * j) % tsize;
if (v[pos] == a || v[pos] == 0) break;
}
}排序
关于排序，基本排序算法基本不会让你自己实现，所以对于选择排序，插入排序，快速排序这些，只需了解基本思想，能够知道实现流程即可。可能考察的题型，是链表的排序，就需要用到选择排序，或者插入排序的思想，因为链表不能直接跳转，无法直接使用sort函数。
冒泡排序
void bubbleSort(int arr[], int n) {
bool NoSwap;
for (int i = 0; i < n - 1; ++i) {
NoSwap = true;
for (int j = n - 1; j > i; --j) {
if (arr[j] < arr[j - 1]) {
swap(arr[j], arr[j - 1]);
NoSwap = false;
}
}
if (NoSwap) return;
}
}选择排序
void selecetSort(int arr[], int n) {
for (int i = 0; i < n-1; ++i) {
int k = i;
// 找到序列中未排序的最小元素
for (int j = i+1; j < n; ++j) {
if (arr[j] < arr[i])
k = j;
}
swap(arr[i], arr[k]);
}
}插入排序
void insertSort(int arr[], int n) {
for (int i = 1; i < n; ++i) {
int temp = arr[i], j = i;
// 找到已排序中的插入位置
while(j > 0 && temp < arr[j]) {
arr[j] = arr[j-1];
j--;
}
arr[j] = temp;
}
}快速排序
考察题型：
这道题的其他解法，参考： DedicateToA 的这篇文章。
void quickSort(int arr[], int left, int right) {
if (right <= left) return;
int pivot = selectPivot(left, right);
swap(arr, pivot, right);
pivot = partion(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
int selectPivot(int left, int right) {
return (left + right)/2;
}
int partion(int arr[], int left, int right) {
int l = left;
int r = right;
int temp = arr[right];
while(l != r) {
while(arr[l] <= temp && r > l)
l++;
if (l < r) {
arr[r] = arr[l];
r--;
}
while(arr[r] >= temp && r > l)
r--;
if (l < r) {
arr[l] = arr[r];
l++
}
}
arr[l] = temp;
return l;
}归并排序
const int maxn = 100;
// 归并排序归并的是相邻的两个区间，[L1,R1]和[L2, R2]
void merge(int A[], int L1, int R1, int L2, int R2) {
int i = L1, j = L2; 、、
int temp[maxn], index = 0;
while(i <= R1 && j <= R2) {
if (A[i] <= A[j])
temp[index++] = A[i++];
else
temp[index++] = B[j++];
}
// 移动剩下的区间
while(i <= R1) temp[index++] = A[i++];
while(j <= R2) temp[index++] = B[j++];
for(int i = 0; i < index; i++) {
A[L1+i] = temp[i];
}
}
void mergeSort(int A[], int left, int right) {
if (left < right) {
int mid = (left + right) /2;
mergeSort(A, left, mid);
mergeSort(A, mid+1, right);
merge(A, left, mid, mid + 1, right);
}
}
// 非递归版本
void mergeSort(int A[]) {
// 每组step长度，前step/2和后step/2的元素合并
for (int setp = 2; step / 2 <= n; step *= 2) {
for (int i = 1; i <= n; i+= step) {
int mid = i + step / 2 - 1;
if (mid + 1 < n) {
merget(A, i, mid, mid + 1, min(i + step - 1, n);
}
}
}
}
// 用sort函数替代merge函数，A1089题用到
void mergeSort(int A[]) {
for (int step = 2; step / 2 <= n; step *= 2) {
for (int i = 1; i < n; i+= step)
sort(A + i, A + min(i + step, n + 1));
// 这里可以输出每一趟归并结果
}
}考察的题型有：
这两道题都是给定了两个序列，一个是未排序初始序列，另一个是排序为完成的序列，判断是采用哪种排序方式，然后给出下一轮次的排序结果。
判断是否是插入排序的方法：
/**
a[]为初始序列，b[]为未完成排序序列，n为序列元素个数
例子如下：n = 10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
判断方法是很trivial的，首先插入排序的特定是每次排序一个元素，并且是从右往左开始依次排序
得到的序列结果是已排序部分是有序的，未排序部分是没有进行任何操作的
*/
for (int i = 0; i < n - 1 && b[i] <= b[i+1]; ++i); // 找到已排序和未排序的分界点
for (int j = i + 1; a[j] == b[j] && j < n; ++j); // 未排序部分没有操作，固和原序列一致
if (j == n) {
cout << "Insertion Sort" << endl;
}
// 然后要输出下一轮次的，只需要排序前面的i+1个元素即可，直接调用sort函数
// 注意，sort排序是前闭后开区间，所以是i+2
// 对比排序vector: sort(v.bein(), v.end())，v.end()指向的是容器最后一个元素的下一个元素
sort(a, a + i + 2); 这两道题可以选择取巧的方式，因为只判断两种排序方式，不是其中一种，那就一定是另外一种了，所以只需要判断一种排序方式即可，相比之下，插入排序的判断方式是比较快的，所以只要判断是否是插入排序，不是的话一定就是另外一种排序方式了。
堆排序
const int maxn = 100;
int heap[maxn], n = 10;// 10个元素
// 这一段是核心
void downAdjust(int low, int high) {
int i = low, j = i * 2;
while (j <= high) {
if (j + 1 <= high && heap[j] < heap[j+1]) j = j + 1; // 找到结点i最大的孩子
if (heap[i] >= heap[j]) break; // 已满足大顶堆
swap(heap[i], heap[j]);
i = j, j = i * 2;
}
}
void createHeap() {
for (int i = n / 2; i >= 1; --i) {
downAdjust(i, n);
}
}
void heapSort() {
createHeap();
for (int i = n; i > 1; --i) {
swap(heap[i], heap[1]);
downAdjust(1, i - 1);
}
}深度优先搜索和广度优先搜索
这三道题的类型一致，都是深度优先搜索，只不过根据题目的要求不同判断条件不同，万变不离其宗，可以对比着学习。
背包问题
n件物品，每件物品的重量为w[i]，价值为c[i]，现在要选出若干件物品放入一个容量为V的背包中，使得选入背包的物品重量不超过容量V的前提下，让背包中共的物品价值最大。
// sumW表示的是物品的重量，sumC表示的是物品的价值，index表示的是当前判断的物品编号
void DFS(int index, int sumW, int sumC) {
if (index == n) {
if (sumW <= V && sumC > maxValue) {
maxValue = sumC;
}
return;
}
DFS(index + 1, sumW, sumC); // 不选第index件商品
DFS(index + 1, sumW + w[index], sumC + c[index]); // 选第index件商品
}
// 剪枝版本
void DFS(int index, int sumW, int sumC) {
if (index == n)
return;
DFS(index + 1, sumW, sumC);
if (sumW + w[index] <= V) { // 只有满足了总重量小于背包容量的情况下才能选择该物品
if (sumC + c[index] > ans) {
ans = sumC + c[index];
}
DFS(index + 1, sumW + w[index], sumC + c[index]);
}
}总结：这个问题给了一类常见的DFS问题的解决办法，即给定一个序列，枚举这个序列的所有子序列（可以不连续）。
比如说，从N个整数中选择K个数，使得这个K个数的和为X，如果有多个方案，选择元素平方和最大的一个。
int n, k, x, maxSumSqu = -1, A[maxn];
vector<int> temp, ans;
void DFS(int index, int nowK, int sum, int sumSqu) {
if (nowK == k && sum == x) {
if (sumSqu > maxSumSqu) {
maxSumSqu = sumSqu;
ans = temp;
}
return;
}
if (index == n || nowK > k || sum > x) return;
temp.push_back(A[index]);
DFS(index + 1, nowK + 1, sum + A[index], sumSqu + A[index] * A[index]);
temp.pop_back();
DFS(index + 1, nowK, sum, sumSqu);
}有趣的算法问题
全排列
给定一个数组为1~N，如果输出它的全排列呢？（《算法笔记》P115）
拓展问题：如何输出给定数据的全排列呢？例如输入['a', 'b', 'c']，[11， 12， 13]，我的思路：既然我们可以求出1~N的全排列，把这些全排列作为index下面，然后依据下标index输出输入的['a', 'b', 'c']即可。
const int maxn = 11;
int n, P[maxn], hashTable[maxn] = {false};
void generateP(int index) {
if (index == n + 1) {
for (int i = 0; i <= n; ++i) {
printf("%d", P[i]);
}
printf("\n");
return ;
}
for (int x = 1; x <= n; x++) {
if (hashTable[x] = false) {
P[index] = x;
hashTable[x] = true;
generate(index + 1);
hashTable[x] = false;
}
}
}
// 测试
n = 3;
generateP(1); // 从P[1]开始生成拓展N皇后问题
这道题难度不大，核心就是判断N皇后的位置不在对角线以及同一行即可。
简单概述下N皇后问题，就是将N皇后放在N×N的棋盘上，要求是皇后不能处在同一排，同一列以及对角线上，目标是求出这样的排列方式有哪些。
这个问题为什么和全排列有关系呢，是这样的，每个N皇后的摆放位置可以是1N的位置，那么在棋牌上从左到右来看的话，就是每个皇后的位置都是从1~N中选择一个数值，这样满足了不是同一列，那么为了满足不是同一排，那么每个皇后选择的位置是不同的，这样得到的最终数值就是一个全排列，现在唯一不满的就是对角线了，所以只需要在全排列代码的基础上判断不处于对角线即可。
int count = 0; // 统计有多少个N皇后的排列方案
void generateP(int index) {
if (index == n + 1) {
bool 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 = false;
}
}
}
if (flag) count++;
return;
}
for (int x = 1; x <= n; x++) {
if (hashTable[x] = false) {
P[index] = x;
hashTable[x] = true;
generateP(index + 1);
hashTable[x] = false;
}
}
}日期处理
输出两个日期的差值，两个日期之间相差多少天，思路是对小的日期进行++，直到等于大的日期。
// 这的代码摘录自《算法笔记》，有两个可以改进的
// 1. month数组可以减少为一维，减少空间暂用，对2月进行判断即可
// 2. isLeap调用次数较多，增加标志位进行判断即可
// 这里设置为13的原因是保证下标从1~12月
int month[13][2] = {{0, 0}, {31, 31}, {28, 29}, {30, 30}, {31, 31}, {30, 30}, {31, 31}
, {31, 31}, {30, 30}, {31, 31},{30, 30}, {31, 31}};
bool isLeap(int year) {
return (year % 4 == 0 && year % 100 != 0) || (year % 400) == 0);
}
// 这里假设了time1的时间小于time2
int time1, time2; // 日期格式为20200101的形式，求的是time1和time2相差的天数
int y1, y2, m1, m2, d1, d2;
y1 = time1 / 10000, m1 = time1 % 10000 / 100, di = time1 % 100;
y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
int ans = 1; // 用于记录相差天数的结果
while(y1 < y2 || m1 < m2 || d1 < d2) {
d1 ++; // 天数+1
if (d1 = month[m1][isLeap(y1)] + 1) { // 超过一个月
m1 ++;
d1 = 1;
}
if (m1 == 13) { // 超过一年
y1++;
m1 == 1;
}
ans ++;
}快速幂
typedef long long LL;
LL binaryPow(LL a, LL b, LL m) {
if (b==0) return 1;
if (b % 2 == 1) return a * binaryPow(a, b - 1, m) % m;
else {
LL mul = binaryPow(a, b / 2, m);
return mul * mul %m;
}
}n!有多少个质因子P
int cal(int n, int p) {
int ans = 0;
while(n) {
ans += n / p;
n /= p;
}
return ans;
}
int cal(int n, int p) {
if (n / p) return 0;
return n/p + cal(n / p, p);
}组合数
long long C(long long n, long long m) {
if ( == 0|| m == n) return 1;
return C(n - 1, m) + C(n - 1, m - 1);
}注意！！
使用scanf读入字符时要注意，前面加个空格，原因参考这里
// 输入为：1 2
// 这样才可以正确读取到内容
scanf(" %c %c", &a, &b);2. i++和++i
在代码里面，我们可以看到for循环的第三个表达式有两种写法，i++和++i，那么这两个区别是什么呢，要用哪一个呢？结论是用哪一个都可以，但是效率上有一点点差别，但是随着现代编译器和计算机性能的发展，这个差别几乎可以不考虑。那么差别在哪里呢？
3. map的神奇之处
map可以直接访问未插入的元素，比如下面的代码：
map<int, int> mp;
cout << mp[100] << endl; // 前面并没有执行mp[100] = 1这个操作，这里也可以直接访问mp[100]4. 数值的表示范围
题目中会给出数据的取值范围，我们需要判断相应的变量类型是否可以放得下，所以记住各个变量的表示范围是很有必要的。题目中一般给的是10的几次方的形式，所以大致范围需要重点关注。其他类型属于常规，可直接参考《算法笔记》P7.
5. 输入一行单词的小技巧
// 方法1
char words[90][90];
int num = 0;
while(scanf("%s", words[num]) != EOF) {
num++;
}
// 方法2
char str[90];
char words[90][90];
gets(str);
int len = strlen(str), r = 0; h = 0;
for (int i = 0; i < len; ++i) {
if (str[i] != ' ')
words[r][h++]=str[i];
else {
words[r][h] = '\0';
r++;
h = 0;
}
}6. 什么叫做剪枝？
和这个相关的有几个说法：
暴力法：枚举所有的情况，然后判断每一种情况是否合法，这种做法是非常朴素的，没有优化的算法
回溯法：如果到达递归边界的某层，由于一些事情导致已经不需要往任何一个子问题递归，就可以直接返回上一层，这种做法称之为回溯法
剪枝：在DFS中，通过题目限制条件来减少DFS计算量的方法称之为剪枝。至于为什么叫做剪枝，是因为DFS的遍历就如果如果树的先根遍历，剪枝就是去掉不满足条件的子树，所以称之为剪枝。《算法笔记》P305
7. STL中queue的注意事项
// STL中queue的push操作只是制造了元素的一个副本入队，因此对入队元素的修改不会影响原来的值
// 二者之间没有关联
// 所以如果要对队列的元素进行修改的话，不要入队元素本身，而是要入队它们的编号(数组的话就是下标)
struct node {
int data;
}a[3];
queue<node> q;
for (int i = 0; i < 3; ++i) {
a[i].data = i;
q.push(a[i]);
}
q.front().data = 5000;
printf("%d %d %d\n", a[0].data, a[1].data, a[2].data); // 0 1 2
a[0].data = 1000;
a[1].data = 2000;
a[2].data = 3000;
printf("%d", q.front().data); // 50008. 要点
要注意数据的取值范围！选择正确的数据类型！
注意数据中是否可能出现重复数据，使用大于小于，还是大于等于，小于等于
注意下标是从0开始还是从1开始!
使用printf和scanf进行输出输入，时间和cin和cout差别很大！尽量不适用cin和cout
参考材料
《算法笔记》胡凡.曾磊.著
《算法笔记 - 上机训练实战指南》 胡凡.曾磊.著
浒鱼鱼的CSDN博客
Last updated