题目描述

模板题打卡

样例

blablabla

算法1

时间复杂度

参考文献

JAVA 代码

//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Comparator;
import java.util.Collections;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
     public static class DoubleListOfArray{
        public static int N = 100010;
        int[] e;
        int[] l;
        int[] r;
        int head;
        int tail;
        int idx;
        int n;

        public DoubleListOfArray() {
            this(N);
        }

        public DoubleListOfArray(int n) {
            this.n = n + 1;
            init();
        }

        void init() {
            e = new int[n];
            l = new int[n];
            r = new int[n];
            head = 0;
            tail = 1;
            r[head] = tail;
            l[tail] = head;
            idx = 2;
        }

        /**
         * k: 第几个节点的右边插入一个节点
         */
        public void addOnRight(int k, int x) {
            ++k;//第一个节点的下标从2开始的
            r[idx] = r[k];
            l[idx] = k;
            l[r[k]] = idx;
            r[k] = idx ;
            e[idx++] = x;
        }

        /**
         * k: 第几个节点的左边插入一个节点 (就是在k的左节点的右边插入一个节点)
         */
        public void addOnLeft(int k, int x) {
            addOnRight(l[++k] - 1,x);
        }

        public void addToHead(int x) {
            addOnRight(head-1,x);
        }

        public void addToTail(int x) {
            addOnLeft(tail - 1 ,x);
        }

        /**
         * 删除第k个插入的数
         * @param k
         */
        public void remove(int k){
            k++;
            r[l[k]] = r[k];
            l[r[k]] = l[k];
            //模拟节点释放
            l[k]=-1;
            r[k]=-1;
            e[k]=0x80000000;
        }

        public void print(boolean reverse, String delimiter, boolean endLine) {
            if (reverse) {
                for (int i = l[tail]; i != head; i = l[i]) {
                    System.out.print(e[i] + delimiter);
                }
            } else {
                for (int i = r[head]; i != tail; i = r[i]) {
                    System.out.print(e[i] + delimiter);
                }
            }
            if (endLine) System.out.println();
        }

        public String getDesc() {
            return "数组模拟双链表";
        }
    }

    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        DoubleListOfArray list = new DoubleListOfArray();
        int m = sc.nextInt();
        while(m-->0){
            String op = sc.next();
            if("L".equals(op)){
                list.addToHead(sc.nextInt());
            }else if("R".equals(op)){
                list.addToTail(sc.nextInt());
            }else if("D".equals(op)){
                list.remove(sc.nextInt());
            }else if("IL".equals(op)){
                list.addOnLeft(sc.nextInt(),sc.nextInt());
            }else if("IR".equals(op)){
                list.addOnRight(sc.nextInt(),sc.nextInt());
            }
        }
        list.print(false," ",false);
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla