做网站这么便宜可以吗,wordpress 百度云,vs2010网站开发 调试 打不开页面 浏览器错误,成都网站建设58文章目录整体结构为什么用数组链表与邻接表单链表存储插入插入至头结点将x插入到下标为k的点后面删除遍历双链表初始化插入删除邻接表栈和队列栈队列单调栈单调队列KMP整体结构
链表与邻接表#xff08;用数组模拟#xff09;栈与队列#xff08;用数组模拟#xff09;kmp…
文章目录整体结构为什么用数组链表与邻接表单链表存储插入插入至头结点将x插入到下标为k的点后面删除遍历双链表初始化插入删除邻接表栈和队列栈队列单调栈单调队列KMP整体结构
链表与邻接表用数组模拟栈与队列用数组模拟kmp 背还是要背的考试的时候再想是来不及的 熟练掌握非常快地将代码默写出来像背古诗背单词一样 应试教育 记忆力毅力/自制力 沉下心来好好背东西 为什么用数组
结构体加指针
struct Node
{int val;Node *next;
}//不讲面试比较多笔试比较少
new Node();//非常慢笔试的话10000或者1000000笔试不采用动态链表方式链表与邻接表
用数组模拟 单链表 邻接表 其实是n个链表最主要应用是存储图和树 双链表 优化某些问题
单链表
存储 $$
$$ 每个点有两个值e与ne通过下标相互关联空节点的下标用-1表示
插入
单链表只向后看不往前看。
插入至头结点 先处理插入值的ene之后处理前驱head与idx
将x插入到下标为k的点后面 先处理插入值的ene之后处理前驱ne[k]与idx
删除 通过ne[k]找到后继通过ne[ne[k]]找到后继的后继
遍历
从下标为head一直到-1
关于链表的删除
算法题不是写工程写工程为动态链表需要考虑空间释放与内存泄漏
算法题不需要负责浪费就浪费,只需要保证程序在1s内执行完毕
#include iostream
using namespace std;
const int N 100010;//head 表示头结点的下标所有节点都可以用下标来索引
//e[i] 表示节点i的值
//ne[i] 表示节点i的next指针是多少节点i的下一个坐标在什么地方
//idx 指针从第一个点开始存储当前已经用到的哪个地址。
//当需要分配新的点的时候将idx指向的节点分配idx向后移动一位
int head,e[N],ne[N]idx;//初始化
void init()
{head -1; //空的idx 0;
}//将x插入头结点,算法题中80%操作是把节点插入至头结点
void add_to_head(int x)
{//分配节点e[idx] x,ne[idx] headhead idx;idx;
}//将x插入到下标为k的点后面
void insert(int x,int k)
{e[idex] x,ne[idex] ne[k],ne[k] idx,idx;
}//将下标是k的点后面的点删掉
void remove(int k)
{ne[k] ne[ne[k]];
}具体题目
//826
实现一个单链表链表初始为空支持三种操作向链表头插入一个数
删除第 k 个插入的数后面的数
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作进行完所有操作后从头到尾输出整个链表。注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数则按照插入的时间顺序这 n 个数依次为第 1 个插入的数第 2 个插入的数…第 n 个插入的数。输入格式
第一行包含整数 M表示操作次数。接下来 M 行每行包含一个操作命令操作命令可能为以下几种H x表示向链表头插入一个数 x。
D k表示删除第 k 个插入的数后面的数当 k 为 0 时表示删除头结点。
I k x表示在第 k 个插入的数后面插入一个数 x此操作中 k 均大于 0。
输出格式
共一行将整个链表从头到尾输出。数据范围
1≤M≤100000
所有操作保证合法。输入样例
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例
6 4 6 5#include iostream
using namespace std;
const int N 100010;//head 表示头结点的下标注意是下标
//e[i] 表示节点i的值
//ne[i] 表示节点i的next指针是多少
//idx 存储当前已经用到的哪个点
int head,e[N],ne[N],idx;//初始化
void init()
{head -1;idx 0;
}//将x插入头结点
void add_to_head(int x)
{//处理e,ne数组e[idx] x,ne[idx] head;//处理idxhead idx;//最后idx移位idx;
}//将x插入到下标为k的点后面
void add(int k,int x)
{e[idx] x,ne[idx] ne[k],ne[k] idx,idx;
}//将下标是k的点后面的点删掉
void remove(int k)
{ne[k] ne[ne[k]];
}int main()
{int m;cinm;init();while(m--){int k,x;char op;cinop;if(op H){cinx;add_to_head(x);}else if(op D){cink;//特判 k 0if(!k) head ne[head];else remove(k-1);}else{cinkx;add(k-1,x);}}//遍历链表,注意终止条件是到达链表尾部即下标变为-1初始化时head -1,-1代表尾节点下标随着不断插入-1一直向后移动for(int i head;i!-1;i ne[i]) coute[i] ;coutendl;return 0;
}双链表
让下标为0的点为头结点下标为1的点为尾节点 初始化 为方便下标为0为头部下标为1为尾部任意节点最终都插入至两者之间因此不需要head指针
插入
在在下标为k的右边插入一个点 在下标为k的左边插入一个点 add(l[k],x)
为避免出错先处理左指针再处理右指针先左后右。
删除 #include iostreamusing namespace std;const int N 100010;int m;int e[N],l[N],r[N],idx;
/*
struct Node
{int l,r,e;
}nodes[N]
*/
//初始化
void init()
{//0表示左端点1表示右端点r[0] 1,l[1] 0;idx 2;
}
//在下标为k的右边插入一个点
void add(int k,int x)
{e[idx] x;l[idx] k;r[idx] r[k];l[r[k]] idx;r[k] idx; idx;
}//删除第k个点
void remove(int k)
{l[r[k]] l[k];r[l[k]] r[k];//如果使用结构体//nodes[nodes[k].l].r nodes[k].r;
}邻接表
邻接表就是一堆单链表 栈和队列 栈
特点头插头出 #include iostreamusing namespace std;const int N 100010;
//*******************************栈
//tt 栈顶下标 tt 0 ,stk[0]不存放数据
int stk[N],tt;//插入
stk[tt] x;
//删除
tt--//判断栈是不是为空
if(tt0) not empty
else empty//栈顶
stk[tt]队列 特点
尾插头出 //******************************** 队列
//hh 队头tt 队尾
//在队尾插入元素在队头弹出元素
int q[N],hh,tt -1;
//插入
q[tt] x;//从队头弹出
hh;
//从队尾弹出
tt--;//判断是否为空
if(hh tt) not empty
else empty//取出队头元素
q[hh]
//取队尾元素
q[tt]单调栈
给定一个长度为 N 的整数数列输出每个数左边第一个比它小的数如果不存在则输出 −1。输入格式
第一行包含整数 N表示数列长度。第二行包含 N 个整数表示整数数列。输出格式
共一行包含 N 个整数其中第 i 个数表示第 i 个数的左边第一个比它小的数如果不存在则输出 −1。数据范围
1≤N≤105
1≤数列中元素≤109
输入样例
5
3 4 2 7 5
输出样例
-1 3 -1 2 2 思路先想一下暴力做法是什么再挖掘一些性质使我们可以将目标集中在比较少的状态中从而将问题的复杂度降低
暴力思路 性质i向右移动过程中用一个栈存储i左边的所有元素 栈里面是不是有些元素永远不会输出来 举例 数字2在4的后面输入2比4小并且在4的后面因此4永远不会被输出。在单调栈中应该提前弹出。
删除不会输出的点剩余点的格式严格单调上升 时间复杂度每个元素只会进栈一次每个元素只会出栈一次。所以最多2n次操作。
不会从头操作整个算法的复杂度为o(n)
#include iostreamusing namespace std;const int N 100010;int n;
int stk[N],tt;int main()
{// ios::sync_with_stdio(false);// cin n;scanf(%d,n);for(int i 0;in;i){int x;// cinx;scanf(%d,x);//栈中如果存在数据while(tt)并且栈中数据比x大进行出栈每个数据执行这个过程while(tt stk[tt] x) tt--;// if(tt) coutstk[tt] ;//如果栈中存在数据打印栈顶元素if(tt) printf(%d ,stk[tt]);else printf(-1 );// else cout -1 ;//进栈stk[tt] x;}
}简洁版
#include iostreamusing namespace std;const int N 100010;int stk[N],tt 0;int main()
{int n,x;scanf(%d,n);for(int i 0;i n;i){scanf(%d, x);while(tt stk[tt] x) tt--;if(tt) printf(%d ,stk[tt]);else printf(-1 );stk[tt] x;}}单调队列
最常见题型就几道。最典型问题
思路相同
先想一下暴力做法怎么做观察其中没有用的元素把其中没有用的元素删掉得到单调性。在看有没有单调性。有单调性的话再去优化问题
给定一个大小为 n≤106 的数组。有一个大小为 k 的滑动窗口它从数组的最左边移动到最右边。你只能在窗口中看到 k 个数字。每次滑动窗口向右移动一个位置。以下是一个例子该数组为 [1 3 -1 -3 5 3 6 7]k 为 3。 你的任务是确定滑动窗口位于每个位置时窗口中的最大值和最小值。输入格式
输入包含两行。第一行包含两个整数 n 和 k分别代表数组长度和滑动窗口的长度。第二行有 n 个整数代表数组的具体数值。同行数据之间用空格隔开。输出格式
输出包含两个。第一行输出从左至右每个位置滑动窗口中的最小值。第二行输出从左至右每个位置滑动窗口中的最大值。输入样例
8 3
1 3 -1 -3 5 3 6 7
输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7暴力求解方法 O(nk)
栈里面存储元素的下标窗口由队列来维护保证队列中时时刻刻保存当前窗口的元素
栈里面存储元素的下标
步骤
在队尾插入1、3、-1 第四次先在队尾插入-3然后在队头弹出1窗口由队列来维护保证队列中时时刻刻保存当前窗口的元素
优化-3进来以后3、-1永远不会输出。前面值比后面值大前面的数值一定不会弹出来。因此可以将前面数值较大的点删除。整个队列成为严格上升的趋势。一个严格上升的最小值在队头。每次找最小值找队头就可以了 3 、-1会被弹出。3是头-3是尾巴
新插入的值比队尾大的时候将队尾删除 1. 如何判断窗口长度是否溢出
队列中存储的数组下标而不是存储数据值因为如果存储数据值则无法进行判断到底是否溢出。存储下标的话只需要套一层就可以得到对应的数据值。
i–当前队列的右端点。k–窗口长度
队列中存储的不是值而是数组下标。
队头的下标是否超出了i-k1,i,如果超出弹出队头
#include iostreamusing namespace std;const int N 1000010;int n,k;
//a[N]val q[N]队列中存储下标想要取值的时候还需要套一层
int a[N],q[N];
int main()
{scanf(%d%d,n,k);for(int i 0 ;in;i) scanf(%d,a[i]);int hh 0,tt -1;for(int i 0;in;i){//1. 判断队头是否已经划出窗口--判断是不是空的并且当前是i。//由于遍历每次最多只有一个数不在窗口内写if足够使用//q[hh]当前头部下标 i-k1 窗口的最左端if(hhtt q[hh] i-k1) hh;//2. 如果新插入的数比队尾小则队尾不起作用删除队尾直到小于新插入的数为止while(hhtt a[q[tt]]a[i]) tt--;//3. 在队尾插入新的数组下标索引q[tt] i;//4. 当i不足k时不用输出if(ik-1) printf(%d ,a[q[hh]]);}puts();hh 0,tt -1;for(int i 0;in;i){//判断队头是否已经划出窗口if(hhtt i-k1 q[hh]) hh;while(hhtt a[q[tt]]a[i]) tt--;q[tt] i;if(ik-1) printf(%d ,a[q[hh]]);}puts();return 0;
}KMP
给定一个字符串 S以及一个模式串 P所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现的位置的起始下标。输入格式
第一行输入整数 N表示字符串 P 的长度。第二行输入字符串 P。第三行输入整数 M表示字符串 S 的长度。第四行输入字符串 S。输出格式
共一行输出所有出现位置的起始下标下标从 0 开始计数整数之间用空格隔开。数据范围
1≤N≤105
1≤M≤106
输入样例
3
aba
5
ababa
输出样例
0 2用朴素算法解决KMP问题 用图表示匹配过程红绿圈之前的字符串均相同。暴力做法移动一位之后再进行匹配 假定移动一定长度后可以重新匹配即下图所示的情况。蓝色表示的为同一块区域 则存在蓝色与棕色相等的关系。因此可以对模板串进行预处理。需要对每一个点都预处理。即后缀与前缀相等。相等的最大长度是多少。 next数组含义
以i为终点的后缀与一开始的前缀相等并且后缀的长度最长
如下图表示
next[i] j即p[1, j] p[p-j1,i] 最多向后移动多长距离只和模板串有关系–后缀与前缀相等的最大长度是多少 以最终对比为例移动后点不同点变为next[j],再对比后面的值 求next数组的过程 #include iostream
using namespace std;const int N 100010,M 1000010;int n,m;char p[N],s[M];
//next数组在某些头文件中用过用的时候可能报错因此替换为ne
int ne[N];int main()
{//数组下标从1开始cinn p 1 m s 1;//求next过程//i是从2开始ne[1] 0:因为如果ne[1]失败后只能从0开始因此不必要计算for(int i 2,j 0;in;i){//while(j p[i] ! p[j1]) j ne[j];if(p[i] p[j1]) j;ne[i] j;}//KMP匹配过程//i是遍历所有数组j是从0开始做for(int i 1,j 0;i m;i){//j没有退回起点并且当前s[i]与p[j1]不同s[i]不能与我下一个j去匹配//直到j退到开头退无可退或者可以匹配了//判断j是否退无可退与是否j可以向后走//如果最终真的退无可退了直接对比原始串的下一个字符即iwhile(j s[i] ! p[j1]) j ne[j];//如果两者匹配了j移动到下一位置jif(s[i] p[j1]) j;if(j n){//匹配成功printf(%d ,i-n);//完全匹配成功后向后移动的下标j ne[j];}}return 0;
}举例 P的next数组前缀与后缀相等的最大长度
next下标数值102031425364for(int i 2,j 0;in;i){while(j p[i] ! p[j1]) j ne[j];if(p[i] p[j1]) j;ne[i] j;}
