AcWing數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)

1. 單鏈表 head表示頭節(jié)點(diǎn)的下標(biāo),e[i]表示節(jié)點(diǎn)i的值,ne[i]表示節(jié)點(diǎn)i的next指針是多少（節(jié)點(diǎn)i的下一個(gè)位置在什么地方） idx存儲(chǔ)當(dāng)前已經(jīng)用到了哪個(gè)點(diǎn)

int head,e[N], ne[N], idx;

初始化

void init() {head = -1;
    idx = 0;
}

將x插到頭節(jié)點(diǎn)

void add_to_head(int x) {e[idx] = x; // 存新指針的值
    ne[idx] = head; // 插入新指針指向head指向的位置
    head = idx; // head指向插入新指針的位置
    idx ++; // idx指向下一個(gè)位置
}

將x插到下標(biāo)是k的點(diǎn)后面

void add(int k, int x) {e[idx] = x; // 存新指針的值
    ne[idx] = ne[k]; // 新指針指向k點(diǎn)的下一個(gè)位置
    ne[k] = idx; // k點(diǎn)的下一個(gè)位置指向新插入點(diǎn)的位置
    idx ++; // idx指向下一個(gè)位置
}

將頭節(jié)點(diǎn)刪除，需要保證頭節(jié)點(diǎn)存在

void remove () {head = ne[head];
}

將下標(biāo)是k的點(diǎn)后面的點(diǎn)刪掉

void remove(int k) {ne[k] = ne[ne[k]];
}

遍歷鏈表

for(int i = head; i != -1; i = ne[i])

2. 雙鏈表

int e[N], l[N], r[N], idx;

在點(diǎn)a的右邊插入x

void add(int a, int x) {e[idx] = x;
	l[idx] = a, r[idx] = r[a];
	l[r[a]] = idx, r[a] = idx ++;
}

刪除點(diǎn)a

void remove(int a) {l[r[a]] = l[a];
    r[l[a]] = r[a];
}

遍歷鏈表

for (int i = r[0]; i != 1; i = r[i])

3. 棧插入:

stk [++ tt] = x;

彈出：

tt --;

判斷棧是否為空:

if(tt >0) not empty;
else empty;

查詢棧頂:

stk[tt]; // tt存的棧頂元素

4. 隊(duì)列在隊(duì)尾插入元素，在隊(duì)頭彈出元素:

int q[N], hh, tt = -1; // hh表示隊(duì)頭，tt表示隊(duì)尾

插入:

q[++ tt] = x;

彈出:

hh ++;

判斷隊(duì)列是否為空:

if(hh<= tt) not empty 
else empty

取出隊(duì)頭元素:

q[hh];

取出隊(duì)尾元素:

q[tt];

5. 單調(diào)棧

常見模型：找出每個(gè)數(shù)左邊離它最近的比它大/小的數(shù)
int tt = 0;
for (int i = 1; i<= n; i ++ ) {while (tt && check(stk[tt], i)) {tt -- ;
    }
    stk[ ++ tt] = i;
}

6. 單調(diào)隊(duì)列

常見模型：找出滑動(dòng)窗口中的大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i< n; i ++ ) {while (hh<= tt && check_out(q[hh])) {hh ++ ;  // 判斷隊(duì)頭是否滑出窗口
    }
    while (hh<= tt && check(q[tt], i)) {tt -- ;
    }
    q[ ++ tt] = i;
}

7. KMP

// s[]是長文本，p[]是模式串，n是s的長度，m是p的長度
// 求模式串的Next數(shù)組：
for (int i = 2, j = 0; i<= m; i ++ ) {while (j && p[i] != p[j + 1]) {j = ne[j];
    }
    if (p[i] == p[j + 1]) {j ++ ;
    }
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i<= n; i ++ ) {while (j && s[i] != p[j + 1]) {j = ne[j];
    }
    if (s[i] == p[j + 1]) {j ++ ;
    }
    if (j == m) {j = ne[j];
        // 匹配成功后的邏輯
    }
}

8. Trie

int son[N][26], cnt[N], idx;
// 0號(hào)點(diǎn)既是根節(jié)點(diǎn)，又是空節(jié)點(diǎn)
// son[][]存儲(chǔ)樹中每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)
// cnt[]存儲(chǔ)以每個(gè)節(jié)點(diǎn)結(jié)尾的單詞數(shù)量

// 插入一個(gè)字符串
void insert(char *str) {int p = 0;
    for (int i = 0; str[i]; i ++ ) {int u = str[i] - 'a';
        if (!son[p][u]) {son[p][u] = ++ idx;
        }
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查詢字符串出現(xiàn)的次數(shù)
int query(char *str) {int p = 0;
    for (int i = 0; str[i]; i ++ ) {int u = str[i] - 'a';
        if (!son[p][u]) {return 0;
        }
        p = son[p][u];
    }
    return cnt[p];
}

9. 并查集樸素并查集：

int p[N]; //存儲(chǔ)每個(gè)點(diǎn)的祖宗節(jié)點(diǎn)

// 返回x的祖宗節(jié)點(diǎn)
int find(int x) {if (p[x] != x) {p[x] = find(p[x]);
    }
    return p[x];
}

// 初始化，假定節(jié)點(diǎn)編號(hào)是1~n
for (int i = 1; i<= n; i ++ ) {p[i] = i;
}
// 合并a和b所在的兩個(gè)集合：
p[find(a)] = find(b);

維護(hù)size的并查集：

int p[N], size[N];
//p[]存儲(chǔ)每個(gè)點(diǎn)的祖宗節(jié)點(diǎn), size[]只有祖宗節(jié)點(diǎn)的有意義，表示祖宗節(jié)點(diǎn)所在集合中的點(diǎn)的數(shù)量

// 返回x的祖宗節(jié)點(diǎn)
int find(int x) {if (p[x] != x) {p[x] = find(p[x]);
    }
    return p[x];
}

// 初始化，假定節(jié)點(diǎn)編號(hào)是1~n
for (int i = 1; i<= n; i ++ ) {p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的兩個(gè)集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

維護(hù)到祖宗節(jié)點(diǎn)距離的并查集：

int p[N], d[N];
//p[]存儲(chǔ)每個(gè)點(diǎn)的祖宗節(jié)點(diǎn), d[x]存儲(chǔ)x到p[x]的距離

// 返回x的祖宗節(jié)點(diǎn)
int find(int x) {if (p[x] != x) {int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定節(jié)點(diǎn)編號(hào)是1~n
for (int i = 1; i<= n; i ++ ) {p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的兩個(gè)集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根據(jù)具體問題，初始化find(a)的偏移量

[例題]

AcWing 1250. 格子游戲
AcWing 1252. 搭配購買
AcWing 237. 程序自動(dòng)分析

專注于為中小企業(yè)提供成都網(wǎng)站制作、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)馬關(guān)免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上1000+企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。10. 堆

// h[N]存儲(chǔ)堆中的值, h[1]是堆頂，x的左兒子是2x, 右兒子是2x + 1
// ph[k]存儲(chǔ)第k個(gè)插入的點(diǎn)在堆中的位置
// hp[k]存儲(chǔ)堆中下標(biāo)是k的點(diǎn)是第幾個(gè)插入的
int h[N], ph[N], hp[N], size;

// 交換兩個(gè)點(diǎn)，及其映射關(guān)系
void heap_swap(int a, int b) {swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u) {int t = u;
    if (u * 2<= size && h[u * 2]< h[t]) {t = u * 2;
    }
    if (u * 2 + 1<= size && h[u * 2 + 1]< h[t]) {t = u * 2 + 1;
    }
    if (u != t) {heap_swap(u, t);
        down(t);
    }
}

void up(int u) {while (u / 2 && h[u]< h[u / 2]) {heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) {down(i);
}

二叉堆例題

acwing 148 合并果子

11. 哈希表拉鏈法(N = 100003)

int h[N], e[N], ne[N], idx;//槽,鏈表值，下一個(gè)位置，當(dāng)前用到哪個(gè)位置 

void insert(int x) {int k = (x % N + N) % N;//+N%N是為了讓余數(shù)變成正數(shù)
	e[idx] = x;
	ne[idx] = h[k];
	h[k] = idx ++; 
}

bool find(int x) {int k = (x % N + N) % N;
	for(int i = h[k]; i != -1; i = ne[i]) {if(e[i] == x) {	return true;
		}
	}
	return false;		
}

開放尋址法(N=200003)

int h[N]; // 槽

int find(int x) {// 如果x在哈希表存在，返回x的位置，如果不存在，返回x應(yīng)該存貯的位置 
	int k = (x % N + N) % N;
	while(h[k] != null && h[k] != x){// 當(dāng)前位置有人并且不是x 
		k ++;
		if(k == N) {	k = 0;//循環(huán)看第一個(gè)位置 
		}
	} 
	return k;	
}

12. STL

vector變長數(shù)組，利用倍增思想

初始化

vectora;

返回元素個(gè)數(shù)

a.size()

返回a是否為空空true，非空false

a.empty()

清空vector

a.clear()

返回第一個(gè)數(shù)

a.front()

返回最后一個(gè)數(shù)

a.back()

在最后插入一個(gè)數(shù)

a.push_back()

刪除最后一個(gè)數(shù)

a.pop_back()

迭代器

第0個(gè)數(shù)

a.begin()

最后一個(gè)數(shù)的下一個(gè)數(shù)

a.end()

pair存儲(chǔ)二元組

定義

pairt;

元素

p.first
p.second

三種元素

pair>p

string字符串

定義

string s

字符串長度

a.size()

字符串是否為空

a.empty()

清空字符串

a.clear()

從起始位置開始的字符串

a.substr(字串的起始位置，字串的長度)

queuq隊(duì)列

定義

queueq

隊(duì)列長度

q.size()

隊(duì)列是否為空

q.empty()

向隊(duì)尾插入元素

q.push()

返回隊(duì)尾元素

q.back()

彈出對(duì)頭元素

q.pop()

清空隊(duì)列(沒有clear函數(shù))

q = queue();

priority_queue優(yōu)先隊(duì)列，默認(rèn)是大根堆

定義

priority_queueq

插入一個(gè)元素

q.push()

返回堆頂元素

q.top()

彈出堆頂元素

q.pop()

變成小根堆

方法一

priority_queueheap;
heap(-x);

方法二

priority_queue, greater>heap;

stack棧

定義

stackq;

棧長度

q.size()

棧是否為空

q.empty()

向棧頂插入一個(gè)元素

q.push()

返回棧頂元素

q.top()

彈出棧頂元素

q.pop()

deque雙端隊(duì)列

定義

dequeq;

隊(duì)列長度

q.size()

隊(duì)列是否為空

q.empty()

清空隊(duì)列

q.clear()

返回隊(duì)列的第一個(gè)元素

q.front()

返回隊(duì)列的最后一個(gè)元素

q.back()

向隊(duì)列最后插入一個(gè)元素

q.push_back()

彈出隊(duì)列最后一個(gè)元素

q.pop_back()

向隊(duì)首插入一個(gè)元素

q.push_front()

從隊(duì)首彈出元素

q.pop_front()

迭代器

第0個(gè)數(shù)

q.begin()

最后一個(gè)數(shù)的下一個(gè)數(shù)

q.end()

其他STL

binary_search查找某個(gè)元素是否出現(xiàn)

函數(shù)模板：

binary_search(arr[],arr[]+size,x)

參數(shù)說明：

arr[]:數(shù)組首地址
size:數(shù)組元素個(gè)數(shù)
x：需要查找的值

函數(shù)功能：

在數(shù)組中以二分法檢索的方式查找，若在數(shù)組中查找到indx元素則真，若查找不到則返回值是假

lower_bound查找第一個(gè)大于或等于某個(gè)元素的位置

返回查找元素的第一個(gè)可安插位置，也就是“元素值>=查找值”的第一個(gè)元素的位置

函數(shù)模板：

lower_bound(arr[],arr[]+size,x)

參數(shù)說明：

arr[] : 數(shù)組首地址
size : 數(shù)組元素的個(gè)數(shù)
x : 需要查找的值

函數(shù)功能：函數(shù)lower_bound()在first和last的前閉后開區(qū)間進(jìn)行二分查找，返回大于或等于val的第一個(gè)元素的位置，如果所有元素都小于val，則返回last的位置，且last的位置是越界的！

upper_bound查找第一個(gè)大于某個(gè)元素的位置

返回查找元素的最后一個(gè)可安插位置，也就是“元素值>查找值”的第一個(gè)元素的位置

函數(shù)模板 :

upper_bound(arr[] , arr[]+size , x)

參數(shù)說明：

arr[] : 數(shù)組首地址
size : 數(shù)組元素個(gè)數(shù)
x : 需要查找的值

函數(shù)功能 : 函數(shù)upper_bound()返回的在前閉后開區(qū)間查找的關(guān)鍵字的上界，返回大于val的第一個(gè)元素位置 13.樹狀數(shù)組

int a[N];
int tr[N]; // 樹狀數(shù)組
int Greater[N], lower[N]; // Greater[i]表示比i大的數(shù),lower[i]表示比i大的數(shù)

int lowbit(int x) {return x & -x;
}

void add(int x, int c) {// 樹狀數(shù)組的增加函數(shù) 為第x個(gè)數(shù)加上c,并且給它的父親節(jié)點(diǎn)也加上，這里為了表示是否出現(xiàn)，所以加的是1
    for (int i = x; i<= n; i += lowbit(i)) {tr[i] += c;
    }
}

// 求前1~x個(gè)數(shù)的和,tr[x]存儲(chǔ)的是區(qū)間[x ? lowbit(x) + 1,x]出現(xiàn)的數(shù)的次數(shù)，題目說y1到y(tǒng)n是1到n的排列，所以這個(gè)sum是用來求1~x中出現(xiàn)的數(shù)的個(gè)數(shù)
int sum (int x) {// 樹狀數(shù)組的查詢函數(shù)
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {res += tr[i];
    }

    return res;
}

[例題]

AcWing 241. 樓蘭圖騰
AcWing 242. 一個(gè)簡(jiǎn)單的整數(shù)問題
AcWing 243. 一個(gè)簡(jiǎn)單的整數(shù)問題2
AcWing 244. 謎一樣的牛

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：AcWing數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)
文章URL：http://jinyejixie.com/article30/diposo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、外貿(mào)網(wǎng)站建設(shè)、App開發(fā)、小程序開發(fā)、建站公司、自適應(yīng)網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

AcWing數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)