链表、栈、队列、KMP相关知识点

时间：2024-11-12 23:04:02

链表、栈与队列、kmp;

数组模拟单链表：

用的最多的是邻接表--就是多个单链表：

作用：存储树与图

需要明确相关定义：

为什么需要使用数组模拟链表

  1. 比使用结构体 或者类来说 速度更快
  2. 代码简洁
  3. 算法题：空间换时间

题目详情

图解：

链表、栈、队列、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;

        }

    }

}

单调队列:

滑动窗口：

解题思路：

  1. 判断队头出没出窗口 if true-->hh++;
  2. 求最小值，保持队列单调上升，判断队尾元素tt与当前元素a[i]的大小，若tt >=a[i],剔除队尾元素；
  3. 求最大值，保持队列单调下降，判断队尾元素tt与当前元素a[i]的大小，若tt <=a[i],剔除队尾元素；
  4. 将当前元素下标加入队尾；
  5. 如果满足条件输出

注：队列是先进先出模式，只有在队列中保持单调性 才能保证，队头为最小值或者最大值；

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。

模板串的匹配：

链表、栈、队列、KMP相关知识点

链表、栈、队列、KMP相关知识点

匹配失败的话，假设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;

链表、栈、队列、KMP相关知识点

// 实现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/

相关文章