目录

Acwing算法基础课第二讲总结(正在写)

本讲主要内容
单链表,双链表,栈,队列,单调栈,单调队列,KMP,Tire,并查集,堆,哈希表。

单链表

Acwing-826 单链表

原题链接

思路
模板题。代码中head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
参考代码
#include <iostream> 
#include <algorithm>
using namespace std;

const int maxn = 1e5+10;
int head, e[maxn], ne[maxn], idx;	//idx充当题目中k的作用,但是注意是idx从0开始,而k从1开始,所以对应的用到k的地方需要减一

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

void add_to_head(int x)
{
	e[idx] = x;
	ne[idx] = head;
	head = idx++;
}

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

//插入到第k个数后 
void add_to_back(int k, int x)
{
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx++;
}

int main(void)
{
	int m;
	cin >> m;
	init();
	
	while(m--)
	{
		char op;
		cin >> op;
		
		if(op == 'H') 
		{
			int x;
			cin >> x;
			add_to_head(x);
		}
		
		else if(op == 'D')
		{
			int k;
			cin >> k;
			//k为0时删除头结点
			if(k == 0) head = ne[head];
			else remove(k - 1);
		}
		
		else if(op == 'I')
		{
			int k, x;
			cin >> k >> x;
			add_to_back(k-1, x);
		}
	}
	
	for(int i = head; i != -1; i = ne[i] ) cout << e[i] << ' ';
	cout << endl;
	return 0;
}

双链表

Acwing-827 双链表

原题链接

思路
模板题。代码中e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
参考代码
#include <iostream>
#include <string>
using namespace std;

const int maxn = 1e5+10;
int e[maxn], l[maxn], r[maxn], idx;

void init(void)
{
	//0是左端点,1是右端点
    r[0] = 1;
	l[1] = 0;
	idx = 2;
}

// 在节点k的右边插入一个数x
void insert(int k, int x)
{
	e[idx] = x;
	l[idx] = k;
	r[idx] = r[k];
	l[r[k]] = idx;
	r[k] = idx++; 
}

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

int main(void)
{
	int m;
	cin >> m;
	
	init();
	while(m--)
	{
		//这里注意定义为string,因为操作序列有字符串 
		string op;
		cin >> op;
		
		int k, x;
		if(op == "L")
		{
			cin >> x;
			insert(0, x);	//最左端即为左端点后面插入 
		}
		else if(op == "R")
		{
			cin >> x;
			insert(l[1], x);	//最右端插入即为右端点前插入 
		}
		else if(op == "D")
		{
			cin >> k;
			remove(k+1);	//类比单链表,这里由于idx充当k的作用,且从2开始,而k从1开始,所以为idx比k多1 
		}
		else if(op == "IL")
		{
			cin >> k >> x;
			insert(l[k+1], x);	 
		}
		else 
		{
			cin >> k >> x;
			insert(k+1, x);
		}
	}
	
	for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
	cout << endl;
	
	return 0;
}

Acwing-828 模拟栈

原题链接

思路
模板题。
参考代码
#include <iostream>
#include <string>
using namespace std;

const int maxn = 1e5+10;
int stk[maxn], tt;	//tt表示栈顶。这里的栈的下标是从1开始的,也可以从0开始

int main(void)
{
    int m;
    cin >> m;

    string op;
    while(m--)
    {
        cin >> op;
        if(op == "push")    // 向栈顶插入一个数
        {
            int x;
            cin >> x;
            stk[++tt] = x;
        }
        else if(op == "pop")    // 从栈顶弹出一个数
        {
            tt--;
        }
        else if(op == "empty")  // 判断栈是否为空
        {
            if(tt > 0) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else    // 栈顶的值
        {
            cout << stk[tt] << endl;
        }
    }

    return 0;
}

队列

Acwing-829 模拟队列

原题链接

思路
模板题。
参考代码

普通队列

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

// hh 表示队头,tt表示队尾
// 这里的队列起始坐标是从0开始的
const int maxn = 1e5+10;
int q[maxn], hh, tt = -1;

int main(void)
{
    int m;
    cin >> m;

    string op;
    while(m--)
    {
        cin >> op;
        if(op == "push")    // 向队尾插入一个数
        {
            int x;
            cin >> x;
            q[++tt] = x;
        }
        else if(op == "pop")    // 从队头弹出一个数
        {
            hh++;
        }
        else if(op == "empty")  // 判断队列是否为空
        {
            if(hh <= tt) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else    // 队头的值
        {
            cout << q[hh] << endl;
        }
    }

    return 0;
}

循环队列

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

const int maxn = 1e5+10;
int q[maxn], hh, tt;    //hh表示队头,tt表示队尾的后一个位置

int main(void)
{
    int m;
    cin >> m;

    string op;
    while(m--)
    {
        cin >> op;
        if(op == "push")    // 向队尾插入一个数
        {
            int x;
            cin >> x;
            q[tt++] = x;    //注意这里的tt表示的是队尾的后一个位置
            if(tt == maxn) tt = 0;
        }
        else if(op == "pop")    // 从队头弹出一个数
        {
            hh++;
            if(hh == maxn) hh = 0;
        }
        else if(op == "empty")  // 判断队列是否为空
        {
            if(hh != tt) cout << "NO" << endl;
            else cout << "YES" << endl;
        }
        else    // 队头的值
        {
            cout << q[hh] << endl;
        }
    }

    return 0;
}

单调栈

Acwing-830 单调栈

原题链接

思路
模板题。
参考代码
#include <iostream>
using namespace std;

const int maxn = 1e5+10;
int stk[maxn], tt;

int main(void)
{
	int n;
	cin >> n;

	int x;
	while(n--)
	{
		cin >> x;
		
		//遍历单调栈寻找满足条件的数字,并且删除掉逆序对,维护栈的单调性(升序)
        //注意while中的>=不能写为>,题目中描述的是“找到比它小的数”,并不包含小于等于的情况
		while(tt && stk[tt] >= x) tt--;

		//若存在最优解则输出,否则输出-1
		if(tt) cout << stk[tt] << ' ';
		else cout << "-1" << ' ';

		//让待查找序列中的数字入栈
		stk[++tt] = x;
	}

	return 0;
}

单调队列

Acwing-154 滑动窗口

原题链接

思路
模板题。滑动窗口是用单调队列来维护下标(当然直接在队列里面存值也可以,但不便于理解)。因为涉及到窗口的移动,下标可以唯一对应到数组元素值并保使得维护窗口长度不超过k。而原序列中的数是储存在另一个数组a中。
参考代码
#include <iostream>
using namespace std;

const int maxn = 1e6+10;
int a[maxn], q[maxn];

int main(void)
{
	//cin和cout关闭同步,使得在输入输出较多的情况下能有更快的速度
	//这里一定要两句都写,只写第二句速度提升效果并不显著
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	//这里也可以把输入写到下面的循环里
	for(int i = 0; i < n; i++) cin >> a[i];
	
	int hh = 0, tt = -1;
	for(int i = 0; i < n; i++)
	{
		//判断队头是否滑出窗口
		while(hh <= tt && i-k+1 > q[hh]) hh++;
		
		//对于这道题,这里的等号可有可无,最值可以不唯一,所以不必为严格单调
		while(hh <= tt && a[q[tt]] >= a[i]) tt--;
		q[++tt] = i;
		//注意是输出窗口内的最值,数字若不足3个则不构成窗口,不输出
		if(i+1 >= k) cout << a[q[hh]] << ' ';
	}
	cout << endl;
	
	hh = 0, tt = -1;
	for(int i = 0; i < n; i++)
	{
		//判断队头是否滑出窗口
		while(hh <= tt && i-k+1 > q[hh]) hh++;
		
		//最大值同理,删除掉数组中的升序逆序对,维护为单调递增序列即可
		while(hh <= tt && a[q[tt]] <= a[i]) tt--;
		q[++tt] = i;
		
		if(i+1 >= k) cout << a[q[hh]] << ' ';
	}

	return 0;
}

KMP

Acwing-831 KMP字符串

原题链接

思路
模板题。
参考代码
#include <iostream>
using namespace std;

const int N = 1e5+10;
const int M = 1e6+10;
int n, m, ne[N];	// s[]是长文本,p[]是模式串,m是s的长度,n是p的长度
char p[N], s[M];

int main(void)
{
	cin.tie(0), cout.tie(0);ios::sync_with_stdio(false);

	//这里KMP算法的下标从1开始
	cin >> n >> (p + 1) >> m >> (s + 1);

	//得到next数组(双指针算法)
	//next数组为模式串的子串中前缀和后缀相同的最大长度,即若有不匹配的情况时可以让模式串往后移动的最少次数
	for(int i = 2, j = 0; i <= n; i++)
	{
		while(j && p[i] != p[j+1]) j = ne[j];   //这一步是j指针先回退后,模式串移动到j指针所指向的地方
		if(p[i] == p[j+1]) j++;
		ne[i] = j;
	}

	for(int i = 1, j = 0; i <= m; i++)
	{
		while(j && s[i] != p[j+1]) j = ne[j];
		if(s[i] == p[j+1]) j++;
		if(j == n)
		{
			j = ne[j];  
			cout << i-n << ' ';
		}
	}

	return 0;
}

Trie

Acwing-835

原题链接

思路
模板题。
参考代码
#include <cstdio>
#include <cstring>

//下列写法适用于只包含小写字母的字符串
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点,第一维为节点总数,第二维为某节点的子节点最大数量,比如这里是26,因为小写字母只有26种情况,若为二进制串则只有两种情况。
// cnt[]存储以每个节点结尾的单词数量
const int maxn = 1e5 + 10;
int n, son[maxn][26], cnt[maxn], idx;
char str[maxn];

// 插入一个字符串
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]++ ;
}

// 查询字符串出现的次数
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];
}

int main(void)
{
    scanf("%d", &n);
    getchar();
    while(n--)
    {
        char op;
        memset(str, 0, sizeof(str));
        scanf("%c %s", &op, str);
        getchar();
        if(op == 'I') insert(str);
        else printf("%d\n", query(str));

    }

    return 0;
}

Acwing-143

原题链接

思路
要使得异或和最大,从最高位开始遍历,两数二进制表示在高位不同的数的个数越多,异或和就越大。
参考代码
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 100010, maxm = 3100010;
int son[maxm][2], idx, a[maxn];

void insert(int x)
{
	int p = 0;
	for(int i = 30; i >= 0; i--)	//从二进制最高位开始遍历存储到trie树中
	{
		int u = x >> i & 1;
		if(!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
	}
}

int query(int x)
{
	int p = 0, res = 0;
	for(int i = 30; i >= 0; i--)
	{
		//求得二进制表示的第i位数字
		int u = x >> i & 1;
		if(son[p][!u])
		{
			p = son[p][!u];
			res = res * 2 + !u;
		}
		else
		{
			p = son[p][u];
			res = res * 2 + u;
		}
	}

	return res;
}

int main(void)
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);

	int ans = 0;
	for(int i = 0; i < n; i++) 
	{
		insert(a[i]);
		int t = query(a[i]);
		ans = max(ans, a[i] ^ t);
	}
	printf("%d\n", ans);

	return 0;
}

并查集

Acwing-836

原题链接

思路
参考代码

Acwing-837

原题链接

思路
参考代码

Acwing-240

原题链接

思路
参考代码

Acwing-838

原题链接

思路
参考代码

Acwing-839

原题链接

思路
参考代码

哈希表

Acwing-840

原题链接

思路
参考代码

Acwing-841

原题链接

思路
参考代码