• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 2周前 (02-21) 6次浏览

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


程序员灯塔
转载请注明原文链接:链表、栈、队列、KMP相关知识点
喜欢 (0)