《算法基础》数据结构

链表

这里只介绍静态链表

静态链表的虽然浪费一定的空间,但是胜在效率高,动态链表的new操作浪费大量的时间.

单链表的实现:

实现三个基本操作:
在头节点插入

删除第k个数的后面一个数(可以自己控制,使得删除第k个数)

在第k个数后面插入一个元素.

具体题型:

h数组为存储元素的数组,ne为链表的下一个节点的下标.

head为头结点,idx为用到的所有下标值.

import java.util.*;
public class Main{
    public static int h[] = new int[100010];
    public static int ne[] = new int[100010];
    public static int head = -1;
    public static int idx = 0;
    public static void inserthead(int x){
        h[idx] = x;
        ne[idx] = head;
        head = idx;
        idx++;
    }
    public static void delete(int k){
        ne[k] = ne[ne[k]];
    }
    public static void insert(int x,int k){
        h[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx++;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n-->0){
            char op = scan.next().charAt(0);
            if(op=='H'){
                int x = scan.nextInt();
                inserthead(x);
            }else if(op=='D'){
                int k = scan.nextInt();
                if(k==0){
                    head = ne[head];
                }else{
                    delete(k-1);
                }
            }else{
                int k = scan.nextInt();
                int x = scan.nextInt();
                insert(x,k-1);
            }
        }
        int i = 0;
        for(i = head;i!=-1;i=ne[i]){
            System.out.print(h[i]+" ");
        }
    }
}

需要注意的是:

1. 我们在插入和删除元素并不是把元素真的删除,而是采取搁置的方法.

2. 对于初始化,一般认为尾节点为-1.如果head的值为-1,则认为这个链表为空.

3. 对于删除操作,ne[k] = ne[ne[k]]的含义是: ne[k]原本存储的是下一个元素的下标,我们需要舍弃这个元素,那么我们就直接找到这个元素的下一个元素的下标(即为ne[ne[k]]),再把ne[k]指向这个下标(ne[ne[k]]);

4. 打印的时候,我们就直接拿到ne数组的值,进行对h数组的遍历即可,其中,当i=-1,即可以说明已经遍历到了尾节点了.

双链表

实现五个操作:

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 k 个插入的数删除；
4. 在第 k 个插入的数左侧插入一个数；
5. 在第 k 个插入的数右侧插入一个数;

实际上可以合并为两个操作:即插入与删除

具体题目:

import java.util.*;
public class Main{
    public static int[] h = new int[100010];
    public static int[] l = new int[100010];
    public static int[] r = new int[100010];
    public static int idx = 0;
// 初始化:使得0为左端点,1为右端点
    public static void init(){
        r[0] = 1;
        l[1] = 0;
        idx = 2;
    }
//在第k个数的右侧插入一个数x
    public static void insert(int x,int k){
        h[idx] = x;
        l[idx] = k;
        r[idx] = r[k];
        l[r[k]] = idx;
        r[k] = idx;
        idx++;
    }
//将第k个数删除
    public static void delete(int k){
        l[r[k]] = l[k];
        r[l[k]] = r[k];
    } 
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        init();
        while(n>0){
            String s = scan.next();
            if(s.equals("R")){
//在最右侧插入一个数,我们规定了1为右端点,所以在右端点的前一个数的右侧插入即可
                int x = scan.nextInt();
                insert(x,l[1]);
            }else if(s.equals("L")){
//在最左侧插入一个数,我们规定了0为左端点,所以在0的右侧插入一个数,即为最左侧.
                int x = scan.nextInt();
                insert(x,0);
            }else if(s.equals("D")){
                int k = scan.nextInt();
                delete(k+1);
            }else if(s.equals("IL")){
//在k的左侧插入一个数等于在k的前一个元素的右边插入一个元素
                int k = scan.nextInt();
                int x = scan.nextInt();
                insert(x,l[k+1]);
            }else if(s.equals("IR")){
                int k = scan.nextInt();
                int x = scan.nextInt();
                insert(x,k+1);
            }
            n--;
        }
        for(int i = r[0];i!=1;i=r[i]){
            System.out.print(h[i]+" ");
        }
    }
}

栈和队列:

栈和队列的概念:
栈: 先进后出

队列: 先进先出

栈:

    public static int[] p = new int[100010];
    public static int idx = 0;
    public static void push(int x){
        p[++idx] = x;
    }
    public static void pop(){
        idx--;
    }
    public static int peek(){
        return p[idx];
    }
    public static boolean empty(){
        return idx==0;
    }

队列:

    public static int[] p = new int[100010];
    public static int idx = 0;
    public static int h = 1;  //队头
    public static void push(int x){
        p[++idx] = x;
    }
    public static void pop(){
        h++;
    }
    public static boolean empty(){
        return h>idx;
    }
    public static int peek(){
        return p[h];
    }

单调栈问题:

一般只用与一种题型:在一个数组集合中找出左边的数中比当前元素小的第一个元素.

具体题型:

import java.util.*;
public class Main{
    public static int[] p = new int[100010];
    public static int idx = 0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n-->0){
            int x = scan.nextInt();
            while(idx!=0&&p[idx]>=x){
                idx--;
            }
            if(idx==0){
                System.out.print("-1 ");
            }else{
                System.out.print(p[idx]+" ");
            }
            p[++idx] = x;
        }
    }
}

滑动窗口问题:

滑动窗口模板:(一般也就用来求滑动窗口的最大或者最小值)

           for(int i = 0;i < n;i++){
            //判断队头是否已经滑出了队尾
           //hh<=tt则证明该窗口目前不为空.
            if(hh<=tt&&i-k+1>q[hh]){
                hh++;
            }
            //检查窗口中的值与目前的arr[i]的关系,不需要这个元素则直接弹出队列
            while(hh<=tt&&check(arr[q[tt],arr[i]){
                tt--;
            }
            q[++tt] = i;
            if(i>=k-1){
               writer.write(arr[q[hh]]+" ");
            }
        }

使用单调队列解决:

import java.util.*;
import java.io.*;
public class Main{
    public static int[] q = new int[1000100];
    public static int tt = 0;
    public static int hh = 0;
    public static void main(String[] args)throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.valueOf(s[0]);
        int k = Integer.valueOf(s[1]);
        int[] arr = new int[1000100];
        s = reader.readLine().split(" ");
        for(int i = 0;i < n;i++){
            arr[i] = Integer.valueOf(s[i]);
        }
        for(int i = 0;i < n;i++){
            //判断队头是否已经滑出了队尾
            if(hh<=tt&&i-k+1>q[hh]){
                hh++;
            }
            //如果窗口中的值大于目前的arr[i],则直接弹出队列
            while(hh<=tt&&arr[q[tt]]>=arr[i]){
                tt--;
            }
            q[++tt] = i;
            if(i>=k-1){
               writer.write(arr[q[hh]]+" ");
            }
        }
        hh=0;
        tt=0;
        writer.write("\n");
        for(int i = 0;i < n;i++){
            //判断队头是否已经滑出了队尾
            if(hh<=tt&&i-k+1>q[hh]){
                hh++;
            }
            //如果窗口中的值大于目前的arr[i],则直接弹出队列
            while(hh<=tt&&arr[q[tt]]<=arr[i]){
                tt--;
            }
            q[++tt] = i;
            if(i>=k-1){
                writer.write(arr[q[hh]]+" ");
            }
        }
        writer.flush();
        reader.close();
        writer.close();
    }
}

KMP算法(匹配字符串)

KMP全称为Knuth Morris Pratt算法，三个单词分别是三个作者的名字。KMP是一种高效的字符串匹配算法，用来在主字符串中查找模式字符串的位置

算法原理:

在两个字符串中,我们希望能判断s1字符串是否为s2的子串.

如果直接采用暴力的思想,时间复杂度为O(n^2);

我们在暴力求解的过程中可以发现,有一部分的判断过程是一样的:

当模式串和主串匹配时，遇到模式串中某个字符不能匹配的情况，对于模式串中已经匹配过的那些字符，如果我们能找到一些规律，将模式串多往后移动几位，而不是像暴力算法算法一样，每次把模式串移动一位，就可以提高算法的效率.

核心:ne数组(存储模拟串队友的各个前嘴后缀的公共元素的最大值.)

// kmp匹配
       for (int i = 1, j = 0; i <= m; i++) {
           while (j != 0 && s[i] != p[j + 1]) {
               j = ne[j]; // s[i] != p[j + 1]即不匹配，则往后移动
           }
           if (s[i] == p[j + 1])
               j++; // 匹配时将j++进行下一个字符得匹配
           if (j == n) { // 匹配了n字符了即代表完全匹配了
               System.out.print(i - n + " ");
               j = ne[j]; // 完全匹配后继续搜索
           }
       }
//求ne[]数组
       for (int i = 2, j = 0; i <= n; i++) {
            //i从2开始，因为prefix[1]肯定为0
            while (j != 0 && p[i] != p[j + 1])
                j = ne[j];
            if (p[i] == p[j + 1])
                j++;
            ne[i] = j;
       }

Tire树

Tire树的应用:更加高效的存储字符串或者数字;

算法原理:

用树形结构来避免大量重复子串的存储,如图所示:

例如插入 abc abdg abcmg

模板:

    public static int[][] son = new int[100010][26];//tire树
    public static int[] cnt = new int[100010];  //标记这个字符串的结尾,为0表示不是结尾,为1则为结尾
    public static int idx = 0;
    //插入
    public static void insert(String s){
        int p = 0;
        for(int i = 0;i < s.length();i++){
            int u = s.charAt(i)-'a';
            if(son[p][u]==0){
                son[p][u] = ++idx;
            }
            p = son[p][u];
        }
        cnt[p]++;
    }
    //查询
    public static int query(String s){
        int p = 0;
        for(int i = 0;i < s.length();i++){
            int u = s.charAt(i)-'a';
            if(son[p][u]==0){
                return 0;
            }
            p = son[p][u];
        }
        return cnt[p];
    }

Tire树的题目应用:

import java.util.*;
public class Main{
    public static int[][] son = new int[3000010][2];
    public static int idx = 0;
    public static void insert(int x){
        int p = 0;
        for(int i = 30;i >= 0;i--){
            int u = (x>>i)&1;
            if(son[p][u]==0){
                son[p][u]=++idx;
            }
            p = son[p][u];
        }
    }
    public static int query(int x){
        int p = 0;
        int res = 0;
        for(int i = 30;i>=0;i--){
            int u = (x>>i)&1;
            if(son[p][1-u]!=0){
                res+=(1<<i);
                p = son[p][1-u];
            }else{
                p = son[p][u];
            }
        }
        return res;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int max = 0;
        int[] arr = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = scan.nextInt();
            insert(arr[i]);
        }
        for(int i = 0;i < n;i++){
            max = Math.max(max,query(arr[i]));
        }
        System.out.println(max);

    }
}

并查集

什么是并查集?

并查集并的是多个集合，查的是元素是否在集合中，并查集主要是解决连通性问题，主要是用于维护连通关系和查询连通关系，但是由于并查集可以根据不同的使用场景进行灵活使用所以没有固定的模板.

简单的并查集模板:

public static int[] p = new int[100010];
public static int idx = 0;
public static int find(int x){
    if(p[x]!=x){
        p[x] = find(p[x]);
    }
    return p[x];
}

find(a)==find(b) //判断a和b在不在同一个集合中
p[find(a)]=find(b)//将a整个集合插入到b的集合中去

维护一个集合中元素个数的数组:

    //维护一个集合中元素个数的数组:
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

维护到祖宗节点的距离:

应用题目:

240. 食物链 - AcWing题库

(3)维护到祖宗节点距离的并查集：
    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
。

堆排序与模拟堆:

堆排序:

import java.util.*;
public class Main{
    public static int[] h = new int[100010];
    public static int size = 0;
   //这里是调整点的下面节点,使得成为一颗优先级队列(排序树)
    public static void down(int u){
        int t = u;
        while(u*2<=size&&h[u*2]<h[t]){
            t = u*2;
        }
        while(u*2+1<=size&&h[u*2+1]<h[t]){
            t = u*2+1;
        }
        if(t!=u){
            int m = h[t];
            h[t] = h[u];
            h[u] = m;
            down(t);
        }
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        for(int i = 1;i <= n;i++){
            h[i] = scan.nextInt();
            size++;
        } 
        //建堆
        for(int i = n/2;i!=0;i--){
            down(i);
        }
        for(int i = 1;i <= m;i++){
            System.out.print(h[1]+" ");
            h[1] = h[size];
            size--;
            down(1);
        }
    }
}

import java.util.*;
public class Main{
    public static int[] h = new int[100010];
    public static int[] ph = new int[100010];
    public static int[] hp = new int[100010];
    public static int size = 0;
    public static void swap(int[] a,int x,int y){
        int m = a[x];
        a[x] = a[y];
        a[y] = m;
    }
    public static void heap_swap(int a,int b){
        swap(ph,hp[a],hp[b]);
        swap(hp,a,b);
        swap(h,a,b);
    }
    public static void down(int u){
        int t = u;
        while(u*2<=size&&h[u*2]<h[t]){
            t = u*2;
        }
        while(u*2+1<=size&&h[u*2+1]<h[t]){
            t = u*2+1;
        }
        if(t!=u){
            heap_swap(u,t);
            down(t);
        }
    }
    public static void up(int u){
        while(u/2>0&&h[u/2]>h[u]){
            heap_swap(u,u/2);
            u = u / 2;
        }
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = 0;//表示第几个插入的数
        while(n-->0){
            String s = scan.next();
            if(s.equals("I")){
                int x = scan.nextInt();
                size++;
                k++;
                ph[k] = size; //第k个插入的数坐标是size
                hp[size] = k;  //目前这个数是第k个数插入的
                h[size] = x;
                up(size);
            }
            if(s.equals("PM")){
                System.out.println(h[1]);
            }
            if(s.equals("DM")){
                heap_swap(1,size);
                size--;
                down(1);
            }
            if(s.equals("D")){
                int m = scan.nextInt();
                m = ph[m];
                heap_swap(m,size);
                size--;
                down(m);
                up(m);
            }
            if(s.equals("C")){
                int m = scan.nextInt();
                int x = scan.nextInt();
                m = ph[m];
                h[m] =x;
                down(m);
                up(m);
            }
        }
    }
}

哈希

模拟哈希表(只介绍开放寻址法)

import java.util.*;
public class Main{
    public static int N = 200003;   //防止死循环
    public static int nul = 0x3f3f3f3f; //避免哈希冲突
    public static int h[] = new int[N];
    public static int find(int x){
        int t = (x%N+N)%N; //使得负数也能存下
        while(h[t]!=nul&&h[t]!=x){
            t++;
            if(t==N){
                t=0;
            }
        }
        return t;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n  = scan.nextInt();
        for(int i = 0;i < N;i++){
            h[i] = nul;
        }
        while(n-->0){
            char s = scan.next().charAt(0);
            if(s=='I'){
                int x = scan.nextInt();
                h[find(x)]=x;
            }
            if(s=='Q'){
                int x = scan.nextInt();
                if(h[find(x)]!=nul){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
    }
}

字符串哈希

可以在O(1)的时间复杂度算出两个字符串是否相等:

import java.util.*;
import java.io.*;
public class Main{
    public static int P = 131;
    public static int N = 100010;
    public static long[] h = new long[N];
    public static long[] p = new long[N];
    public static long get(int l,int r){
        return h[r] - h[l-1]*p[r-l+1];
    }
    public static void main(String[] args)throws IOException{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wri = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = buf.readLine().split(" ");
        int n = Integer.valueOf(s[0]);
        int m = Integer.valueOf(s[1]);
        String str = buf.readLine();
        p[0] = 1;
        for(int i = 1;i <= str.length();i++){
            p[i] = p[i-1]*P;
            h[i] = h[i-1]*P+str.charAt(i-1);
        }
        while(m-->0){
            s = buf.readLine().split(" ");
            int l1 = Integer.valueOf(s[0]);
            int r1 = Integer.valueOf(s[1]);
            int l2 = Integer.valueOf(s[2]);
            int r2 = Integer.valueOf(s[3]);
            if(get(l1,r1)==get(l2,r2)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
        
    }
}

关键的两步:

    //初始的P,N和哈希数组
    public static int P = 131;
    public static int N = 100010;
    public static long[] h = new long[N];
    public static long[] p = new long[N];
    //求得字串哈希
    public static long get(int l,int r){
        return h[r] - h[l-1]*p[r-l+1];
    }
    //构造哈希数组
    p[0] = 1;
    for(int i = 1;i <= str.length();i++){
        p[i] = p[i-1]*P;
        h[i] = h[i-1]*P+str.charAt(i-1);
    }