复习THIRD_C/C++/C#

文章目录

- 1、链表
- - 1.1单链表
  - 1.2双链表
- 2、模拟栈
- 3、模拟队列
- 单调栈
- 滑动窗口
- KMP

1、链表 1.1单链表

输入：

输出：

6 4 6 5

链表所要熟记的就是 e[]，ne[] 和 head 这三个值，他们分别表示第 k 个插入的值，第 k 个插入的值所指向的下一个指针（这个指针指的是下一个值是第几个插入的值）和头指针，头指针指的是表头数是第几个插入的；

以下为本题三个操作：
1、向链表头插入一个数 x：
此时只需新建数组 e，然后将 ne 指针指向head，（此操作是为指向原表头，但如果head= -1，则表示结束），最后将head指向新表头，head归位；

2、表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）：
此时只需第 k 个插入的数的ne指向下一个数的ne就可以完成删除；
当k=0时，加一层特判，使得头指针指向原来指向的后一个数，完成删除头指针操作；

3、表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）：
首先新建一个e，然后使其ne指向 ne[k]，最后使 ne[k] 指向新来的数，完成插入；

#include

using namespace std;
typedef long long ll;
const ll N=1020;
ll e[N],ne[N],head=-1,idx;

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

void add(int k,int x) {
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx;
	idx++;
}

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

int main() {
	ll n;
	cin>>n;
	char a;
	while(n--) {
		cin>>a;
		if(a=='H') {
			int b;
			cin>>b;
			add_head(b);
		} else if(a=='I') {
			int b,c;
			cin>>b>>c;
			add(b-1,c);
		} else if(a=='D') {
			int b;
			cin>>b;
			if(b==0) {
				head=ne[head];
			}
			cut(b-1);
		}
	}
	for(ll i=head; i!=-1; i=ne[i]) {
		cout< 
1.2双链表 

 双链表在单链表的基础上加了向左指的指针，由ne 分为了 l 和 r 两个部分，L指向左侧，r 指向右侧，其他执行方式可以利用单链表进行理解； 
要注意的是，此双链表中默认0为开头，1为结尾 idx 默认从2开始，故输入位数 k 后执行任务需要 +1；以及输出语段： 
for(int i=r[0];i!=1;i=r[i]){
	cout< 
从 r[0] 开始，遇到 1 结束； 
#include

using namespace std;
typedef  long long ll;
const ll N=1020;
ll e[N],l[N],r[N],idx=2;

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

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

int main() {
	ll n;
	cin>>n;
	r[0]=1,l[1]=0;
	while(n--) {
		string a;
		int k,x;
		cin>>a;
		if(a=="L") {
			cin>>x;
			insert(0,x);
		} else if(a=="R") {
			cin>>x;
			insert(l[1],x);
		} else if(a=="D") {
			cin>>k;
			cut(k+1);
		} else if(a=="IL") {
			cin>>k>>x;
			insert(l[k+1],x);
		} else if(a=="IR") {
			cin>>k>>x;
			insert(k+1,x);
		}
	}
	for(int i=r[0];i!=1;i=r[i]){
		cout< 
2、模拟栈 

 输入： 
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
 
输出： 
5
5
YES
4
NO
 
这就是用数组模拟stack的一个过程，将数组的最后一个数视为栈顶来执行操作； 
#include

using namespace std;
typedef long long ll;
const ll N=1020;
ll a[N],tt,n;

int main(){
	cin>>n;
	while(n--){
		string op;
		ll x;
		cin>>op;
		if(op=="push"){
			cin>>x;
			a[++tt]=x;
		}else if(op=="pop"){
			--tt;
		}else if(op=="empty"){
			cout<<(tt? "NO": "YES")< 
我做过STL的思维导图，但是太大了放不进来，只好截取了stack的一部分：
 
 将程序改用stack走一遍： 
#include

using namespace std;
typedef long long ll;
const ll N=1020;
ll a[N],tt,n;
stack b;

int main(){
	cin>>n;
	while(n--){
		string op;
		ll x;
		cin>>op;
		if(op=="push"){
			cin>>x;
			b.push(x);
		}else if(op=="pop"){
			b.pop();
		}else if(op=="empty"){
			cout<<(b.empty() ? "YES": "NO")< 
还有一个不熟悉的点： 
(A? "YES": "NO");
 
意思等于： 
if(A) cout<<"YES";
else cout<<"NO";
 
3、模拟队列 

 输入： 
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6
 
输出： 
NO
6
YES
4
 
这题模拟的是STL中的queue队列，可以再加一个任务：back 返回队尾元素；
 
 此题是向队尾插入元素，并需要返回队头元素，所以此处用两个指针hh和tt，hh指向队头，tt指向队尾，当hh 
#include

using namespace std;
typedef long long ll;
const ll N=1020;
ll a[N],hh,tt,n;

int main(){
	cin>>n;
	while(n--){
		string op;
		ll x;
		cin>>op;
		if(op=="push"){
			cin>>x;
			a[tt++]=x;
		}else if(op=="pop"){
			hh++;
		}else if(op=="empty"){
			cout<<(hh
			cout<
			cout< 
改用STL： 
#include

using namespace std;
typedef long long ll;
const ll N=1020;
ll a[N],hh,tt,n;
queue b;

int main(){
	cin>>n;
	while(n--){
		string op;
		ll x;
		cin>>op;
		if(op=="push"){
			cin>>x;
			b.push(x);
		}else if(op=="pop"){
			b.pop();
		}else if(op=="empty"){
			cout<<(b.empty()?"YES":"NO")<
			cout<
			cout< 
单调栈 

 输入： 
5
3 4 2 7 5
 
输出： 
-1 3 -1 2 2
 
这题很容易理解，就是使用数组模拟，每输入一个数时，保存包括这个数之前第一个比他小的数以及这个数之前的数，当没有比他小的值时输出 -1； 
最后stk数组保存的序列应该是一个递增的序列； 
#include 

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[ ++ tt] = x;
    }

    return 0;
}
 
滑动窗口 

 
 输入： 
8 3
1 3 -1 -3 5 3 6 7
 
输出： 
-1 -3 -3 -3 3 3
3 3 5 5 6 7
 
这题比较复杂，一部分一部分来看； 
这题涉及双指针，hh指向窗口内最小值的在a数组的下标，tt指向新读取的数，q数组中hh到tt之间存储的是向右移时每个窗口的最小值； 
这块代码是为了控制存储在hh-tt范围内的q数组中的数在窗口范围内，譬如当p[0]=3，i=6时a[p[0]]=-3，存储的还是前一个窗口内的最小值，但是i-p[0]=3，说明窗口已经滑动到取不到**-3的位置了，此时hh++**，**p[hh]**就是下一个窗口的最小值； 
 
 if(hh<=tt&&i-k+1>q[hh]) hh++; 
 
这块代码执行的就是寻找窗口内的最小值位置存储进q的命令，当q中有比i更大的值就删除他们，同时存储新i，从而保证 q[hh] 一定是窗口内的最小值，hh<=tt又能保证滑动窗口内有值存储在q中； 
 
 while(hh<=tt&&a[q[tt]]>=a[i]) tt–;
 q[++tt]=i; 
 
然后当i>=k-1时，也就窗口滑动到已经包括k个数字了，逐个输出； 
输出窗口内最大值就是把a[q[tt]]>=a[i]改成了a[q[tt]]<=a[i]； 
#include

using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll a[N],q[N],hh,tt;

int main() {
	ll n,k;
	cin>>n>>k;
	for(ll i=0; i
		cin>>a[i];
	}
	hh=0,tt=-1;
	for(ll i=0; i
		if(hh<=tt&&i-k+1>q[hh]) hh++;
		while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
		q[++tt]=i;
		if(i>=k-1) cout<
		if(hh<=tt&&i-k+1>q[hh]) hh++;
		while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
		q[++tt]=i;
		if(i>=k-1) cout< 
KMP 

 输入： 
3
aba
5
ababa
 
输出： 
0 2
 
KMP里面最重要的就是ne数组，在数组某一位置之前的子串中，取一部分作为子子串，满足此子子串既是此子串的前缀和后缀，而 ne 数组存储的就是此位置的子子串的长度； 
还有一个要注意的细节就是因为在比较过程中s和p需要错位比较，所以在输入时后移一位输入： 
 
 cin >> n >> p + 1 >> m >> s + 1; 
 
还有while的深意，还没参悟… 
#include

using namespace std;
typedef long long ll;
const ll N=1020;
ll n,m,ne[N];

int main() {
	char s[N],p[N];
	cin>>n>>p+1>>m>>s+1;

	for(ll i=2,j=0; i<=n; i++) {
		while(j&&p[i]!=p[j+1]) j=ne[j];
		if(p[i]==p[j+1]) j++;
		ne[i]=j;
	}

	for(ll 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) {
			cout<

复习THIRD

C/C++/C#相关栏目本月热门文章