晴神笔记

2020-07-27

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() 之外

初始化

//全赋值 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()

//简单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函数使用

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

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] 插入前序列，以此类推

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

常用算法思想

递归

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

void generate(int value){
    if(边界条件){
        return
    }
    
    下一层迭代
    e.g: generate(int value+1)
}

贪心

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

多需要数学证明

贪心是思想不是具体算法

二分

多使用有序序列

每次放弃一半的数据

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

双指针

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

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

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

数学问题

最大公约数

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;

分数处理

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 可变数组

访问

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

常用函数

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

set 集合

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

红黑树实现

访问

只能迭代器访问

常用函数

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)

常用函数

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

访问

下标（键唯一）
迭代器

it->first 键

it->second 值

常用函数

find()
earse()
size()
clear()

unordered_map 无序映射

无序

散列实现

常用函数基本同上

queue 队列

访问

front() back()

常用函数

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() 访问

常用函数

push()
top()
pop()
empty()
size()

pair

#include <utility>

二元结构体

定义可直接初始化

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

访问

p.first

p.second

可直接比较

先比 first

再比 second

DFS

多使用递归处理

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

BFS

多使用队列处理

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

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

树

二叉树

链表表示

struct Tree{
    int data;
    Tree* lc;
    Tree* rc;
};

数组表示

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

struct Tree{
    int data;
    int lc;
    int rc;
}tree[maxn];

完全二叉树

具有唯一性

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

二叉树 4种遍历

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

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

先序遍历 - DFS思想

第一个一定是根

递归实现

void preOrder(Tree* root){
    if(root==NULL) return;
    
    get root data;
    preOrder(root->lc);
    preOrder(root->rc);
}

中序遍历 - 分左右

递归实现

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

void inOrder(Tree* root){
    if(root==NULL) return;
    
    inOrder(root->lc);
    get root data;
    inOrder(root->rc);
}

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

递归实现

void postOrder(Tree* root){
    if(root==NULL) return;
    
    postOrder(root->lc);
    postOrder(root->rc);
    get root data;
}

层序遍历 - BFS思想

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

步骤

初始化

入队

读

弹

子树入队

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
2
3

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

合并

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

路径压缩

只关心大家的爹

那就每人都指向根结点

查询缩到 $O(1)$

图

比树来说，图更加自由

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

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

DFS遍历 - 递归实现

邻接矩阵版

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遍历 - 队列实现

邻接矩阵版

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 的最短路径

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);
                    }
                }
            }
        }
    }
}

栈

2020-06-26

读书笔记 / 数据结构 / 基础类型

栈

堆栈 - 顺序数组实现

堆栈本质上是特殊的线性表，只是对于元素的存取做出了一定的规定

起床时最先穿的内裤，睡觉时确实最后一层才能脱

可见生活中也有很多堆栈性质的例子

定义

struct _node {
    int *data;
    int top;
    int maxSize;
} Node;
typedef struct _node *Stack;

初始化

top = -1 时栈空

top = maxSize - 1 时栈满

Stack createStack(int maxSize) {
    Stack s = (Stack) malloc(sizeof(Node));
    s->data = (int *) malloc(maxSize * sizeof(int));
    s->top = -1;
    s->maxSize = maxSize;
    return s;

}

栈满判断

1
2
3

bool isFull(Stack s) {
    return (s->top == s->maxSize - 1);
}

入栈

bool push(Stack s, int value) {
    if (isFull(s)) {
        printf("栈满");
        return false;
    }
    else {
        s->top++;
        s->data[s->top] = value;
        return true;
    }
}

栈空

bool isEmpty(Stack s) {
    return (s->top == -1);

}

出栈

int pop(Stack s) {
    if (isEmpty(s)) {
        printf("栈空");
        return ERROR;
    }
    else {
        return (s->data[s->top--]);
    }
}

注意事项

取首元素与出栈：一定是先出后取

PAT-A-1001

2020-06-13

PAT / PAT A

PAT-A-1001

所有甲级题全解

原题链接

生僻词汇：

Comma 逗号

题意

给定 $a$，$b$，未超出 int 范围

计算出和，按要求格式化输出

知识点

整数范围的把握

整数转字符串

字符串格式化处理

思路

用 C++ string 更方便

代码

#include <iostream>

using namespace std;
int a, b, sum;

int main() {
    //输入
    cin >> a >> b;
    sum = a + b;
    string str = to_string(sum);

    //如果 sum 是负数，位数应减去1
    int comma;
    if (sum < 0) comma = (int) (str.length() - 2) / 3;
    else comma = (int) (str.length() - 1) / 3;

    //从尾部向前 3*i 位加逗号
    for (int i = comma; i >= 1; i--) {
        str.insert(str.length() - 3 * i, ",");
    }

    //输出
    cout << str << endl;
    return 0;
}

数据结构-线性表

2020-06-13

读书笔记 / 数据结构 / 线性表

线性表

同一类型元素

有序

线性结构

线性表顺序存储

定义

typedef struct _node *PtrToSqList;
struct _node {
    int data[1024];
    int last;
};
typedef PtrToSqList List;

用数组储存线性表

1024 可替换为任何合适的数

last 本质上是指向表尾的指针，因为数组角标的特殊性，直接使用表尾角标即可

C语言值传递，传递大数组显然很蠢比，不如传数组指针

初始化

List makeEmpty() {
    List l = (List) malloc(sizeof(Node));
    l->last = -1;
}

申请内存，不然空指针

last = -1 表示表空

插入

bool insert(List l, int position, int value) {
    int index = position - 1;
    if (!(index >= 0 && index <= l->last + 1)) {
        printf("位置非法");
        return false;
    }
    else if (l->last == 1023) {
        printf("表满");
        return false;
    }
    else {
        for (int i = l->last; i >= index; i--) {
            l->data[i + 1] = l->data[i];
        }
        l->data[index] = value;
        l->last++;
        return true;
    }
}

凡是数组相关的，形参有位置一定要判断是否合法

注意角标

删除

bool delete(List l, int position) {
    int index = position - 1;
    if (!(index >= 0 && index <= l->last)) {
        printf("位置非法");
        return false;
    }
    else if (l->last == -1) {
        printf("表空");
        return false;
    }
    else {
        for (int i = index; i <= l->last; i++) {
            l->data[i] = l->data[i + 1];
        }
        l->last--;
        return true;
    }

}

链表-线性表链式存储

单链表一定要有一个空的头结点，主要目的是保持引用传递时，头结点指针不会随着第一个结点的变化而变化，进而引起不必要的维护漏洞

定义

struct _node {
    int data;
    struct _node *next;
} Node;
typedef struct _node *List;
typedef struct _node *PtrToList;

List 虽然跟 PtrToList 定义一致，但是 List 侧重于其指向的内容，PtrToList 侧重于自己是一个指针的身份事实

初始化

List makeEmpty() {
    List head = (List) malloc(sizeof(Node));
    head->next = NULL;
    List l = head;
    return l;
}

申请内存，不然空指针

注意 l 将永远指向 head 结点，但仅限单链表

表长度

int length(List l) {
    PtrToList p = l;
    int cnt = -1;
    while (p) {
        p = p->next;
        cnt++;
    }
    return cnt;

}

逻辑相连，动态的代价就是长度不确定性

插入

bool insert(List l, int position, int value) {
    int lent = length(l);
    PtrToList pre = l;
    List tmp = (List) malloc(sizeof(Node));
    tmp->data = value;

    if (!(position >= 1 && position <= lent + 1)) {
        printf("位置非法");
        return false;
    }
    else {
        for (int i = 1; i <= position - 1; i++) {
            pre = pre->next;
        }
        tmp->next = pre->next;
        pre->next = tmp;
        return true;
    }


}

索引

按位索引

int findByPosition(List l, int position) {
    int lent = length(l);
    PtrToList p = l;
    if (!(position >= 1 && position <= lent)) {
        printf("位置非法");
        return false;

    }
    else {
        for (int i = 1; i <= position; i++) {
            p = p->next;
        }
        return p->data;
    }
}

检测位置合法性

按值索引

int findByValue(List l, int value) {
    int lent = length(l);
    PtrToList p = l;

    for (int i = 1; i <= lent; i++) {
        p = p->next;
        if (p->data == value) {
            return i;
        }
    }
    return false;

}

没找到应该返回 false

删除

bool delete(List l, int position) {
    int lent = length(l);
    PtrToList pre = l;
    if (!(position >= 1 && position <= lent)) {
        printf("位置非法");
        return false;
    }
    else {
        for (int i = 1; i <= position - 1; i++) {
            pre = pre->next;
        }
        PtrToList cur = pre->next;
        pre->next = cur->next;
        free(cur);
        return true;
    }

}

设计模式读书笔记

2020-05-18

读书笔记 / 设计模式

设计模式

我一直持有一个观点：代码首先是给人看的，其次才是给机器读的，不然搞什么面向对象又是面向过程，一个文件塞满理论上也能满足计算机的要求，但是想让人看懂，易于操控，就需要理解语言创造者的苦心。而进阶的编程爱好者，对于设计模式的理解便显得弥足珍贵了，本文为多语言各种设计模式的横纵向比较分析与记录。

创造者模式

与其说是创造对象，不如说是产品说明，此类模式关心一个实例创造前的全部内容，如同造汽车前，设计和制造流水线工程。

这些设计模式提供了一种在创建对象的同时隐藏创建逻辑的方式，而不是使用 new 运算符直接实例化对象。这使得程序在判断针对某个给定实例需要创建哪些对象时更加灵活

工厂模式 Factory Pattern

不涉及创造实例

大部分程序一直在研究的就是解耦，因为高度耦合会带来难以维护，变量联系过于紧密等问题，我们希望模块化，而不是牵一发而动全身，因此创造对象时一大堆初始化工作不应该放在业务代码里，应该有一个工厂一样的接口代为保存，这样核心业务变化的时候，不用在所有创造实例的业务里修改，只需要修改工厂即可。

抽象工厂模式 Abstract Factory Pattern

工厂的工厂

当业务复杂化后，需要对工厂本身抽象，进而满足工厂实例跟着业务实例的变化，如流水线核心不变，生产轿车还是跑车这种小细节变化，只需要实例化抽象工厂就能满足要求。

单例模式 Singleton Pattern

有且只有自己存在

单例的核心思想是全局唯一性，本类实例化自己，且唯一，外部只能销毁和创建调用，不能去关心内部逻辑。

适用于全局唯一的实例，如单线程。

建造者模式 Builder Pattern

核心是造变形金刚

变形金刚由多个部件组成，部件本身复杂多变，但是合体变形金刚的算法或者结构却是相对简单的，这时考虑使用建造者模式。

比起工厂模式更关心部件的组装顺序。

原型模式 Prototype Pattern

克隆人

当新建对象代价很大的时候，对象需要复用时使用。

如一个对象需要在一个高代价的数据库操作之后被创建。可以缓存该对象，在下一个请求时返回它的克隆，在需要的时候更新数据库，以此来减少数据库调用。

对象池模式 Pool

水库存水

老是用水龙头取水，水龙头容易坏，还容易无法满足需求，先搞个水库，把常用对象扔进去，异步的存取使用，避免同步操作带来的消耗。

如：线程池、数据库连接池、任务队列池、图片资源对象池。

举例：laravel 的邮件发送是同步的，修改成一个队列池，每个新请求会被放到池子里，服务器可以从容不迫的 FIFO 处理任务。

多例模式 Multiton

包含多个实例的单例模式

如多个数据库链接。

静态工厂模式 Static Factory

针对静态资源的工厂模式

结构型模式

适配器模式 Adapter Pattern

电力中的转换器也是相同思路，220v 换成 120v 需要一个接口处理，就是适配器。

当年写 Android 的时候，适配器是必须掌握的知识。

缺点就是反常规，看不懂会奇怪，明明 A 类的资源，怎么扔 B 类还能用？

桥接模式 bridge Pattern

桥接的核心思路是将抽象与行为解耦，从继承关系弱化为关联模式

如一个实例面临多个并列行为的关系时，可以用桥接，如设计一杯饮料，杯子大小，饮料内容，配料均有多个选择，使用桥接很适合。

共享模式 Flyweight

核心是高度重复资源的可重复利用性，多跟工厂模式共用，当遇到请求时，首先检索共享池里是否有合适对象，否则创造并返回。

面临高度重复的请求时，最大程度减少资源开销。

装饰模式 Decorator

动态基于对象新的功能，像打补丁一样，不在意被装饰对象本身细节。

相当于万智牌的合变放在下面，下面的生物只给了异能，别的啥事没干。

组合模式 Composite

本质上是树形结构的封装利用，利用树形结构的访问速度优势，迭代得获取各组件。

非叶节点也可以看成另一个组构体。

代理模式 Proxy Pattern

核心在于请求本身涉及安全性或者大花销等问题，需要代理看看给不给权限，不然对象造完了再研究给不给权限就没什么意义了。

相当于请个管家管一下。

外观模式 Facade

比起小管家，Facade 是总管，对一个系统的访问做整理跟统筹，最大程度降耦，保证子系统自由性。

行为类模式

迭代模式 Iterator

迭代器的抽象，没啥好说的，核心在于不暴露内部结构的遍历。

模板模式 Template

定义操作骨架，通过继承丰富内容或者实现。

抽象类常用思想，定义却不完化，给予后人补充说明。

责任链 Chain of Responsibility

请求来源高度不确定性，使用 cor 可以使链上任意一个类的负担不至于过重，统一一个 handler 分配工作。

备忘模式 Memento

可能二次需要的内容做保存。

如 laravel 中的 old()方法。

中介者 Mediator

各个对象之间的交互操作非常多;每个对象的行为操作都依赖彼此对方,修改一个对象的行为,同时会涉及到修改很多其他对象的行为。

如 laravel 中的 Controller

解释器 Interpreter

很少会用到，关注于非可识别语言的解释，如正则，表达式等。

策略模式 Strategy

也叫算法簇模式，针对不同需求，有策略的分派不同算法解决问题。

状态模式 State

就是状态机。

观察者 Observer

常驻内存检测变化，一旦变化就触发。

访问者模式 visitor

作用于某个对象群中各个对象的操作. 它可以使你在不改变这些对象本身的情况下,定义作用于这些对象的新操作.

命令模式 Command

Laravel 中的 Artisan 是很典型的命令模式，请求对象化。

且听风吟

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

常用最大值

思想

变量类型

整型

浮点型

浮点比较精度损失

字符型

字符串

C

string.h 只能接收字符数组

sscanf, sprintf

C++

数组

初始化

控制台输入，输出

C

scanf()

printf () 格式化

getchar(), putchar()

gets(), puts()

常用函数

C

math.h

C++

algorithm

sort()

排序

STL-sort函数使用

冒泡排序 bubble sort

选择排序 Selection Sort

插入排序 insert sort

归并排序 merge sort

快速排序 Quicksort

堆排序

进制处理

散列

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

字符串散列-逻辑有序

常用算法思想

递归

贪心

二分

双指针

数学问题

最大公约数

最小公倍数

分数处理

四则运算

注意

素数

质因子分解

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

组合数

C++ STL

vector 可变数组

访问

常用函数

set 集合

访问

常用函数

unorder_set 无序集合

string 字符串

访问

常用函数

map 映射

访问

常用函数

unordered_map 无序映射

queue 队列

访问

常用函数

priority_queue 优先队列

访问

stack 栈

常用函数

pair

定义可直接初始化

访问

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