链表、栈与队列、kmp;
数组模拟单链表:
用的最多的是邻接表–就是多个单链表:
作用:存储树与图
需要明确相关定义:
为什么需要使用数组模拟链表
- 比使用结构体 或者类来说 速度更快
- 代码简洁
- 算法题:空间换时间
题目详情
图解:
head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
import java.util.*;
public class Main{
static int N = 100010;
static int idx,head;
static int[] e = new int[N];
static int[] next = new int[N];
// 初始化
static void init(){
head = -1;
idx = 0;
}
// 向链表头插入一个数
static void insertHead(int x){
e[idx] = x;
next[idx] = head;
head = idx++;
}
// 向k位置插入x
static void insert(int k,int x){
e[idx] = x;
next[idx] = next[k];
next[k] = idx++;
}
// 删除k位置的数
static void delete(int k){
next[k] = next[next[k]];
}
// 主函数
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
init();
int n = sc.nextInt();
while(n-- != 0){
String s = sc.next();
if(s.equals("H")){
int x = sc.nextInt();
insertHead(x);
}else if(s.equals("D")){
int k = sc.nextInt();
if(k == 0) head=next[head];
else delete(k-1);
}else if(s.equals("I")){
int k = sc.nextInt();
int x = sc.nextInt();
insert(k-1,x);
}
}
for(int i =head;i != -1;i=next[i]){
System.out.print(e[i]+" ");
}
}
}
数组模拟双链表:
作用:优化某些问题
题目详情
栈:
先进后出
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空
if (tt > 0)
{
}
队列:
先进先出
1. 普通队列:
// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh <= tt)
{
}
2. 循环队列
// hh 表示队头,tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空
if (hh != tt)
{
}
单调栈:
题目详情
每个数找到左边离自己最近且比自己小的数:
暴力算法 :
import java.util.*;
import java.io.*;
public class Main{
static int N = 100010;
static int[] q = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 0;i < n; i++){
q[i] = sc.nextInt();
}
for(int i = 0;i < n;i++){
int index =0;
for(int j = i-1;j >=0;j--){
if(q[i]>q[j]){
index = j;
System.out.print(q[j]+" ");
break;
}
}
if(q[i]<=q[index]){
System.out.print("-1 ");
}
}
}
}
AC代码:
import java.util.*;
public class Main{
static int N = 100010;
static int[] stk = new int[N];
static int tt=0;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 0; i < n; i++){
int x = sc.nextInt();
// 如果栈中还有元素并且栈顶元素大于x的话,从栈顶弹出;
while(tt != 0 && stk[tt] >= x) tt--;
// 上面结束以后是栈顶元素小于输入的元素; stk[tt] < x; 这样就保证了x元素在左边并且小于本身的元素是栈顶元素;
//如果栈中有元素,输出栈顶元素
if(tt != 0) System.out.print(stk[tt]+" ");
// 否则栈中没有元素
else System.out.print("-1"+" ");
// 将元素加入栈中
stk[++tt] = x;
}
}
}
单调队列:
滑动窗口:
解题思路:
- 判断队头出没出窗口 if true–>hh++;
- 求最小值,保持队列单调上升,判断队尾元素tt与当前元素a[i]的大小,若tt >=a[i],剔除队尾元素;
- 求最大值,保持队列单调下降,判断队尾元素tt与当前元素a[i]的大小,若tt <=a[i],剔除队尾元素;
- 将当前元素下标加入队尾;
- 如果满足条件输出
注:队列是先进先出模式,只有在队列中保持单调性 才能保证,队头为最小值或者最大值;
import java.io.*;
public class Main{
static int N = 1000010;
// 原数组
static int[] a = new int[N];
// 队列
static int[] q = new int[N];
static int hh=0,tt=-1;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] num = br.readLine().split(" ");
// a数组中由n个元素
int n = Integer.parseInt(num[0]);
// 滑动窗口的大小
int k = Integer.parseInt(num[1]);
String[] nums = br.readLine().split(" ");
// 初始化a数组
for(int i = 0; i < n; i++) a[i] = Integer.parseInt(nums[i]);
// 查找最小值
for(int i = 0; i < n; i++){
// 判断当前窗口是否大于滑动窗口的大小
if(hh <= tt && i-q[hh]+1 > k) hh++;
// 判断如果有元素并且队尾元素大于入队元素,则舍弃队尾元素来保证单调上升的队列;
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
//向队列加入元素下标
q[++tt] = i;
// 如果下标大于等于窗口大小,那么输出队头元素
if(i+1 >=k) bw.write(a[q[hh]]+" ");
}
bw.write("\n");
hh = 0;
tt = -1;
// 查找最大值
for(int i = 0; i < n; i++){
// 判断当前窗口是否大于滑动窗口的大小
if(hh <= tt && i-q[hh]+1 > k) hh++;
// 判断如果有元素并且队尾元素小于入队元素,则舍弃队尾元素来保证单调上升的队列;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
//向队列加入元素下标
q[++tt] = i;
// 如果下标大于等于窗口大小,那么输出队头元素
if(i+1 >=k) bw.write(a[q[hh]]+" ");
}
bw.flush();
br.close();
bw.close();
}
}
KMP算法:
KMP定义:是取自三个发明人的首字母组成的;
作用:是一个字符串匹配算法,对暴力的一种优化
kmp实现的方式:求next[]、以及匹配字符串
明确其中的概念:
对字符串的匹配,需要两个字符串:长字符串为模板字符串,短的字符串为匹配字符串;
前缀与后缀的概念:(很重要)
举个例子:枚举
ababa
其前缀为:
a,ab,aba,abab
其后缀:
baba,aba,ba,a
其中前缀与后缀的最长且相同的元素字符串是:aba
;长度length:3。
模板串的匹配:
匹配失败的话,假设p1串往后移动到p2串位置,表明1串=2.2串;
\[\because 匹配失败使得p1移动到p2位置\\ \therefore s-1 = p2-2.2\\ \because p2是p1的平移\\ \therefore p1 = p2\\ \therefore p1-2.1 = p2-2.2\\ 又\because s = p1\\ \therefore s-1 = p1-3\\ 由上可知:\\ p2-2.2 = p1-3;\\ p1-2.1 = p1-3; \]
如果匹配失败,p串最少往右移动多少(看next[]数组),可以使得p串与s串相等,由图可知:往后移动多少是看p串,如果我们能预处理来这个东西:使得p1-2.1串能与p1.3串相等;这个相等的最大值是多少,值越大,则表示往后移动p串的距离越少;
// kmp匹配过程,遍历s模板每个元素
for(int i =1, j =0; i<=m; i++ ){
// 如果j回退到0或者i位置元素与j+1位置的元素不相同,那么执行回退操作,
//j退回next[i]处,即前缀与后缀相同的区间最后元素位置
while(j != 0 && s[i] != p[j+1]) j = next[j];
if(s[i] == p[j+1]) j++;
// 如果匹配成功
if(j ==n){
// 输出匹配元素在s模板中的起始位置
bw.write(i-n+" ");
// 继续匹配;
j = next[j];
}
也就是p串的前缀与后缀相同的最大字串是多少;—-也就是next[]数组;
next[]数组(难点)
其中next[j]数组表示的是:子串p[1~j]的最长相等前后缀的前缀最后一位的下标。
对 p = “abcab”
p a b c a b
下标 1 2 3 4 5
next[ ] 0 0 0 1 2
对next[ 1 ] :前缀 = 空集—————后缀 = 空集—————next[ 1 ] = 0; (特殊点)
对next[ 2 ] :前缀 = { a }—————后缀 = { b }—————next[ 2 ] = 0;
对next[ 3 ] :前缀 = { a , ab }—————后缀 = { c , bc}—————next[ 3 ] = 0;
对next[ 4 ] :前缀 = { a , ab , abc }—————后缀 = { a . ca , bca }—————next[ 4 ] = 1;
对next[ 5 ] :前缀 = { a , ab , abc , abca }————后缀 = { a , ab , cab , bcab}————next[ 5 ] = 2;
// 实现next数组(找到前缀与后缀相同的最大元素长度)
int[] next = new int[n+1];
//next[1] = 0;
for(int i = 2,j =0; i<= n;i++){
// 如果j没有回退到0并且i位置元素与j+1位置的元素不相同,那么执行回退操作,
//j退回next[i]处,即前缀与后缀相同的区间最后元素位置
while(j !=0 && p[i] != p[j+1]) j = next[j];
// 如果i与j+1相同,那么移动j向后匹配
if(p[i] == p[j+1]) j++;
// p[1,j] = p[i-j+1,i];前缀与后缀相同;i表示终点
next[i] = j;
}
完整代码:
import java.util.*;
import java.io.*;
//下标为什么从1开始,简化代码的复杂度;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 对模式串p进行操作
int n = Integer.parseInt(br.readLine());
char[] p = new char[n+1];
// 将输入的字符保存到缓冲区
String pstr = br.readLine();
for(int i = 1; i <=n;i++){
// 取出的字符串下标-1;
p[i] = pstr.charAt(i-1);
}
// 对模板串进行操作
int m = Integer.parseInt(br.readLine());
char[] s = new char[m+1];
String sstr = br.readLine();
for(int i = 1;i <= m;i++){
s[i] = sstr.charAt(i-1);
}
// 实现next数组
int[] next = new int[n+1];
//next[1] = 0;
for(int i = 2,j =0; i<= n;i++){
// 如果j回退到0或者i位置元素与j+1位置的元素不相同,那么执行回退操作,
//j退回next[i]处,即前缀与后缀相同的区间最后元素位置
while(j !=0 && p[i] != p[j+1]) j = next[j];
// 如果i与j+1相同,那么移动j向后匹配
if(p[i] == p[j+1]) j++;
// p[1,j] = p[i-j+1,i];前缀与后缀相同;i表示终点
next[i] = j;
}
// kmp匹配过程,遍历s模板每个元素
for(int i =1, j =0; i<=m; i++ ){
// 如果j回退到0或者i位置元素与j+1位置的元素不相同,那么执行回退操作,
//j退回next[i]处,即前缀与后缀相同的区间最后元素位置
while(j != 0 && s[i] != p[j+1]) j = next[j];
if(s[i] == p[j+1]) j++;
// 如果匹配成功
if(j ==n){
// 输出匹配元素在s模板中的起始位置
bw.write(i-n+" ");
// 继续匹配;
j = next[j];
}
}
bw.flush();
br.close();
bw.close();
}
}
结束:
感谢大家看到最后,如果有错误,欢迎指正!
参考文献:https://www.acwing.com/solution/content/14666/