数据结构整理 顶

public interface Array<T> {
    T[] getData();
    int getSize();
    int getCapacity();
    boolean isEmpty();
    void addLast(T t);
    void addFirst(T t);
    void add(int index, T t);
    T get(int index);
    T getLast();
    T getFirst();
    void set(int index, T t);
    boolean contains(T t);
    int find(T t);
    void removeElement(T t);
    T remove(int index);
    T removeFirst();
    T removeLast();

    /**
     * 交换两个索引的元素的位置
     * @param i
     * @param j
     */
    void swap(int i,int j);
}

public class DefaultArray<T> implements Array<T> {
    private static final int factor = 2;
    private T[] data;
    private int size;

    @SuppressWarnings("unchecked")
    public DefaultArray(int capacity) {
        data = (T[]) new Object[capacity];
        size = 0;
    }

    public DefaultArray() {
        this(20);
    }

    @SuppressWarnings("unchecked")
    public DefaultArray(T[] data) {
        this.data = (T[]) new Object[data.length + 1];
        for (int i = 0;i < data.length;i++) {
            this.data[i] = data[i];
        }
        this.size = data.length;
    }

    @Override
    public T[] getData() {
        return data;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public int getCapacity() {
        return data.length;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void addLast(T value) {
        add(size,value);
    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void add(int index,T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加失败，要求index >=0且index<=size");
        }
        for (int i = size;i > index;i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        size++;
        if (size == data.length) {
            resize(getCapacity() * factor);
        }
    }

    @Override
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("获取失败，index参数错误");
        }
        return data[index];
    }

    @Override
    public T getLast() {
        return get(size - 1);
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public void set(int index,T value) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("设置失败，index参数错误");
        }
        data[index] = value;
    }

    @Override
    public boolean contains(T value) {
        for (int i = 0;i < size;i++) {
            if (data[i].equals(value)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int find(T value) {
        for (int i = 0;i < size;i++) {
            if (data[i].equals(value)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public void removeElement(T value) {
        int index = find(value);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("移除失败，index参数错误");
        }
        T ret = data[index];
        for (int i = index;i < size;i++) {
            data[i] = data[i + 1];
        }
        size--;
        if (size <= getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / factor);
        }
        return ret;
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        return remove(size - 1);
    }

    @Override
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("索引非法");
        }
        T temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    @SuppressWarnings("unchecked")
    private void resize(int capacity) {
        if (capacity == size) {
            capacity++;
        }
        T[] newData = (T[]) new Object[capacity];
        for (int i = 0;i < size;i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("DefaultArray(data=[");
        for (int i = 0;i < size - 1;i++) {
            builder.append(data[i] + ",");
        }
        builder.append(data[size -1] + "], size=" + size);
        return builder.toString();
    }
}

public class ArrayMain {
    public static void main(String[] args) {
        Array<Integer> array = new DefaultArray<>(3);
        array.addLast(66);
        array.addLast(99);
        array.addLast(88);
        System.out.println(array);
        array.add(1,77);
        array.addFirst(100);
        array.set(4,11);
        array.remove(2);
        System.out.println(array);
        System.out.println(array.get(3));
        array.remove(1);
        array.removeFirst();
        array.removeFirst();
        System.out.println(array);
    }
}

@FunctionalInterface
public interface On {
    int compute(Integer[] nums);
}

public class SumOn {
    public int sum(Array<Integer> array,On on) {
        return on.compute(array.getData());
    }
}

public class Main {
    public static void main(String[] args) {
        Array<Integer> array = new DefaultArray<>(new Integer[]{1,2,3,4,5,6,7});
        SumOn sumOn = new SumOn();
        int sum = sumOn.sum(array, nums ->
                Stream.of(nums).reduce((x, y) -> x + y).get());
        System.out.println(sum);
    }
}

public interface Stack<T> {
    /**
     * 入栈
     * @param t
     */
    void push(T t);

    /**
     * 出栈
     * @return
     */
    T pop();

    /**
     * 获取栈顶元素
     * @return
     */
    T peek();
    int getSize();
    boolean isEmpty();
}

@ToString
public class ArrayStack<T> implements Stack<T> {
    private Array<T> array;

    public ArrayStack(int capacity) {
        array = new DefaultArray<>(capacity);
    }

    public ArrayStack() {
        array = new DefaultArray<>();
    }

    @Override
    public void push(T value) {
        array.addLast(value);
    }

    @Override
    public T pop() {
        return array.removeLast();
    }

    @Override
    public T peek() {
        return array.getLast();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    public int getCapacity() {
        return array.getCapacity();
    }
}

public class StackMain {
    public static void main(String[] args) {
        Stack<Integer> stack = new ArrayStack<>(5);
        for (int i = 0;i < 5;i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

public class JavaSolution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0;i < s.length();i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') {
                    return false;
                }
                if (c == ']' && topChar != '[') {
                    return false;
                }
                if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        JavaSolution solution = new JavaSolution();
        String patten = "{}[()]";
        System.out.println(solution.isValid(patten));
    }
}

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new ArrayStack<>();
        for (int i = 0;i < s.length();i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') {
                    return false;
                }
                if (c == ']' && topChar != '[') {
                    return false;
                }
                if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String patten = "{[()]}";
        boolean valid = solution.isValid(patten);
        System.out.println(valid);
    }
}

public interface Queue<T> {
    /**
     * 入队
     * @param t
     */
    void enqueue(T t);

    /**
     * 出队
     * @return
     */
    T dequeue();

    /**
     * 获取队首元素
     * @return
     */
    T getFront();
    int getSize();
    boolean isEmpty();
}

@ToString
public class ArrayQueue<T> implements Queue<T> {
    private Array<T> array;

    public ArrayQueue(int capacity) {
        array = new DefaultArray<>(capacity);
    }

    public ArrayQueue() {
        array = new DefaultArray<>();
    }

    @Override
    public void enqueue(T value) {
        array.addLast(value);
    }

    @Override
    public T dequeue() {
        return array.removeFirst();
    }

    @Override
    public T getFront() {
        return array.getFirst();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    public int getCapaticy() {
        return array.getCapacity();
    }
}

public class QueueMain {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayQueue<>(10);
        for (int i = 0;i < 10;i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

public class LoopQueue<T> implements Queue<T> {
    private T[] data;
    /**
     * 循环队列队首
     */
    private int front;
    /**
     * 循环队列队尾
     */
    private int tail;
    /**
     * 循环队列成员数量
     */
    private int size;
    /**
     * 扩容因子
     */
    private static final int factor = 2;

    @SuppressWarnings("unchecked")
    public LoopQueue(int capacity) {
        data = (T[]) new Object[capacity + 1];
        front = tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(20);
    }

    public int getCapacity() {
        return data.length - 1;
    }

    @Override
    public void enqueue(T value) {
        //判断队列是否已满
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * factor);
        }
        data[tail] = value;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("无法从空队列出队");
        }
        T ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size <= getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / factor);
        }
        return ret;
    }

    @Override
    public T getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @SuppressWarnings("unchecked")
    private void resize(int capacity) {
        T[] newData = (T[]) new Object[capacity + 1];
        for (int i = 0;i < size;i++) {
            //将老数组的元素放入新数组时，将重新将0定位新数组的front
            newData[i] = data[(front + i) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("LoopQueue{data=[");
        for (int i = 0;i < size - 1;i++) {
            builder.append(data[(front + i) % data.length] + ",");
        }
        builder.append(data[(tail - 1) % data.length] + "], size=" + size);
        return builder.toString();
    }
}

public class QueueMain {
    public static void main(String[] args) {
        Queue<Integer> queue = new LoopQueue<>(7);
        for (int i = 0;i <= 10;i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

public class TestQueueMain {
    private static double testQueue(Queue<Integer> q,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 100000;
        Queue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue,opCount);
        System.out.println("ArrayQueue,time: " + time1 + " s");

        Queue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue,opCount);
        System.out.println("LoopQueue,time: " + time2 + " s");
    }
}

public interface List<T> {
    int getSize();
    boolean isEmpty();
    void addFirst(T t);
    void add(int index,T t);
    void addLast(T t);
    T get(int index);
    T getFirst();
    T getLast();
    void set(int index,T t);
    boolean contains(T t);
    T remove(int index);
    T removeFirst();
    T removeLast();
    void removeElement(T t);
}

public class LinkedList<T> implements List<T> {
    @AllArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node next;

        public Node(T element) {
            this(element,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    /**
     * 链表虚拟头节点
     */
    private Node dummyHead;
    private int size;

    public LinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(int index,T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加错误，非法索引");
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.getNext();
        }
        prev.setNext(new Node(value, prev.getNext()));
        size++;

    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void addLast(T value) {
        add(size,value);
    }

    @Override
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("获取错误，非法索引");
        }
        Node cur = dummyHead.getNext();
        for (int i = 0;i < index;i++) {
            cur = cur.getNext();
        }
        return cur.getElement();
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public T getLast() {
        return get(size - 1);
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("设置错误，非法索引");
        }
        Node cur = dummyHead.getNext();
        for (int i = 0;i < index;i++) {
            cur = cur.getNext();
        }
        cur.setElement(value);
    }

    @Override
    public boolean contains(T value) {
        Node cur = dummyHead.getNext();
        while (cur != null) {
            if (cur.getElement().equals(value)) {
                return true;
            }
            cur = cur.getNext();
        }
        return false;
    }

    @Override
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("删除错误，非法索引");
        }
        Node prev = dummyHead;
        for (int i = 0;i < index;i++) {
            prev = prev.getNext();
        }
        Node retNode = prev.getNext();
        prev.setNext(retNode.getNext());
        retNode.setNext(null);
        size--;
        return retNode.getElement();
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        return remove(size - 1);
    }

    @Override
    public void removeElement(T value) {
        Node pre = dummyHead;
        while (pre.getNext() != null) {
            if (value.equals(pre.getNext().getElement())) {
                Node delNode = pre.getNext();
                pre.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                break;
            }
            pre = pre.getNext();
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.getNext();
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL");
        return builder.toString();
    }
}

public class ListMain {
    public static void main(String[] args) {
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0;i < 5;i++) {
            linkedList.add(i,i);
            System.out.println(linkedList);
        }
        linkedList.add(3,666);
        System.out.println(linkedList);

        linkedList.addLast(777);
        System.out.println(linkedList);

        linkedList.set(4,888);
        System.out.println(linkedList);

        System.out.println(linkedList.get(5));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.contains(3));

        linkedList.removeLast();
        System.out.println(linkedList);

        linkedList.remove(4);
        System.out.println(linkedList);

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
        linkedList.removeElement(2);
        System.out.println(linkedList);
        System.out.println(linkedList.getLast());
    }
}

@ToString
public class LinkedListStack<T> implements Stack<T> {
    private List<T> list;

    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public void push(T value) {
        list.addFirst(value);
    }

    @Override
    public T pop() {
        return list.removeFirst();
    }

    @Override
    public T peek() {
        return list.getFirst();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
}

public class StackMain {
    public static void main(String[] args) {
        Stack<Integer> stack = new LinkedListStack<>();
        for (int i = 0;i < 5;i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
}

public class TestStackMain {
    private static double testStack(Stack<Integer> stack,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            stack.push(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            stack.pop();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 10000000;
        Stack<Integer> arrayStack = new ArrayStack<>();
        double time1 = testStack(arrayStack,opCount);
        System.out.println("ArrayStack,time: " + time1 + " s");

        Stack<Integer> linkedListStack = new LinkedListStack<>();
        double time2 = testStack(linkedListStack,opCount);
        System.out.println("LinkedListStack,time: " + time2 + " s");
    }
}

public class LinkedListQueue<T> implements Queue<T> {
    @AllArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node next;

        public Node(T element) {
            this(element,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    /**
     * 队列头节点
     */
    private Node head;
    /**
     * 队列尾节点
     */
    private Node tail;
    /**
     * 队列元素个数
     */
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public void enqueue(T value) {
        //当整个队列为空的时候
        if (tail == null) {
            tail = new Node(value);
            head = tail;
        }else { //从尾部入队
            tail.setNext(new Node(value));
            tail = tail.getNext();
        }
        size++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("无法从空队列出队");
        }
        //从头部出队
        Node retNode = head;
        head = head.getNext();
        retNode.setNext(null);
        if (head == null) {
            tail = null;
        }
        size--;
        return retNode.getElement();
    }

    @Override
    public T getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return head.getElement();
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Queue: front ");
        Node cur = head;
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL tail");
        return builder.toString();
    }
}

public class QueueMain {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedListQueue<>();
        for (int i = 0;i <= 10;i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

public class TestQueueMain {
    private static double testQueue(Queue<Integer> q,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 100000;
        Queue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue,opCount);
        System.out.println("ArrayQueue,time: " + time1 + " s");

        Queue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue,opCount);
        System.out.println("LoopQueue,time: " + time2 + " s");

        Queue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue,opCount);
        System.out.println("LinkedListQueue,time: " + time3 + " s");
    }
}

public class TestQueueMain {
    private static double testQueue(Queue<Integer> q,int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0;i < opCount;i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0;i < opCount;i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int opCount = 10000000;
//        Queue<Integer> arrayQueue = new ArrayQueue<>();
//        double time1 = testQueue(arrayQueue,opCount);
//        System.out.println("ArrayQueue,time: " + time1 + " s");

        Queue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue,opCount);
        System.out.println("LoopQueue,time: " + time2 + " s");

        Queue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue,opCount);
        System.out.println("LinkedListQueue,time: " + time3 + " s");
    }
}

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //移除所有可能值为val的头部节点
        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        if (head == null) {
            return null;
        }
        //移除所有可能值为val的中间节点
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }
        return head;
    }
}

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //建立虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //移除所有可能值为val的中间节点
        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }
}

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        val = x;
    }

    /**
     * 通过一个数组转化成一个链表
     * @param arr
     */
    public ListNode(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1;i < arr.length;i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            builder.append(cur.val + "->");
            cur = cur.next;
        }
        builder.append("NULL");
        return builder.toString();
    }
}

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //建立虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //移除所有可能值为val的中间节点
        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6);
        System.out.println(listNode);
    }
}

public class Sum {
    private static int sum(int[] arr) {
        return sum(arr,0);
    }

    private static int sum(int[] arr,int l) {
        //求解最基本的问题
        if (l == arr.length) {
            return 0;
        }
        //把原问题转化成更小的问题
        return arr[l] + sum(arr,l + 1);
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        System.out.println(sum(arr));
    }
}

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //求解最基本的问题
        if (head == null) {
            return null;
        }
        //把原问题转化成更小的问题
        //此时把链表拆分成头节点+一个不包含头节点的链表
        ListNode node = removeElements(head.next, val);
        //拼接头节点
        if (head.val == val) {
            return node;
        }else {
            head.next = node;
            return head;
        }
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6);
        System.out.println(listNode);
    }
}

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //求解最基本的问题
        if (head == null) {
            return null;
        }
        //把原问题转化成更小的问题
        //此时把链表拆分成头节点+一个不包含头节点的链表
        head.next = removeElements(head.next, val);
        //是否拼接头节点
        return head.val == val?head.next : head;
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6);
        System.out.println(listNode);
    }
}

public class Solution {
    public ListNode removeElements(ListNode head, int val,int depth) {
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println("调用: 删除 " + val + "在 " + head + "中");
        //求解最基本的问题
        if (head == null) {
            System.out.print(depthString);
            System.out.println("返回:" + head);
            return null;
        }
        //把原问题转化成更小的问题
        //此时把链表拆分成头节点+一个不包含头节点的链表
        ListNode node = removeElements(head.next, val,depth + 1);
        System.out.print(depthString);
        System.out.println("删除 " + val + "之后: " + node);
        //是否拼接头节点
        ListNode ret;
        if (head.val == val) {
            ret = node;
        }else {
            head.next = node;
            ret = head;
        }
        System.out.print(depthString);
        System.out.println("返回: " + ret);
        return ret;
    }

    private String generateDepthString(int depth) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < depth;i++) {
            builder.append("--");
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        int[] values = {1,2,6,3,4,5,6};
        ListNode node = new ListNode(values);
        System.out.println(node);
        Solution solution = new Solution();
        ListNode listNode = solution.removeElements(node, 6,0);
        System.out.println(listNode);
    }
}

public class RecursiveLinkedList<T> implements List<T> {
    @AllArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node next;

        public Node(T element) {
            this(element,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    /**
     * 链表虚拟头节点
     */
    private Node dummyHead;
    private int size;

    public RecursiveLinkedList() {
        dummyHead = new Node();
        size = 0;
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void add(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加错误，非法索引");
        }
        dummyHead = add(-1,index,dummyHead,value);
    }

    private Node add(int i,int index,Node node,T value) {
        if (i == index - 1) {
            size++;
            node.setNext(new Node(value,node.getNext()));
            return node;
        }
        node.setNext(add(i + 1,index,node.getNext(),value));
        return node;
    }

    @Override
    public void addLast(T value) {
        add(size,value);
    }

    @Override
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("查找错误，非法索引");
        }
        return get(0,index,dummyHead.getNext());
    }

    private T get(int i,int index,Node node) {
        if (i == index) {
            return node.getElement();
        }
        return get(i + 1,index,node.getNext());
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public T getLast() {
        return get(size - 1);
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("更新错误，非法索引");
        }
        set(0,index,dummyHead.getNext(),value);
    }

    private void set(int i,int index,Node node,T value) {
        if (i == index) {
            node.setElement(value);
            return;
        }
        set(i + 1,index,node.getNext(),value);
    }

    @Override
    public boolean contains(T value) {
        return contains(dummyHead.getNext(),value);
    }

    private boolean contains(Node node,T value) {
        if (node == null) {
            return false;
        }
        if (node.getElement().equals(value)) {
            return true;
        }
        return contains(node.getNext(),value);

    }

    @Override
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("删除错误，非法索引");
        }
        return remove(-1,index,dummyHead).getElement();
    }

    private Node remove(int i,int index,Node node) {
        if (i == index - 1) {
            Node ret = node.getNext();
            node.setNext(ret.getNext());
            ret.setNext(null);
            size--;
            return ret;
        }
        return remove(i + 1,index,node.getNext());
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        return remove(size - 1);
    }

    @Override
    public void removeElement(T value) {
        dummyHead = removeElement(dummyHead,value);
    }

    private Node removeElement(Node node,T value) {
        if (node.getNext() == null) {
            return null;
        }
        else {
            if (value.equals(node.getNext().getElement())) {
                Node delNode = node.getNext();
                node.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                return node;
            }
        }
        node.setNext(removeElement(node.getNext(),value));
        return node;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.getNext();
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL");
        return builder.toString();
    }
}

public class ListMain {
    public static void main(String[] args) {
        List<Integer> linkedList = new RecursiveLinkedList<>();
        for (int i = 0;i < 5;i++) {
            linkedList.add(i,i);
            System.out.println(linkedList);
        }
        linkedList.add(3,666);
        System.out.println(linkedList);

        linkedList.addLast(777);
        System.out.println(linkedList);

        linkedList.set(4,888);
        System.out.println(linkedList);

        System.out.println(linkedList.get(5));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.contains(3));

        linkedList.removeLast();
        System.out.println(linkedList);

        linkedList.remove(4);
        System.out.println(linkedList);

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
        linkedList.removeElement(2);
        System.out.println(linkedList);
        System.out.println(linkedList.getLast());
    }
}

public class MutualLinkedList<T> implements List<T> {
    @AllArgsConstructor
    @NoArgsConstructor
    @Data
    private class Node {
        private T element;
        private Node prev;
        private Node next;

        public Node(T element) {
            this(element,null,null);
        }

        @Override
        public String toString() {
            return element.toString();
        }
    }

    private Node dummyHead;
    private Node tail;
    private int size;

    public MutualLinkedList() {
        dummyHead = new Node();
        tail = null;
        size = 0;
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void addFirst(T value) {
        add(0,value);
    }

    @Override
    public void add(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("添加错误，非法索引");
        }
        if (index <= size / 2 + 1) {
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.getNext();
            }
            Node node = new Node(value,prev,prev.getNext());
            if (prev.getNext() != null) {
                prev.getNext().setPrev(node);
            }else {
                tail = node;
            }
            prev.setNext(node);
        }else {
            if (index == size) {
                addLast(value);
                return;
            } else {
                Node cur = tail;
                for (int i = size; i > index + 1; i--) {
                    cur = cur.getPrev();
                }
                Node node = new Node(value, cur.getPrev(), cur);
                cur.getPrev().setNext(node);
                cur.setPrev(node);
            }
        }
        size++;
    }

    @Override
    public void addLast(T value) {
        Node node = new Node(value,tail,tail.getNext());
        tail.setNext(node);
        tail = node;
        size++;
    }

    @Override
    public T get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("获取错误，非法索引");
        }
        if (index <= size / 2) {
            Node cur = dummyHead.getNext();
            for (int i = 0;i < index;i++) {
                cur = cur.getNext();
            }
            return cur.getElement();
        }else {
            Node cur = tail;
            for (int i = size;i > index + 1;i--) {
                cur = cur.getPrev();
            }
            return cur.getElement();
        }
    }

    @Override
    public T getFirst() {
        return get(0);
    }

    @Override
    public T getLast() {
        return tail.getElement();
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("设置错误，非法索引");
        }
        if (index <= size / 2) {
            Node cur = dummyHead.getNext();
            for (int i = 0;i < index;i++) {
                cur = cur.getNext();
            }
            cur.setElement(value);
        }else {
            Node cur = tail;
            for (int i = size;i > index + 1;i--) {
                cur = cur.getPrev();
            }
            cur.setElement(value);
        }
    }

    @Override
    public boolean contains(T value) {
        Node cur = dummyHead.getNext();
        while (cur != null) {
            if (cur.getElement().equals(value)) {
                return true;
            }
            cur = cur.getNext();
        }
        return false;
    }

    @Override
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("删除错误，非法索引");
        }
        if (index <= size / 2) {
            Node prev = dummyHead;
            for (int i = 0;i < index;i++) {
                prev = prev.getNext();
            }
            Node ret = prev.getNext();
            prev.setNext(ret.getNext());
            ret.getNext().setPrev(prev);
            ret.setNext(null);
            ret.setPrev(null);
            size--;
            return ret.getElement();
        }else {
            Node cur = tail;
            for (int i = size;i > index + 1;i--) {
                cur = cur.getPrev();
            }
            cur.getPrev().setNext(cur.getNext());
            if (cur.getNext() != null) {
                cur.getNext().setPrev(cur.getPrev());
            }else {
                tail = cur.getPrev();
            }
            cur.setPrev(null);
            cur.setNext(null);
            size--;
            return cur.getElement();
        }
    }

    @Override
    public T removeFirst() {
        return remove(0);
    }

    @Override
    public T removeLast() {
        Node node = tail;
        tail = tail.getPrev();
        tail.setNext(null);
        node.setPrev(null);
        size--;
        return node.getElement();
    }

    @Override
    public void removeElement(T value) {
        Node pre = dummyHead;
        while (pre.getNext() != null) {
            if (value.equals(pre.getNext().getElement())) {
                Node delNode = pre.getNext();
                pre.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                break;
            }
            pre = pre.getNext();
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node cur = dummyHead.getNext();
        while (cur != null) {
            builder.append(cur + "->");
            cur = cur.getNext();
        }
        builder.append("NULL");
        return builder.toString();
    }
}

public class ListMain {
    public static void main(String[] args) {
        List<Integer> linkedList = new MutualLinkedList<>();
        for (int i = 0;i < 5;i++) {
            linkedList.add(i,i);
            System.out.println(linkedList);
        }
        linkedList.add(3,666);
        System.out.println(linkedList);

        linkedList.addLast(777);
        System.out.println(linkedList);

        linkedList.set(4,888);
        System.out.println(linkedList);

        System.out.println(linkedList.get(5));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.contains(3));

        linkedList.removeLast();
        System.out.println(linkedList);

        linkedList.remove(4);
        System.out.println(linkedList);

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
        linkedList.removeElement(2);
        System.out.println(linkedList);
        System.out.println(linkedList.getLast());
    }
}

public interface Tree<T> {
    int getSize();
    boolean isEmpty();
    void add(T t);
    boolean contains(T t);

    /**
     * 前序遍历
     */
    void preOrder();

    /**
     * 中序遍历
     */
    void inOrder();

    /**
     * 后序遍历
     */
    void postOrder();

    /**
     * 层序遍历，又称广度遍历
     * 而前、中、后序遍历又称深度遍历
     */
    void levelOrder();

    /**
     * 查找最小元素
     * @return
     */
    T minimum();

    /**
     * 查找最大元素
     * @return
     */
    T maximum();

    /**
     * 删除最小元素
     * @return
     */
    T removeMin();

    /**
     * 删除最大元素
     * @return
     */
    T removeMax();

    /**
     * 删除任意节点
     * @return
     */
    void remove(T t);

    /**
     * 找出比t小的最大值
     * @param t
     * @return
     */
    T floor(T t);

    /**
     * 找出比t大的最小值
     * @param t
     * @return
     */
    T ceil(T t);
}

public class BST<T extends Comparable<T>> implements Tree<T> {
    @AllArgsConstructor
    @Data
    private class Node{
        private T element;
        private Node left;
        private Node right;

        public Node(T element) {
            this(element,null,null);
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(T value) {
        root = add(root,value);
    }

    private Node add(Node node,T value) {
        //递归终止条件
        if (node == null) {
            size++;
            return new Node(value);
        }
        //递归
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(add(node.getLeft(),value));
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(add(node.getRight(),value));
        }
        return node;
    }

    @Override
    public boolean contains(T value) {
        return contains(root,value);
    }

    private boolean contains(Node node,T value) {
        if (node == null) {
            return false;
        }
        if (value.compareTo(node.getElement()) == 0) {
            return true;
        }else if (value.compareTo(node.getElement()) < 0) {
            return contains(node.getLeft(),value);
        }else {
            return contains(node.getRight(),value);
        }
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.println(node.getElement());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    /**
     * 非递归前序遍历
     */
    public void preOrderNR() {
        Stack<Node> stack = new ArrayStack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.getElement());
            if (cur.getRight() != null) {
                stack.push(cur.getRight());
            }
            if (cur.getLeft() != null) {
                stack.push(cur.getLeft());
            }
        }
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.getLeft());
        System.out.println(node.getElement());
        inOrder(node.getRight());
    }

    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.println(node.getElement());
    }

    @Override
    public void levelOrder() {
        Queue<Node> queue = new LoopQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node cur = queue.dequeue();
            System.out.println(cur.getElement());

            if (cur.getLeft() != null) {
                queue.enqueue(cur.getLeft());
            }
            if (cur.getRight() != null) {
                queue.enqueue(cur.getRight());
            }
        }
    }

    @Override
    public T minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return minimum(root).getElement();
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    @Override
    public T maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return maximum(root).getElement();
    }

    private Node maximum(Node node) {
        if (node.getRight() == null) {
            return node;
        }
        return maximum(node.getRight());
    }

    @Override
    public T removeMin() {
        T ret = minimum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node) {
        //递归的终止条件，当节点的左子树为空时，递归达到最大深度
        if (node.getLeft() == null) {
            //保存最终节点的右子树
            Node rightNode = node.getRight();
            //将最终节点分离
            node.setRight(null);
            size--;
            //将保存的右子树拼接回最终节点的父节点
            return rightNode;
        }
        //从根节点开始不断向左子树递归，并逐层返回删除后的子节点重新
        //设为上层节点的左节点
        node.setLeft(removeMin(node.getLeft()));
        return node;
    }

    @Override
    public T removeMax() {
        T ret = maximum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        if (node.getRight() == null) {
            Node leftNode = node.getLeft();
            node.setLeft(null);
            size--;
            return leftNode;
        }

        node.setRight(removeMax(node.getRight()));
        return node;
    }

    @Override
    public void remove(T value) {
        root = remove(root,value);
    }

    private Node remove(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(remove(node.getLeft(),value));
            return node;
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(remove(node.getRight(),value));
            return node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                return rightNode;
            }
            //待删除节点右子树为空的情况
            if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                return leftNode;
            }
            //待删除节点左右子树均不为空的情况
            //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.getRight());
            successor.setRight(removeMin(node.getRight()));
            successor.setLeft(node.getLeft());
            node.setLeft(null);
            node.setRight(null);
            return successor;
            //找到比待删除节点小的最大节点，即待删除节点左子树的最大节点
            //用这个节点顶替待删除节点的位置,此二种方法取其一即可
//            Node predecessor = maximum(node.getLeft());
//            predecessor.setLeft(removeMax(node.getLeft()));
//            predecessor.setRight(node.getRight());
//            node.setLeft(null);
//            node.setRight(null);
//            return predecessor;
        }
    }

    @Override
    public T floor(T value) {
        Node node = floor(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node floor(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) <= 0) {
            return floor(node.getLeft(),value);
        }else {
            if (node.getRight() == null) {
                return node;
            }else if (node.getRight().getLeft() == null &&
                    value.compareTo(node.getRight().getElement()) <= 0) {
                return node;
            }else if (node.getRight().getRight() == null &&
                    value.compareTo(node.getRight().getElement()) > 0) {
                return node.getRight();
            }
            return floor(node.getRight(),value);
        }
    }

    @Override
    public T ceil(T value) {
        Node node = ceil(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node ceil(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) >= 0) {
            return ceil(node.getRight(),value);
        }else {
            if (node.getLeft() == null) {
                return node;
            }else if (value.compareTo(maximum(node.getLeft()).getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getRight() == null &&
                    value.compareTo(node.getLeft().getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getLeft() == null &&
                    value.compareTo(node.getLeft().getElement()) < 0) {
                return node.getLeft();
            }
            return ceil(node.getLeft(),value);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        generateBSTString(root,0,builder);
        return builder.toString();
    }

    private void generateBSTString(Node node,int depth,StringBuilder builder) {
        if (node == null) {
            builder.append(generateDepthString(depth) + "null\n");
            return;
        }
        builder.append(generateDepthString(depth) + node.getElement() + "\n");
        generateBSTString(node.getLeft(),depth + 1,builder);
        generateBSTString(node.getRight(),depth + 1,builder);
    }

    private String generateDepthString(int depth) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < depth;i++) {
            builder.append("--");
        }
        return builder.toString();
    }
}

public class TreeMain {
    public static void main(String[] args) {
        Tree<Integer> bst = new BST<>();
        Integer[] nums = {50,30,60,80,40,20};
        Stream.of(nums).forEach(bst::add);
        System.out.println("递归前序遍历");
        bst.preOrder();
        System.out.println("非递归前序遍历");
        ((BST)bst).preOrderNR();
        ///////////////////////////////
        //            50              //
        //           / \             //
        //          30  60            //
        //         / \   \           //
        //        20  40  80          //
        ///////////////////////////////
        System.out.println("中序遍历");
        bst.inOrder();
        System.out.println("后续遍历");
        bst.postOrder();
        System.out.println("层序遍历");
        bst.levelOrder();
        System.out.println();
        System.out.println(bst);
        System.out.println(bst.floor(35));
        System.out.println(bst.ceil(45));
        System.out.println();
        bst.remove(30);
        System.out.println(bst);
    }
}

public class TreeMain1 {
    public static void main(String[] args) {
        Tree<Integer> bst = new BST<>();
        Random random = new Random();
        for (int i = 0;i < 1000;i++) {
            bst.add(random.nextInt(10000));
        }
        Array<Integer> numsMin = new DefaultArray<>();
        while (!bst.isEmpty()) {
            numsMin.addLast(bst.removeMin());
        }
        System.out.println(numsMin);
        for (int i = 1;i < numsMin.getSize();i++) {
            if (numsMin.get(i - 1) > numsMin.get(i)) {
                throw new IllegalArgumentException("错误");
            }
        }
        System.out.println("removeMin测试成功");

        for (int i = 0;i < 1000;i++) {
            bst.add(random.nextInt(10000));
        }
        Array<Integer> numsMax = new DefaultArray<>();
        while (!bst.isEmpty()) {
            numsMax.addLast(bst.removeMax());
        }
        System.out.println(numsMax);
        for (int i = 1;i < numsMax.getSize();i++) {
            if (numsMax.get(i - 1) < numsMax.get(i)) {
                throw new IllegalArgumentException("错误");
            }
        }
        System.out.println("removeMax测试成功");
    }
}

public interface Set<T> {
    void add(T t);
    void remove(T t);
    boolean contains(T t);
    int getSize();
    boolean isEmpty();
}

public class BSTSet<T extends Comparable<T>> implements Set<T> {
    private Tree<T> bst;

    public BSTSet() {
        bst = new BST<>();
    }
    @Override
    public void add(T value) {
        bst.add(value);
    }

    @Override
    public void remove(T value) {
        bst.remove(value);
    }

    @Override
    public boolean contains(T value) {
        return bst.contains(value);
    }

    @Override
    public int getSize() {
        return bst.getSize();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }
}

public class FileOperation {
    /**
     * 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中
     * @param filename
     * @param words
     * @return
     */
    public static boolean readFile(String filename, Array<String> words) {
        if (filename == null || words == null) {
            System.out.println("filename为空或words为空");
            return false;
        }
        Scanner scanner;

        try {
            File file = new File(filename);
            if (file.exists()) {
                FileInputStream fis = new FileInputStream(file);
                scanner = new Scanner(new BufferedInputStream(fis),"UTF-8");
                scanner.useLocale(Locale.ENGLISH);
            }else {
                return false;
            }
        } catch (FileNotFoundException e) {
            System.out.println("无法打开" + filename);
            return false;
        }
        //简单分词
        if (scanner.hasNextLine()) {
            String contents = scanner.useDelimiter("\\A").next();
            int start = firstCharacterIndex(contents,0);
            for (int i = start + 1;i <= contents.length();) {
                if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
                    String word = contents.substring(start,i).toLowerCase();
                    words.addLast(word);
                    start = firstCharacterIndex(contents,i);
                    i = start + 1;
                }else {
                    i++;
                }
            }
        }
        return true;

    }

    private static int firstCharacterIndex(String s,int start) {
        for (int i = start;i < s.length();i++) {
            if (Character.isLetter(s.charAt(i))) {
                return i;
            }
        }
        return s.length();
    }
}

public class SetMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Set<String> set = new BSTSet<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(set::add);
        System.out.println("共有不同的单词: " + set.getSize());
    }
}

public class LinkedListSet<T> implements Set<T> {
    private List<T> list;

    public LinkedListSet() {
        list = new LinkedList<>();
    }
    @Override
    public void add(T value) {
        if (!list.contains(value)) {
            list.addFirst(value);
        }
    }

    @Override
    public void remove(T value) {
        list.removeElement(value);
    }

    @Override
    public boolean contains(T value) {
        return list.contains(value);
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }
}

public class SetMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Set<String> set = new LinkedListSet<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(set::add);
        System.out.println("共有不同的单词: " + set.getSize());
    }
}

public class TestSetMain {
    private static double testSet(Set<String> set,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        if (FileOperation.readFile(filename,words)) {
            System.out.println("共有单词: " + words.getSize());
            Stream.of(words.getData()).filter(data -> data != null)
                    .forEach(set::add);
            System.out.println("共有不同单词: " + set.getSize());
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Set<String> bstSet = new BSTSet<>();
        double time1 = testSet(bstSet,filename);
        System.out.println("BST Set: " + time1 + " s");
        System.out.println();
        Set<String> linkedListSet = new LinkedListSet<>();
        double time2 = testSet(linkedListSet,filename);
        System.out.println("LinkedList Set: " + time2 + " s");
    }
}

                          log n                           n

public class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        Set<String> set = new TreeSet<>();
        Stream.of(words).forEach(word -> {
            StringBuilder builder = new StringBuilder();
            for (int i = 0;i < word.length();i++) {
                builder.append(codes[word.charAt(i) - 'a']);
            }
            set.add(builder.toString());
        });
        return set.size();
    }
}

public interface Map<K,V> {
    void add(K key,V value);
    V remove(K key);
    boolean contains(K key);
    V get(K key);
    void set(K key,V value);
    int getSize();
    boolean isEmpty();
}

public class LinkedListMap<K,V> implements Map<K,V> {
    @AllArgsConstructor
    @Data
    @NoArgsConstructor
    private class Node {
        private K key;
        private V value;
        private Node next;

        public Node(K key) {
            this(key,null,null);
        }

        public Node(K key,V value) {
            this(key,value,null);
        }

        @Override
        public String toString() {
            return key.toString() + " : " + value.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        dummyHead = new Node();
        size = 0;
    }

    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            dummyHead.setNext(new Node(key,value,dummyHead.getNext()));
            size++;
        }else {
            node.setValue(value);
        }
    }

    @Override
    public V remove(K key) {
        Node pre = dummyHead;
        while (pre.getNext() != null) {
            if (key.equals(pre.getNext().getKey())) {
                Node delNode = pre.getNext();
                pre.setNext(delNode.getNext());
                delNode.setNext(null);
                size--;
                return delNode.getValue();
            }
            pre = pre.getNext();
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node == null ? null : node.getValue();
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            throw new IllegalArgumentException(key + "不存在");
        }
        node.setValue(value);
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private Node getNode(K key) {
        Node cur = dummyHead.getNext();
        while (cur != null) {
            if (key.equals(cur.getKey())) {
                return cur;
            }
            cur = cur.getNext();
        }
        return null;
    }
}

public class MapMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Map<String,Integer> map = new LinkedListMap<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
    }
}

public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> {
    @Data
    @AllArgsConstructor
    private class Node{
        private K key;
        private V value;
        private Node left;
        private Node right;

        public Node(K key) {
            this(key,null,null,null);
        }
        public Node(K key,V value) {
            this(key,value,null,null);
        }
    }

    private Node root;
    private int size;

    public BSTMap() {
        root = null;
        size = 0;
    }
    @Override
    public void add(K key, V value) {
        root = add(root,key,value);
    }

    private Node add(Node node, K key,V value) {
        //递归终止条件
        if (node == null) {
            size++;
            return new Node(key,value);
        }
        //递归
        if (key.compareTo(node.getKey()) < 0) {
            node.setLeft(add(node.getLeft(),key,value));
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(add(node.getRight(),key,value));
        }else {
            node.setValue(value);
        }
        return node;
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root,key);
        if (node != null) {
            root = remove(root,key);
            return node.getValue();
        }
        return null;
    }

    private Node remove(Node node,K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.getKey()) < 0) {
            node.setLeft(remove(node.getLeft(),key));
            return node;
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(remove(node.getRight(),key));
            return node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                return rightNode;
            }
            //待删除节点右子树为空的情况
            if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                return leftNode;
            }
            //待删除节点左右子树均不为空的情况
            //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.getRight());
            successor.setRight(removeMin(node.getRight()));
            successor.setLeft(node.getLeft());
            node.setLeft(null);
            node.setRight(null);
            return successor;
        }
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    private Node removeMin(Node node) {
        if (node.getLeft() == null) {
            Node rightNode = node.getRight();
            node.setRight(null);
            size--;
            return rightNode;
        }
        node.setLeft(removeMin(node.getLeft()));
        return node;
    }

    @Override
    public boolean contains(K key) {
        return getNode(root,key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(root,key);
        return node == null ? null : node.getValue();
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(root,key);
        if (node == null) {
            throw new IllegalArgumentException(key + "不存在");
        }
        node.setValue(value);
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private Node getNode(Node node,K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.getKey()) == 0) {
            return node;
        }else if (key.compareTo(node.getKey()) < 0) {
            return getNode(node.getLeft(),key);
        }else {
            return getNode(node.getRight(),key);
        }
    }
}

public class MapMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Map<String,Integer> map = new BSTMap<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
    }
}

public class TestMapMain {
    private static double testMap(Map<String,Integer> map,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile(filename,words);
        System.out.println("共有单词: " + words.getSize());
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Map<String,Integer> bstMap = new BSTMap<>();
        double time1 = testMap(bstMap,filename);
        System.out.println("BST Map: " + time1 + " s");

        Map<String,Integer> linkedListMap = new LinkedListMap<>();
        double time2 = testMap(linkedListMap,filename);
        System.out.println("LinkedList Map: " + time2 + " s");
    }
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new TreeSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        List<Integer> list = new ArrayList<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                list.add(num);
                set.remove(num);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0;i < list.size();i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new TreeMap<>();
        for (int num : nums1) {
            if (map.putIfAbsent(num,1) != null) {
                map.put(num,map.get(num) + 1);
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int num : nums2) {
            if (map.containsKey(num)) {
                list.add(num);
                map.put(num,map.get(num) - 1);
                if (map.get(num) == 0) {
                    map.remove(num);
                }
            }
        }
        int[] ret = new int[list.size()];
        for (int i = 0;i < list.size();i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}

public interface Heap<T> {
    int getSize();
    boolean isEmpty();
    void add(T t);

    /**
     * 取出最大元素(最大堆)或最小元素(最小堆)
     * @return
     */
    T extract();

    /**
     * 查看最大元素(最大堆)或最小元素(最小堆)
     * @return
     */
    T findHeap();

    /**
     * 取出堆中最大元素(最大堆)或最小元素(最小堆)
     * 并且替换成元素t
     * @param t
     * @return
     */
    T replace(T t);
}

public class MaxHeap<T extends Comparable<T>> implements Heap<T> {
    private Array<T> data;

    public MaxHeap(int capacity) {
        data = new DefaultArray<>(capacity);
    }

    public MaxHeap() {
        data = new DefaultArray<>();
    }

    /**
     * 将任意一个数组转化成最大堆,此种方式称为Heapify
     * 过程为先找到非叶节点的最后一个节点，依次向根节点遍历，
     * 将每一个节点浮动下沉，即可完成任意数组向最大堆的转化
     * 找最后一个非叶节点的方法即为找到最后一个叶节点(数组的最后一个索引size-1)
     * 的父节点
     * 将n个元素逐一插入到一个空堆中，时间复杂度为O(nlog n)
     * heapify的过程，时间复杂度为O(n)
     * @param arr
     */
    public MaxHeap(T[] arr) {
        data = new DefaultArray<>(arr);
        for (int i = parent(getSize() - 1);i >= 0;i--) {
            siftDown(i);
        }
    }

    @Override
    public int getSize() {
        return data.getSize();
    }

    @Override
    public boolean isEmpty() {
        return data.isEmpty();
    }

    @Override
    public void add(T value) {
        data.addLast(value);
        siftUp(data.getSize() - 1);
    }

    /**
     * 堆节点浮动上移
     * @param index
     */
    private void siftUp(int index) {
        while (index > 0 &&
                data.get(parent(index)).compareTo(data.get(index)) < 0) {
            data.swap(index,parent(index));
            index = parent(index);
        }
    }

    @Override
    public T extract() {
        T ret = findHeap();
        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    /**
     * 堆节点浮动下沉
     * @param index
     */
    private void siftDown(int index) {
        while (leftChild(index) < data.getSize()) {
            int j = leftChild(index);
            if (j + 1 < data.getSize() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChile(index);
            }
            //data[j]是左右孩子的最大值
            if (data.get(index).compareTo(data.get(j)) >= 0) {
                break;
            }
            data.swap(index,j);
            index = j;
        }
    }

    @Override
    public T findHeap() {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空，不能做此操作");
        }
        return data.get(0);
    }

    @Override
    public T replace(T value) {
        T ret = findHeap();
        data.set(0,value);
        siftDown(0);
        return ret;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
     * @param index
     * @return
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("索引0没有父节点");
        }
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
     * @param index
     * @return
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
     * @param index
     * @return
     */
    private int rightChile(int index) {
        return index * 2 + 2;
    }
}

public class HeapMain {
    public static void main(String[] args) {
        int n = 1000000;
        Heap<Integer> maxHeap = new MaxHeap<>();
        Random random = new Random();
        for (int i = 0;i < n;i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }
        int[] arr = new int[n];
        for (int i = 0;i < n;i++) {
            arr[i] = maxHeap.extract();
        }
        for (int i = 1;i < n;i++) {
            if (arr[i - 1] < arr[i]) {
                throw new IllegalArgumentException("出错");
            }
        }
        System.out.println("测试最大堆完成");
    }
}

public class TestHeapMain {
    private static double testHeap(Integer[] testData,boolean isHeapify) {
        long startTime = System.nanoTime();
        Heap<Integer> maxHeap;
        if (isHeapify) {
            maxHeap = new MaxHeap<>(testData);
        }else {
            maxHeap = new MaxHeap<>();
            Stream.of(testData).forEach(maxHeap::add);
        }
        int[] arr = new int[testData.length];
        for (int i = 0;i < testData.length;i++) {
            arr[i] = maxHeap.extract();
        }
        for (int i = 1;i < testData.length;i++) {
            if (arr[i - 1] < arr[i]) {
                throw new IllegalArgumentException("错误");
            }
        }
        System.out.println("测试最大堆成功");
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int n = 1000000;
        Random random = new Random();
        Integer[] testData = new Integer[n];
        for (int i = 0;i < n;i++) {
            testData[i] = random.nextInt(Integer.MAX_VALUE);
        }
        double time1 = testHeap(testData,false);
        System.out.println("不使用heapify: " + time1 + " s");
        System.out.println();
        double time2 = testHeap(testData,true);
        System.out.println("使用heapify: " + time2 + " s");
    }
}

public class PriorityQueue<T extends Comparable<T>> implements Queue<T> {
    private Heap<T> heap;

    public PriorityQueue() {
        heap = new MaxHeap<>();
    }

    @Override
    public void enqueue(T value) {
        heap.add(value);
    }

    @Override
    public T dequeue() {
        return heap.extract();
    }

    @Override
    public T getFront() {
        return heap.findHeap();
    }

    @Override
    public int getSize() {
        return heap.getSize();
    }

    @Override
    public boolean isEmpty() {
        return heap.isEmpty();
    }
}

class Solution {
    /**
     * 频次
     */
    private class Freq implements Comparable<Freq> {
        private int e;
        private int freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        public int getE() {
            return e;
        }

        public void setE(int e) {
            this.e = e;
        }

        public int getFreq() {
            return freq;
        }

        public void setFreq(int freq) {
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq o) {
            if (this.freq < o.freq) {
                return -1;
            }else if (this.freq > o.freq) {
                return 1;
            }else {
                return 0;
            }
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new TreeMap<>();
        for (int num : nums) {
            if (map.putIfAbsent(num,1) != null) {
                map.put(num,map.get(num) + 1);
            }
        }
        Queue<Freq> pq = new PriorityQueue<>();
        map.keySet().stream().forEach(key -> {
            if (pq.size() < k) {
                pq.add(new Freq(key,map.get(key)));
            }else if (map.get(key) > pq.peek().getFreq()) {
                pq.poll();
                pq.add(new Freq(key,map.get(key)));
            }
        });
        List<Integer> res = new LinkedList<>();
        while (!pq.isEmpty()) {
            res.add(pq.poll().getE());
        }
        return res;
    }
}

public interface SegmentTree<T> {
    T get(int index);
    int getSize();

    /**
     * 返回区间[queryL,queryR]的值
     * @param queryL
     * @param queryR
     * @return
     */
    T query(int queryL,int queryR);
    void set(int index,T t);
}

public class DefaultSegmentTree<T> implements SegmentTree<T> {
    /**
     * 区间元素
     */
    private T[] data;
    /**
     * 线段树
     */
    private T[] tree;
    /**
     * 函数式接口，继承于BiFunction，用做线段树规则(求和，求最大，最小等等)
     */
    private BinaryOperator<T> merger;

    @SuppressWarnings("unchecked")
    public DefaultSegmentTree(T[] data,BinaryOperator<T> merger) {
        this.merger = merger;
        this.data = (T[]) new Object[data.length];
        for (int i = 0;i < data.length;i++) {
            this.data[i] = data[i];
        }
        tree = (T[]) new Object[data.length * 4];
        buildSegmentTree(0,0,data.length - 1);
    }

    /**
     * 在treeIndex的位置创建表示区间[l...r]的线段树
     * @param treeIndex 根节点的索引
     * @param l 区间左边界
     * @param r 区间右边界
     */
    private void buildSegmentTree(int treeIndex,int l,int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChile(treeIndex);
        int mid = l + (r - l) / 2;
        buildSegmentTree(leftTreeIndex,l,mid);
        buildSegmentTree(rightTreeIndex,mid + 1,r);
        tree[treeIndex] = merger.apply(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    @Override
    public T get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("索引非法");
        }
        return data[index];
    }

    @Override
    public int getSize() {
        return data.length;
    }

    @Override
    public T query(int queryL, int queryR) {
        if (queryL < 0 || queryL >= data.length
                || queryR < 0 || queryR >= data.length || queryL > queryR) {
            throw new IllegalArgumentException("索引非法");
        }
        return query(0,0,data.length - 1,queryL,queryR);
    }

    /**
     * 在以treeID为根的线段树中[l...r]的范围里，搜索区间[queryL...queryR]的值
     * @param treeIndex 根节点的索引
     * @param l 区间的左边界
     * @param r 区间的右边界
     * @param queryL 查询的左边界
     * @param queryR 查询的右边界
     * @return
     */
    private T query(int treeIndex,int l,int r,int queryL,int queryR) {
        if (l == queryL && r == queryR) {
            return tree[treeIndex];
        }
        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChile(treeIndex);
        if (queryL >= mid + 1) {
            return query(rightTreeIndex,mid + 1,r,queryL,queryR);
        }else if (queryR <= mid) {
            return query(leftTreeIndex,l,mid,queryL,queryR);
        }
        T leftResult = query(leftTreeIndex, l, mid, queryL, mid);
        T rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
        return merger.apply(leftResult,rightResult);
    }

    @Override
    public void set(int index, T value) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("索引非法");
        }
        data[index] = value;
        set(0,0,data.length - 1,index,value);
    }

    /**
     * 在以treeIndex为根的线段树中更新index的值为value
     * @param treeIndex
     * @param l
     * @param r
     * @param index
     * @param value
     */
    private void set(int treeIndex,int l,int r,int index,T value) {
        if (l == r) {
            tree[treeIndex] = value;
            return;
        }
        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChile(treeIndex);
        if (index >= mid + 1) {
            set(rightTreeIndex,mid + 1,r,index,value);
        }else {
            set(leftTreeIndex,l,mid,index,value);
        }
        tree[treeIndex] = merger.apply(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
     * @param index
     * @return
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
     * @param index
     * @return
     */
    private int rightChile(int index) {
        return index * 2 + 2;
    }

    @Override
    public String toString() {
        return "DefaultSegmentTree{" +
                "tree=" + Arrays.toString(tree) +
                '}';
    }
}

public class SegmentTreeMain {
    public static void main(String[] args) {
        Integer[] nums = {-2,0,3,-5,2,-1};
        SegmentTree<Integer> segmentTree = new DefaultSegmentTree<>(nums,(x,y) -> x + y);
        System.out.println(segmentTree);
        System.out.println(segmentTree.query(0,2));
        segmentTree.set(3,5);
        System.out.println(segmentTree);
        System.out.println(segmentTree.query(1,4));
    }
}

class NumArray {
    private SegmentTree<Integer> segmentTree;

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            Integer[] data = new Integer[nums.length];
            for (int i = 0;i < nums.length;i++) {
                data[i] = nums[i];
            }
            segmentTree = new DefaultSegmentTree<>(data,(x, y) -> x + y);
        }
    }

    public int sumRange(int i, int j) {
        if (segmentTree == null) {
            throw new IllegalArgumentException("线段树为空");
        }
        return segmentTree.query(i,j);
    }
}

class NumArray {
    //预处理，sum[i]存储前i个元素和，sum[0] = 0
    //sum[i]存储nums[0...i-1]的和
    private int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        sum[0] = 0;
        for (int i = 1;i < sum.length;i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

class NumArray {
    private SegmentTree<Integer> segmentTree;

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            Integer[] data = new Integer[nums.length];
            for (int i = 0;i < nums.length;i++) {
                data[i] = nums[i];
            }
            segmentTree = new DefaultSegmentTree<>(data,(x,y) -> x + y);
        }
    }

    public void update(int i, int val) {
        if (segmentTree == null) {
            throw new IllegalArgumentException("线段树为空");
        }
        segmentTree.set(i,val);
    }

    public int sumRange(int i, int j) {
        if (segmentTree == null) {
            throw new IllegalArgumentException("线段树为空");
        }
        return segmentTree.query(i,j);
    }
}

public interface Trie {
    int getSize();
    void add(String word);
    boolean contains(String word);
    boolean isEmpty();
    boolean isPrefix(String prefix);
    void remove(String word);
}

public class DefaultTrie implements Trie {
    @Data
    private class Node {
        //单词节点的末尾
        private Boolean word;
        private Map<Character,Node> next;

        public Node(boolean word) {
            this.word = word;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }
    }

    private Node root;
    private int size;

    public DefaultTrie() {
        root = new Node();
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void add(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        if (!cur.getWord()) {
            cur.setWord(true);
            size++;
        }
    }

    @Override
    public boolean contains(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return cur.getWord();
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isPrefix(String prefix) {
        Node cur = root;
        for (int i = 0;i < prefix.length();i++) {
            char c = prefix.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return true;
    }

    @Override
    public void remove(String word) {
        if (contains(word)) {
            remove(word,word.length() - 1);
         }
    }

    private void remove(String word,int index) {
        if (index + 1 == word.length()) {
            Node node = get(word,index);
            char c = word.charAt(index);
            if (node.getNext().size() == 1 && mapIsEmpty(node.getNext().get(c).getNext())) {
                node.setNext(null);
            }else if (node.getNext().size() == 1 && node.getNext().get(c).getWord()) {
                node.getNext().get(c).setWord(false);
                size--;
                return;
            }else {
                node.getNext().remove(c);
                size--;
                return;
            }
            word = word.substring(0,word.length() - 1);
        }
        remove(word,index - 1);
    }

    private Node get(String word,int index) {
        Node cur = root;
        for (int i = 0;i < index;i++) {
            char c = word.charAt(i);
            cur = cur.getNext().get(c);
        }
        return cur;
    }

    private boolean mapIsEmpty(Map<?, ?> map) {
        return map == null || map.isEmpty();
    }

    @Override
    public String toString() {
        return "DefaultTrie{" +
                "root=" + root +
                ", size=" + size +
                '}';
    }
}

public class TrieMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Trie trie = new DefaultTrie();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(trie::add);
        System.out.println("共有不同的单词: " + trie.getSize());
    }
}

public class TrieRemoveMain {
    public static void main(String[] args) {
        Trie trie = new DefaultTrie();
        trie.add("adfatr");
        trie.add("adfadhy");;
        trie.add("adfasd");
        trie.remove("adfadhy");
        System.out.println(trie);
    }
}

class Trie {
    private class Node {
        //单词节点的末尾
        private Boolean word;
        private Map<Character,Node> next;

        public Node(boolean word) {
            this.word = word;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }

        public Boolean getWord() {
            return word;
        }

        public void setWord(Boolean word) {
            this.word = word;
        }

        public Map<Character, Node> getNext() {
            return next;
        }

        public void setNext(Map<Character, Node> next) {
            this.next = next;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        if (!cur.getWord()) {
            cur.setWord(true);
        }
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return cur.getWord();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node cur = root;
        for (int i = 0;i < prefix.length();i++) {
            char c = prefix.charAt(i);
            if (cur.getNext().get(c) == null) {
                return false;
            }
            cur = cur.getNext().get(c);
        }
        return true;
    }
}

class WordDictionary {
    private class Node {
        //单词节点的末尾
        private Boolean word;
        private Map<Character,Node> next;

        public Node(boolean word) {
            this.word = word;
            next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }

        public Boolean getWord() {
            return word;
        }

        public void setWord(Boolean word) {
            this.word = word;
        }

        public Map<Character, Node> getNext() {
            return next;
        }

        public void setNext(Map<Character, Node> next) {
            this.next = next;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        Node cur = root;
        for (int i = 0;i < word.length();i++) {
            char c = word.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        if (!cur.getWord()) {
            cur.setWord(true);
        }
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return match(root,word,0);
    }

    private boolean match(Node node,String word,int index) {
        if (index == word.length()) {
            return node.getWord();
        }
        char c = word.charAt(index);
        if (c != '.') {
            if (node.getNext().get(c) == null) {
                return false;
            }
            return match(node.getNext().get(c),word,index + 1);
        }else {
            //遍历所有的字符节点，进行递归
            for (char nextChar : node.getNext().keySet()) {
                if (match(node.getNext().get(nextChar),word,index + 1)) {
                    return true;
                }
            }
            return false;
        }
    }
}

class MapSum {
    private class Node {
        private int value;
        private Map<Character,Node> next;

        public Node(int value) {
            this.value = value;
            next = new TreeMap<>();
        }

        public Node() {
            this(0);
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Map<Character, Node> getNext() {
            return next;
        }

        public void setNext(Map<Character, Node> next) {
            this.next = next;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public MapSum() {
        root = new Node();
    }

    public void insert(String key, int val) {
        Node cur = root;
        for (int i = 0;i < key.length();i++) {
            char c = key.charAt(i);
            cur.getNext().putIfAbsent(c,new Node());
            cur = cur.getNext().get(c);
        }
        cur.setValue(val);
    }

    public int sum(String prefix) {
        Node cur = root;
        for (int i = 0;i < prefix.length();i++) {
            char c = prefix.charAt(i);
            if (cur.getNext().get(c) == null) {
                return 0;
            }
            cur = cur.getNext().get(c);
        }
        return sum(cur);
    }

    private int sum(Node node) {
        int ret = node.getValue();
        for (char c : node.getNext().keySet()) {
            ret += sum(node.getNext().get(c));
        }
        return ret;
    }
}

public interface UnionFind {
    int getSize();

    /**
     * 查看元素p和元素q是否所属同一个集合
     * @param p
     * @param q
     * @return
     */
    boolean isConnected(int p,int q);

    /**
     * 合并元素p和元素q所属的集合
     * @param p
     * @param q
     */
    void unionElements(int p,int q);
}

public class ArrayUnionFind implements UnionFind {
    //该数组的索引，我们称为元素的编号
    //该数组的值，我们称之为元素所属不同集合的编号
    //如果不同索引的值相同，则表示不同的元素属于同一个集合
    private int[] id;

    public ArrayUnionFind(int size) {
        id = new int[size];
        for (int i = 0;i < id.length;i++) {
            id[i] = i;
        }
    }

    /**
     * 查找元素p所对应的集合编号
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= id.length) {
            throw new IllegalArgumentException("p越界");
        }
        return id[p];
    }

    @Override
    public int getSize() {
        return id.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID) {
            return;
        }
        for (int i = 0;i < id.length;i++) {
            if (id[i] == pID) {
                id[i] = qID;
            }
        }
    }
}

public class TreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时，表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素
    private int[] parent;

    public TreeUnionFind(int size) {
        parent = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
        }
    }

    /**
     * 不断向上查找元素的根节点，直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        parent[pRoot] = qRoot;
    }
}

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 1000000;
        int m = 10000;
        UnionFind arrayUnionFind = new ArrayUnionFind(size);
        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind treeUnionFind = new TreeUnionFind(size);
        System.out.println("treeUnionFind : " + testUF(treeUnionFind,m) + " s");
    }
}

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 100000;
        int m = 100000;
        UnionFind arrayUnionFind = new ArrayUnionFind(size);
        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind treeUnionFind = new TreeUnionFind(size);
        System.out.println("treeUnionFind : " + testUF(treeUnionFind,m) + " s");
    }
}

public class SizeTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时，表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素
    private int[] parent;
    //sz[i]表示以i为根的集合中元素个数
    private int[] sz;

    public SizeTreeUnionFind(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点，直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的元素个数不同判断合并方向
        //将元素个数少的集合合并到元素个数多的集合上，降低树的高度
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 100000;
        int m = 100000;
        UnionFind arrayUnionFind = new ArrayUnionFind(size);
        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size);
        System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s");
    }
}

public class RankTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时，表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素
    private int[] parent;
    //rank[i]表示以i为根的集合所表示的树的层数
    private int[] rank;

    public RankTreeUnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点，直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }
}

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 10000000;
        int m = 10000000;
//        UnionFind arrayUnionFind = new ArrayUnionFind(size);
//        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size);
        System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s");

        UnionFind rankTreeUnionFind = new RankTreeUnionFind(size);
        System.out.println("rankTreeUnionFind : " + testUF(rankTreeUnionFind,m) + " s");
    }
}

public class SizeTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时，表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素
    private int[] parent;
    //sz[i]表示以i为根的集合中元素个数
    private int[] sz;

    public SizeTreeUnionFind(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点，直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的元素个数不同判断合并方向
        //将元素个数少的集合合并到元素个数多的集合上，降低树的高度
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}

public class RankTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时，表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素
    private int[] parent;
    //rank[i]表示以i为根的集合所表示的树的层数
    private int[] rank;

    public RankTreeUnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点，直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }
}

public class RecursiveRankTreeUnionFind implements UnionFind {
    //该数组表示每个元素为一个向上指向自己指针的树
    //当数组的值与索引相等时，表示自己指向自己
    //当数组元素的值发生变动为其他元素的索引时，表示向上指针指向其他元素
    private int[] parent;
    //rank[i]表示以i为根的集合所表示的树的层数
    private int[] rank;

    public RecursiveRankTreeUnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0;i < parent.length;i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 不断向上查找元素的根节点，直到找到根节点
     * O(h)复杂度,h为树的高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p越界");
        }
        if (p != parent[p]) {
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //根据两个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
    }
}

public class TestUnionFindMain {
    private static double testUF(UnionFind uf,int m) {
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i = 0;i < m;i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        int size = 10000000;
        int m = 10000000;
//        UnionFind arrayUnionFind = new ArrayUnionFind(size);
//        System.out.println("arrayUnionFind : " + testUF(arrayUnionFind,m) + " s");

        UnionFind sizeTreeUnionFind = new SizeTreeUnionFind(size);
        System.out.println("sizeTreeUnionFind : " + testUF(sizeTreeUnionFind,m) + " s");

        UnionFind rankTreeUnionFind = new RankTreeUnionFind(size);
        System.out.println("rankTreeUnionFind : " + testUF(rankTreeUnionFind,m) + " s");

        UnionFind recursiveRankTreeUnionFind = new RecursiveRankTreeUnionFind(size);
        System.out.println("recursiveRankTreeUnionFind : " + testUF(recursiveRankTreeUnionFind,m) + " s");
    }
}

public class AVLTree<T extends Comparable<T>> implements Tree<T> {
    @Data
    @AllArgsConstructor
    private class Node{
        private T element;
        private Node left;
        private Node right;
        //节点的高度，在节点的左右子树增加、删除节点时需要维护该节点的高度
        private int height;

        public Node(T element) {
            this(element,null,null,1);
        }
    }

    private Node root;
    private int size;

    public AVLTree() {
        root = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.getHeight();
    }

    /**
     * 获得节点node的平衡因子(左右子树的高度差)
     * @param node
     * @return
     */
    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.getLeft()) - getHeight(node.getRight());
    }

    /**
     * 判断该二叉树是否是一颗二分搜索树
     * @return
     */
    public boolean isBST() {
        Array<T> elements = new DefaultArray<>();
        inOrder(root,elements);
        for (int i = 1;i < elements.getSize();i++) {
            if (elements.get(i - 1).compareTo(elements.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断该二叉树是否是一颗平衡二叉树
     * @return
     */
    public boolean isBalanced() {
        return isBalanced(root);
    }

    private boolean isBalanced(Node node) {
        if (node == null) {
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }
        return isBalanced(node.getLeft()) && isBalanced(node.getRight());
    }

    /**
     * 对节点node进行右旋转操作，返回旋转后新的根节点(原node的左节点)
     * @param node
     * @return
     */
    private Node rightRotate(Node node) {
        Node ret = node.getLeft();
        Node rightRet = ret.getRight();
        //向右旋转的过程
        ret.setRight(node);
        node.setLeft(rightRet);
        //更新height
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);

        return ret;
    }

    /**
     * 对节点node进行左旋转操作，返回旋转后新的根节点(原node的右节点)
     * @param node
     * @return
     */
    private Node leftRotate(Node node) {
        Node ret = node.getRight();
        Node leftRet = ret.getLeft();
        //向左旋转的过程
        ret.setLeft(node);
        node.setRight(leftRet);
        //更新height
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);

        return ret;
    }

    @Override
    public void add(T value) {
        root = add(root,value);
    }

    private Node add(Node node,T value) {
        //递归终止条件
        if (node == null) {
            size++;
            return new Node(value);
        }
        //递归
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(add(node.getLeft(),value));
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(add(node.getRight(),value));
        }
        return service(node);
    }

    @Override
    public boolean contains(T value) {
        return contains(root,value);
    }

    private boolean contains(Node node,T value) {
        if (node == null) {
            return false;
        }
        if (value.compareTo(node.getElement()) == 0) {
            return true;
        }else if (value.compareTo(node.getElement()) < 0) {
            return contains(node.getLeft(),value);
        }else {
            return contains(node.getRight(),value);
        }
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.println(node.getElement());
        preOrder(node.getLeft());
        preOrder(node.getRight());
    }

    /**
     * 非递归前序遍历
     */
    public void preOrderNR() {
        Stack<Node> stack = new ArrayStack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.getElement());
            if (cur.getRight() != null) {
                stack.push(cur.getRight());
            }
            if (cur.getLeft() != null) {
                stack.push(cur.getLeft());
            }
        }
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.getLeft());
        System.out.println(node.getElement());
        inOrder(node.getRight());
    }

    private void inOrder(Node node,Array<T> elements) {
        if (node == null) {
            return;
        }
        inOrder(node.getLeft(),elements);
        elements.addLast(node.getElement());
        inOrder(node.getRight(),elements);
    }

    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.println(node.getElement());
    }

    @Override
    public void levelOrder() {
        Queue<Node> queue = new LoopQueue<>();
        queue.enqueue(root);
        while (!queue.isEmpty()) {
            Node cur = queue.dequeue();
            System.out.println(cur.getElement());

            if (cur.getLeft() != null) {
                queue.enqueue(cur.getLeft());
            }
            if (cur.getRight() != null) {
                queue.enqueue(cur.getRight());
            }
        }
    }

    @Override
    public T minimum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return minimum(root).getElement();
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    @Override
    public T maximum() {
        if (size == 0) {
            throw new IllegalArgumentException("二分搜索树为空");
        }
        return maximum(root).getElement();
    }

    private Node maximum(Node node) {
        if (node.getRight() == null) {
            return node;
        }
        return maximum(node.getRight());
    }

    @Override
    public T removeMin() {
        T ret = minimum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node) {
        //递归的终止条件，当节点的左子树为空时，递归达到最大深度
        if (node.getLeft() == null) {
            //保存最终节点的右子树
            Node rightNode = node.getRight();
            //将最终节点分离
            node.setRight(null);
            size--;
            //将保存的右子树拼接回最终节点的父节点
            return rightNode;
        }
        //从根节点开始不断向左子树递归，并逐层返回删除后的子节点重新
        //设为上层节点的左节点
        node.setLeft(removeMin(node.getLeft()));
        return service(node);
    }

    @Override
    public T removeMax() {
        T ret = maximum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        if (node.getRight() == null) {
            Node leftNode = node.getLeft();
            node.setLeft(null);
            size--;
            return leftNode;
        }

        node.setRight(removeMax(node.getRight()));
        return service(node);
    }

    @Override
    public void remove(T value) {
        root = remove(root,value);
    }

    private Node remove(Node node,T value) {
        if (node == null) {
            return null;
        }
        Node retNode;
        if (value.compareTo(node.getElement()) < 0) {
            node.setLeft(remove(node.getLeft(),value));
            retNode = node;
        }else if (value.compareTo(node.getElement()) > 0) {
            node.setRight(remove(node.getRight(),value));
            retNode = node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                retNode = rightNode;
            }
            //待删除节点右子树为空的情况
            else if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                retNode = leftNode;
            }else {
                //待删除节点左右子树均不为空的情况
                //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node successor = minimum(node.getRight());
                successor.setRight(removeMin(node.getRight()));
                successor.setLeft(node.getLeft());
                node.setLeft(null);
                node.setRight(null);
                retNode = successor;
                //找到比待删除节点小的最大节点，即待删除节点左子树的最大节点
                //用这个节点顶替待删除节点的位置,此二种方法取其一即可
//            Node predecessor = maximum(node.getLeft());
//            predecessor.setLeft(removeMax(node.getLeft()));
//            predecessor.setRight(node.getRight());
//            node.setLeft(null);
//            node.setRight(null);
//            return predecessor;
            }
        }
        if (retNode == null) {
            return null;
        }
        return service(retNode);
    }

    /**
     * 维护节点平衡
     * @param node
     * @return
     */
    private Node service(Node node) {
        //更新height
        node.setHeight(1 + Math.max(getHeight(node.getLeft()),getHeight(node.getRight())));
        //计算平衡因子
        int balanceFactor = getBalanceFactor(node);

        //平衡维护
        //LL
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) >= 0) {
            return rightRotate(node);
        }
        //RR
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) <= 0) {
            return leftRotate(node);
        }
        //LR
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) < 0) {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }
        //RL
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) > 0) {
            node.setRight(rightRotate(node.getRight()));
            return leftRotate(node);
        }
        return node;
    }

    @Override
    public T floor(T value) {
        Node node = floor(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node floor(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) <= 0) {
            return floor(node.getLeft(),value);
        }else {
            if (node.getRight() == null) {
                return node;
            }else if (node.getRight().getLeft() == null &&
                    value.compareTo(node.getRight().getElement()) <= 0) {
                return node;
            }else if (node.getRight().getRight() == null &&
                    value.compareTo(node.getRight().getElement()) > 0) {
                return node.getRight();
            }
            return floor(node.getRight(),value);
        }
    }

    @Override
    public T ceil(T value) {
        Node node = ceil(root,value);
        if (node != null) {
            return node.getElement();
        }
        return null;
    }

    private Node ceil(Node node,T value) {
        if (node == null) {
            return null;
        }
        if (value.compareTo(node.getElement()) >= 0) {
            return ceil(node.getRight(),value);
        }else {
            if (node.getLeft() == null) {
                return node;
            }else if (value.compareTo(maximum(node.getLeft()).getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getRight() == null &&
                    value.compareTo(node.getLeft().getElement()) >= 0) {
                return node;
            }else if (node.getLeft().getLeft() == null &&
                    value.compareTo(node.getLeft().getElement()) < 0) {
                return node.getLeft();
            }
            return ceil(node.getLeft(),value);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        generateBSTString(root,0,builder);
        return builder.toString();
    }

    private void generateBSTString(Node node,int depth,StringBuilder builder) {
        if (node == null) {
            builder.append(generateDepthString(depth) + "null\n");
            return;
        }
        builder.append(generateDepthString(depth) + node.getElement() + "\n");
        generateBSTString(node.getLeft(),depth + 1,builder);
        generateBSTString(node.getRight(),depth + 1,builder);
    }

    private String generateDepthString(int depth) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0;i < depth;i++) {
            builder.append("--");
        }
        return builder.toString();
    }
}

public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V> {
    @Data
    @AllArgsConstructor
    private class Node{
        private K key;
        private V value;
        private Node left;
        private Node right;
        private int height;

        public Node(K key) {
            this(key,null,null,null,1);
        }
        public Node(K key,V value) {
            this(key,value,null,null,1);
        }
    }

    private Node root;
    private int size;

    public AVLTreeMap() {
        root = null;
        size = 0;
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.getHeight();
    }

    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.getLeft()) - getHeight(node.getRight());
    }

    private Node rightRotate(Node node) {
        Node ret = node.getLeft();
        Node retRight = ret.getRight();
        ret.setRight(node);
        node.setLeft(retRight);
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);
        return ret;
    }

    private Node leftRotate(Node node) {
        Node ret = node.getRight();
        Node retLeft = ret.getLeft();
        ret.setLeft(node);
        node.setRight(retLeft);
        node.setHeight(Math.max(getHeight(node.getLeft()),getHeight(node.getRight())) + 1);
        ret.setHeight(Math.max(getHeight(ret.getLeft()),getHeight(ret.getRight())) + 1);
        return ret;
    }

    @Override
    public void add(K key, V value) {
        root = add(root,key,value);
    }

    private Node add(Node node, K key, V value) {
        //递归终止条件
        if (node == null) {
            size++;
            return new Node(key,value);
        }
        //递归
        if (key.compareTo(node.getKey()) < 0) {
            node.setLeft(add(node.getLeft(),key,value));
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(add(node.getRight(),key,value));
        }else {
            node.setValue(value);
        }
        return service(node);
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root,key);
        if (node != null) {
            root = remove(root,key);
            return node.getValue();
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }
        Node retNode;
        if (key.compareTo(node.getKey()) < 0) {
            node.setLeft(remove(node.getLeft(),key));
            retNode = node;
        }else if (key.compareTo(node.getKey()) > 0) {
            node.setRight(remove(node.getRight(),key));
            retNode = node;
        }else {
            //待删除节点左子树为空的情况
            if (node.getLeft() == null) {
                Node rightNode = node.getRight();
                node.setRight(null);
                size--;
                retNode = rightNode;
            }
            //待删除节点右子树为空的情况
            else if (node.getRight() == null) {
                Node leftNode = node.getLeft();
                node.setLeft(null);
                size--;
                retNode = leftNode;
            }else {
                //待删除节点左右子树均不为空的情况
                //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node successor = minimum(node.getRight());
                successor.setRight(removeMin(node.getRight()));
                successor.setLeft(node.getLeft());
                node.setLeft(null);
                node.setRight(null);
                retNode = successor;
            }
        }
        if (retNode == null) {
            return null;
        }
        return service(retNode);
    }

    private Node service(Node node) {
        node.setHeight(1 + Math.max(getHeight(node.getLeft()),getHeight(node.getRight())));
        int balanceFactor = getBalanceFactor(node);
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) >= 0) {
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) <= 0) {
            return leftRotate(node);
        }
        if (balanceFactor > 1 && getBalanceFactor(node.getLeft()) < 0) {
            node.setLeft(leftRotate(node.getLeft()));
            return rightRotate(node);
        }
        if (balanceFactor < -1 && getBalanceFactor(node.getRight()) > 0) {
            node.setRight(rightRotate(node.getRight()));
            return leftRotate(node);
        }
        return node;
    }

    private Node minimum(Node node) {
        if (node.getLeft() == null) {
            return node;
        }
        return minimum(node.getLeft());
    }

    private Node removeMin(Node node) {
        if (node.getLeft() == null) {
            Node rightNode = node.getRight();
            node.setRight(null);
            size--;
            return rightNode;
        }
        node.setLeft(removeMin(node.getLeft()));
        return service(node);
    }

    @Override
    public boolean contains(K key) {
        return getNode(root,key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(root,key);
        return node == null ? null : node.getValue();
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(root,key);
        if (node == null) {
            throw new IllegalArgumentException(key + "不存在");
        }
        node.setValue(value);
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.getKey()) == 0) {
            return node;
        }else if (key.compareTo(node.getKey()) < 0) {
            return getNode(node.getLeft(),key);
        }else {
            return getNode(node.getRight(),key);
        }
    }
}

public class MapMain {
    public static void main(String[] args) {
        System.out.println("傲慢与偏见");
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile("/Users/admin/Downloads/pride-and-prejudice.txt",words);
        System.out.println("共有单词: " + words.getSize());
        Map<String,Integer> map = new AVLTreeMap<>();
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
    }
}

public class TestMapMain {
    private static double testMap(Map<String,Integer> map,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        FileOperation.readFile(filename,words);
        System.out.println("共有单词: " + words.getSize());
        Stream.of(words.getData()).filter(word -> word != null)
                .forEach(word -> {
                    if (map.contains(word)) {
                        map.set(word,map.get(word) + 1);
                    }else {
                        map.add(word,1);
                    }
                });
        System.out.println("共有不同的单词: " + map.getSize());
        System.out.println("pride出现的次数: " + map.get("pride"));
        System.out.println("prejudice出现的次数: " + map.get("prejudice"));
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Map<String,Integer> bstMap = new BSTMap<>();
        double time1 = testMap(bstMap,filename);
        System.out.println("BST Map: " + time1 + " s");

        Map<String,Integer> linkedListMap = new LinkedListMap<>();
        double time2 = testMap(linkedListMap,filename);
        System.out.println("LinkedList Map: " + time2 + " s");

        Map<String,Integer> avlTreeMap = new AVLTreeMap<>();
        double time3 = testMap(avlTreeMap,filename);
        System.out.println("AVLTree Map: " + time3 + " s");
    }
}

public class AVLTreeSet<T extends Comparable<T>> implements Set<T> {
    private Tree<T> avlTree;

    public AVLTreeSet() {
        avlTree = new AVLTree<>();
    }

    @Override
    public void add(T value) {
        avlTree.add(value);
    }

    @Override
    public void remove(T value) {
        avlTree.remove(value);
    }

    @Override
    public boolean contains(T value) {
        return avlTree.contains(value);
    }

    @Override
    public int getSize() {
        return avlTree.getSize();
    }

    @Override
    public boolean isEmpty() {
        return avlTree.isEmpty();
    }
}

public class TestSetMain {
    private static double testSet(Set<String> set,String filename) {
        long startTime = System.nanoTime();
        System.out.println(filename);
        Array<String> words = new DefaultArray<>();
        if (FileOperation.readFile(filename,words)) {
            System.out.println("共有单词: " + words.getSize());
            Stream.of(words.getData()).filter(data -> data != null)
                    .forEach(set::add);
            System.out.println("共有不同单词: " + set.getSize());
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
    public static void main(String[] args) {
        String filename = "/Users/admin/Downloads/pride-and-prejudice.txt";
        Set<String> bstSet = new BSTSet<>();
        double time1 = testSet(bstSet,filename);
        System.out.println("BST Set: " + time1 + " s");
        System.out.println();
        Set<String> linkedListSet = new LinkedListSet<>();
        double time2 = testSet(linkedListSet,filename);
        System.out.println("LinkedList Set: " + time2 + " s");
        System.out.println();
        Set<String> avlTreeSet = new AVLTreeSet<>();
        double time3 = testSet(avlTreeSet,filename);
        System.out.println("AVLTree Set: " + time3 + " s");
    }
}