晴神笔记

读书笔记 / 数据结构
字数统计: 3k   |   阅读时长≈ 13 分钟

C/C++ 算法竞赛常用技巧

常用最大值

1
const int INF = 0x3fffffff

INF + INF 还在 int 范围里

思想

贪心应大胆尝试，无需证明

答案确定的问题可以直接打表，再输出，就 $O(1)$ 了

使用递推降低难度

变量类型

整型

类型 范围 大致范围 scanf() printf()
int $2^{31} - 1$ $10^{9}$ ~ $10^{10}$ %d %d
long long $2^{63} - 1$ $10^{18}$ ~ $10^{19}$ %lld %lld

浮点型

浮点一般用 double

精度 15 ~ 16位

输入: scanf("%lf")

输出: printf("%f")

printf("%.2f")

printf("%02d")

浮点比较精度损失

1
2
const double eps = 1e-8
fab(a-b)<eps //满足条件

字符型

-128 ~ 127

小写字母比大写字母 ASCII 大 32

输入: scanf("%c")

输出: printf("%c")

字符串

C

简单可以用 char[n]

输入: scanf("%s",n) 无 & 符号

C char str[] 末尾需要 ‘\0’ 结束符，scanf("%s"), gets() 都自带

string.h 只能接收字符数组

strlen() 长度

strcmp 字典序，常用

strcpy() 复制

strcat() 串接

sscanf, sprintf

sscanf(str, "%d", &n)

sprintf(str,"%d", n)

C++

复杂直接用 C++ 的 string

数组

$10^6$ 级别以上需要定义在 main() 之外

初始化

1
2
3
4
5
6
7
8
9
10
11
//全赋值 o(n)
int arr[n] = {0};
bool arr[n] = {false};

//memset 函数赋值 o(n)
#include <string.h>
int arr[n];
memset(arr, 0, sizeof(int))
memset(arr, -1, sizeof(int))
    
//fill 函数赋值 o(n^2)

控制台输入，输出

C

scanf()

scanf("%c") 会读" " 和 "\n"

printf () 格式化

%md 右对齐，空格补

%0md 右对齐，0 补

getchar(), putchar()

获取（输出）单个字符，可获得空格，换行

gets(), puts()

读一行，以 “\n” 结尾

常用函数

C

math.h

fabs(double x) 绝对值

floor(double x) 向下取整

ceil(double x) 向上取整

pow(double x, double y) $x^y$

round(double x) 四舍五入，输入也是 double 型，题目中说 round up to xxx 指的就是四舍五入

C++

algorithm

max() min() 浮点，整型均可以

abs(int x) 绝对值

swap() 交换

reverse(it, it2) 范围元素反转

fill(arr, arr + n, x) 范围赋值，注意时间复杂度 $O(n^2)$

sort()

1
2
3
4
5
6
7
8
9
10
11
12
13
//简单cmp
bool cmp(int a, int b){
    return a < b;
}

//结构体排序，可多级排序
bool cmp(Node a, Node b){
    if(a.id!=b.id) return a.id < b.id;//一级排序
    else return a.name < b.name;//二级排序
   
}

sort(begin(), end(),cmp)

lower_bound(first, last, val) 找第一个严格 >= $val$，返回 it；

upper_bound(first, last, val) 找第一个严格 > $val$，返回 it；

排序

STL-sort函数使用

利用此函数可进行多级排序

1
2
3
4
bool cmp(node a, node b){
    return a.xxx < b.xxx;
}
sort(a, a + maxn, cmp)

冒泡排序 bubble sort

比较 $n-1$ 次，两两交换，把最大（小）值像泡泡一下送上去

选择排序 Selection Sort

做 $n-1$ 次，每次从头到尾找最大数，给新序列的第一位，以此填补新序列

插入排序 insert sort

a[0] 有序，a[1] 插入，进而 a[2] 插入前序列，以此类推

1
2
3
4
5
6
7
void insertSort() {
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j > 0; j--) {
            if (a[j] > a[j - 1]) std::swap(a[j], a[j-1]);
        }
    }
}

归并排序 merge sort

快速排序 Quicksort

p139

堆排序

p335

进制处理

p93

散列

散列核心思想是将一定有序的序列降维化

对应高等数学中的1对1映射

使一个整数可以尽可能唯一替代一个元素

整数散列-时间复杂度降维

输入的数下标作为手段

统计该数性质

1
2
int hashtable[maxn]
//此时hashtable[i] 可对应原某有序整数元素

字符串散列-逻辑有序

p109

常用算法思想

递归

递归核心：递归式，边界条件

1
2
3
4
5
6
7
8
void generate(int value){
    if(边界条件){
        return
    }
    
    下一层迭代
    e.g: generate(int value+1)
}

贪心

贪心核心：求局部最优，进而多次迭代获得全局最优

多需要数学证明

贪心是思想不是具体算法

二分

多使用有序序列

每次放弃一半的数据

将 $O(n)$ 降到 $O(log n)$

双指针

核心：多个枚举之间互相牵制

前指针向下遍历的时候，每走一步都会影响后面元素的选择或范围

如: 规定 $a+b=X$， 指针等于 $a$ 开始遍历，后指针就等于 $X-a$

数学问题

最大公约数

1
2
3
4
int gcd(int a, int b){
    if(b==0) return a;
    else return gcd(b, a % b);
}

最小公倍数

1
2
int d = gcd(int a, int b);
int c = a / d * b;

分数处理

1
2
3
4
struct Fraction{
    int up;//分子
    int down;//分母
};

四则运算

加减法通分

乘除法正常

注意

  • 输入为 0，直接判断输出

  • 输入先化简

  • 分母 down 为 1 时，直接输出整数

  • 分子绝对值大于分母，为假分数，输出带分数，

    整数: up / down

    分子: abs(up) % down

    分母: down

素数

p160

质因子分解

p161

大整数处理-小学数学模拟

p170

组合数

p181

C++ STL

begin() 是首地址

end() 是尾地址下一位

即[b, e)

只有 vector 和 string 支持 it+n 的写法

循环遍历结束条件是 it!=v.end()

vector 可变数组

访问

  1. 下标 v[i] == *(v.begin()+i)
  2. 迭代器

常用函数

1
2
3
4
5
6
7
v.push_back(x)
v.pop_back(x)//删除尾元素
v.size()
v.clear()
v.insert(it, x)//注意首元素是迭代器
v.erase(it)
v.erase(it, last)//左闭右开

set 集合

自动有序（递增），无重复元素

红黑树实现

访问

只能迭代器访问

常用函数

1
2
3
4
5
6
7
st.insert(x)//自动处理，不需要迭代器给位置
st.find(x)//返回的是迭代器（指针）
set<typename>::iterator it = st.find(x)
st.erase(x)
st.erase(it, last)//可实现删除 *it 及其后所以元素
st.size()
st.clear()

unorder_set 无序集合

无序，无重复元素

散列实现

常用函数基本同上

string 字符串

#include <string>

输入输出只能用 cin，cout

printf() 输出或用 str.c_str()

访问

str[i] == *(str.begin()+i)

常用函数

1
2
3
4
5
6
7
8
9
10
11
str += str1//拼接
int b = str1 == str2 //字典序比较大小    
length() == size()
insert(pos, x)
insert(it, it2, it3)//串[it2, it3)插在it位置上
erase(first, last)
erase(pos, length)//不包括pos
clear()
substr(pos, len)
find(str2)
replace(pos, len ,str2)

map 映射

按键递增排序

红黑树实现

char [] 是数组，不能做键值

map<typename, typename> mp

访问

  1. 下标（键唯一）

  2. 迭代器

    it->first 键

    it->second 值

常用函数

1
2
3
4
find()
earse()
size()
clear()

unordered_map 无序映射

无序

散列实现

常用函数基本同上

queue 队列

访问

front() back()

常用函数

1
2
3
4
push()
pop()
empty()
size()

priority_queue 优先队列

自动有序

堆实现

priority_queue <int, vector<typename> less<int> > q

priority_queue <int, vector<typename> greater<int> > q

访问

top()

stack 栈

top() 访问

常用函数

1
2
3
4
5
push()
top()
pop()
empty()
size()

pair

#include <utility>

二元结构体

定义可直接初始化

pair <int, int> p(1,1)

访问

p.first

p.second

可直接比较

先比 first

再比 second

DFS

多使用递归处理

核心：面对多种选择永远头铁一个分类的选择，如：岔路口永远左拐

BFS

多使用队列处理

核心：追求广度，面面俱到

小技巧：队列多处理数组下标而非元素

树

二叉树

链表表示

1
2
3
4
5
struct Tree{
    int data;
    Tree* lc;
    Tree* rc;
};

数组表示

数组下标可以提供表示，完全不需要 int id

1
2
3
4
5
struct Tree{
    int data;
    int lc;
    int rc;
}tree[maxn];

完全二叉树

具有唯一性

除了最深一层叶子，其他层全部挂满节点

二叉树 4种遍历

这里的X序遍历，指的是根节点 root 的先后顺序，而且只有 root 能获取内容

中序 + 先序或后序或层序 可唯一确定一棵二叉树

先序遍历 - DFS思想

第一个一定是根

递归实现

1
2
3
4
5
6
7
void preOrder(Tree* root){
    if(root==NULL) return;
    
    get root data;
    preOrder(root->lc);
    preOrder(root->rc);
}

中序遍历 - 分左右

递归实现

满足二叉树分左右的性质，比较重要

1
2
3
4
5
6
7
void inOrder(Tree* root){
    if(root==NULL) return;
    
    inOrder(root->lc);
    get root data;
    inOrder(root->rc);
}

后序遍历 - 最后一个一定是根

递归实现

1
2
3
4
5
6
7
void postOrder(Tree* root){
    if(root==NULL) return;
    
    postOrder(root->lc);
    postOrder(root->rc);
    get root data;
}

层序遍历 - BFS思想

队列实现，可以在 struct 中加 深度depth 或者 层数layer 以应对深度判断

步骤

初始化

入队

读

弹

子树入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void layerOrder(Tree* root){
    queue<Tree*> q;
    root->layer = 1;
    q.push(root);
    
    while(!q.empty()){
        Tree* top = q.front();//获取结点
        q.pop();
        do sth. with top;
        //左子树不空
        if(top->lc!=NULL){
            top->lc->layer =  top->layer + 1;
            q.push(top->lc);
        }
        //右子树不空
        if(top->rc!=NULL){
            top->rc->layer = top->layer + 1;
            q.push(top->rc);
        }
    }
}

确定二叉树

中序提供左右

先，后，层提供根结点

基本步骤

  • 画图，标号下标[1, n]
  • Tree* create(int l, int r, int l, int y)
  • 如果先，中，层长度<=0，直接返回
  • 新建结点 root
  • 在中序中找根结点 root
  • 递归给 root 左右子结点
  • 返回 root

二叉查找树 BST

中序遍历，一定有序

查找 $O(log n)$

删除

p313

平衡二叉树 - AVL

struct 多了一个 height

当 root->left->height 与 root->left->height 差 2 时，做平衡

4种变化

方法论：

  1. 判断哪一种旋转

并查集 - 特化树

如果说树是找儿子的过程

并查集更关心找爹

1
2
3
int f[n]
f[1]=1 //1的爹是1，1就是根结点
f[2]=1 //2的爹是1

合并

  • 判断不在一个集合
  • 让 b 的根结点指向 a

路径压缩

只关心大家的爹

那就每人都指向根结点

查询缩到 $O(1)$

图

比树来说，图更加自由

导致有环的风险，必须加 vis[maxn] 限制仅访问一次

每个结点不能保证一定被别人访问，需要 Trave() 保证每个结点一定能被看到一次

DFS遍历 - 递归实现

邻接矩阵版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int maxv = 1000;
const int INF = 0x3fffffff;

int n, G[maxn][maxn];
bool vis[maxn] = {false}
int depth[maxn];

//这里 depth 没屌用，实际问题可以用 &depth 获取深度，或者直接给 depth[maxn] 送过去
void DFS(int u, int depth){
    //访问该节点
    vis[u]= ture;
    
    尝试访问其他人
    for(int v = 0; v < n; v++){
        //未访问且能访问
        if(vis[v]==false && G[u][v] != INF){
            DFS(v, depth+1);
        }
    }
}

void DFSTrave(){
    for(int v = 0; v < n; v++){
        if(vis[v]==false) DFS(v, 1);
    }
}

BFS遍历 - 队列实现

邻接矩阵版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int maxn = 1000;
const int INF = 0x3fffffff;
int n, G[maxn][maxn];
bool vis[maxn] = {false}

void BFS(int u){
    //初始化
    queue<int> q;
    
    //入
    q.push(u);
    vis[u] = true;
    
    while(!q.empty()){
        //弹
        int u = q.front();
        q.pop();
        
        //找
        for(int v = 0; v < n; v++){
            if(vis[v] == false && G[u][v] != INF){
                q.push[v];
                vis[v] = true;
            }  
        }
    }
}
void BFSTrave(){
    for(int v =0; v < n;v++) {
        if(vis[v]==false) BFS(v);
    }
}

最短路径

Dijkstra算法 - 无负权边 （DFS遍历）

找 a 到 b 的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int maxn = 1000;
const int INF = 0x3fffffff;
int n, G[maxn][maxn];//可处理边权
int weight[maxn];//处理点权
int d[maxn];
int vis[maxn];//检测是否访问，防止环导致死循环
vector<int> pre[maxn];//最短路径递归树
vector<int> best, tmp;

void DFS(int v) {
    //边界条件
    if (v == st) {
        tmp.push_back(v);
        best = v;
        tmp.pop_back();
    }
    //递归遍历
    tmp.push_back(v);
    for (int i = 0; i < pre[v].size(); i++) {
        DFS(pre[v][i]);
    }
    tmp.pop_back();

}

void Dij(int st) {
    fill(d, d + maxn, INF);
    d[st] = 0;
    
    //找N次，保证结点都能尝试判断到
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }

            if (u == -1) return;
            vis[u] = true;

            for (int v = 0; v < n; v++) {
                if (vis[v] == false && G[u][v] != INF) {
                    if (d[u] + G[u][v] < d[v]) {
                        d[v] = d[u] + G[u][v];
                        pre[v].clear();
                        pre[v].push_back(u);
                    }
                    else if (d[u] + G[u][v] == d[v]) {
                        pre[v].push_back(u);
                    }
                }
            }
        }
    }
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2020-2023 Jack Kong
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信