【算法&数据结构体系篇class03】：数组、链表、栈、队列、递归时间复杂度、哈希表、有序表问题

灰太狼 2024-03-27 17:10 63阅读 0赞

### 一、反转链表 ###

package class03;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 链表反转
     */
    public class ReverseLinkedList {
        public static class Node {
            public int value;
            public Node next;
    
            public Node(int data) {
                value = data;
            }
        }
    
        public static class DoubleNode {
            public int value;
            public DoubleNode last;
            public DoubleNode next;
    
            public DoubleNode(int data) {
                value = data;
            }
        }
    
        //  head 单链表反转
        //   a    ->   b    ->  c  ->  null
        //   c    ->   b    ->  a  ->  null
        public static Node reverseLinkedList(Node head) {
            Node pre = null;
            Node next = null;
            while (head != null) {
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }
    
        //双链表反转
        public static DoubleNode reverseDoubleList(DoubleNode head) {
            DoubleNode pre = null;
            DoubleNode next = null;
            while (head != null) {
                next = head.next;
                head.next = pre;
                head.last = next;
                pre = head;
                head = next;
            }
            return pre;
        }
    
        //用集合来实现单链表反转，用于进行对比验证
        public static Node testReverseLinkedList(Node head) {
            if (head == null) return null;
            ArrayList<Node> list = new ArrayList<>();
            while (head != null) {
                list.add(head);
                head = head.next;
            }
            list.get(0).next = null;
            for (int i = 1; i < list.size(); i++) {
                list.get(i).next = list.get(i - 1);
            }
            return list.get(list.size() - 1);
        }
    
        //用集合来实现双链表反转，用于对比验证
        public static DoubleNode testReverseDoubleList(DoubleNode head) {
            if (head == null) return null;
            ArrayList<DoubleNode> list = new ArrayList<>();
            while (head != null) {
                list.add(head);
                head = head.next;
            }
            list.get(0).next = null;
            DoubleNode pre = list.get(0);
            for (int i = 1; i < list.size(); i++) {
                DoubleNode cur = list.get(i);
                cur.last = null;
                cur.next = pre;
                pre.last = cur;
                pre = cur;
            }
            return list.get(list.size() - 1);
    
        }
    
        // for test 随机生成单链表
        public static Node generateRandomLinkedList(int len, int value) {
            int size = (int) (Math.random() * (len + 1));
            if (size == 0) return null;
            Node head = new Node((int) (Math.random() * (value + 1)));
            Node pre = head;
            size--;
            while (size != 0) {
                Node cur = new Node((int) (Math.random() * (value + 1)));
                pre.next = cur;
                pre = cur;
                size--;
            }
            return head;
        }
    
        // for test 随机生成双链表
        public static DoubleNode generateRandomDoubleList(int len, int value) {
            int size = (int) (Math.random() * (len + 1));
            if (size == 0) return null;
            DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
            DoubleNode pre = head;
            size--;
            while (size != 0) {
                DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
                pre.next = cur;
                cur.last = pre;
                pre = cur;
                size--;
            }
            return head;
        }
        // for test 集合存储链表节点值
        public static List<Integer> getLinkedListOriginOrder(Node head) {
            List<Integer> ans = new ArrayList<>();
            while (head != null) {
                ans.add(head.value);
                head = head.next;
            }
            return ans;
        }
    
        // for test 验证链表节点值是否反转成功
        public static boolean checkLinkedListReverse(List<Integer> origin, Node head) {
            for (int i = origin.size() - 1; i >= 0; i--) {
                if (!origin.get(i).equals(head.value)) {
                    return false;
                }
                head = head.next;
            }
            return true;
        }
    
        // for test
        public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
            List<Integer> ans = new ArrayList<>();
            while (head != null) {
                ans.add(head.value);
                head = head.next;
            }
            return ans;
        }
    
        // for test 验证双链表节点值是否反转成功
        public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
            DoubleNode end = null;
            for (int i = origin.size() - 1; i >= 0; i--) {
                if (!origin.get(i).equals(head.value)) {
                    return false;
                }
                end = head;
                head = head.next;
            }
            for (int i = 0; i < origin.size(); i++) {
                if (!origin.get(i).equals(end.value)) {
                    return false;
                }
                end = end.last;
            }
            return true;
        }
    
        // head = removeValue(head, 2);  删除链表中值为2的节点。 1->3->2->2->4->2->5  =》   1->3->4->5
        public static Node removeValue(Node head, int num) {
            //head来到第一个不需要删的位置 先确认头节点，排除排前面如果是num 则需一次跳过，比如 2->2->2->2->1->3   需要将新的头节点head指向到1的位置
            while(head != null){
                if(head.value != num){
                    break;
                }
                head = head.next;
            }
            // 1 ) head == null
            // 2 ) head != null
            Node pre =head,cur=head;
            while (cur != null){
                if(cur.value ==num){
                    pre.next = cur.next;
                }else {
                    pre = cur;
                }
                cur = cur.next;
            }
            return head;
        }
    
        // for test
        public static void main(String[] args) {
            int len = 50;
            int value = 100;
            int testTime = 100000;
            System.out.println("test begin!");
            for (int i = 0; i < testTime; i++) {
                Node node1 = generateRandomLinkedList(len, value);
                List<Integer> list1 = getLinkedListOriginOrder(node1);
                node1 = reverseLinkedList(node1);
                if (!checkLinkedListReverse(list1, node1)) {
                    System.out.println("Oops1!");
                }
    
                Node node2 = generateRandomLinkedList(len, value);
                List<Integer> list2 = getLinkedListOriginOrder(node2);
                node2 = testReverseLinkedList(node2);
                if (!checkLinkedListReverse(list2, node2)) {
                    System.out.println("Oops2!");
                }
    
                DoubleNode node3 = generateRandomDoubleList(len, value);
                List<Integer> list3 = getDoubleListOriginOrder(node3);
                node3 = reverseDoubleList(node3);
                if (!checkDoubleListReverse(list3, node3)) {
                    System.out.println("Oops3!");
                }
    
                DoubleNode node4 = generateRandomDoubleList(len, value);
                List<Integer> list4 = getDoubleListOriginOrder(node4);
                node4 = testReverseDoubleList(node4);
                if (!checkDoubleListReverse(list4, node4)) {
                    System.out.println("Oops4!");
                }
    
            }
            System.out.println("test finish!");
        }
    }

### 二、双向链表实现栈和队列 ###

package class03;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    
    //双向链表实现队列和栈
    public class DoubleEndsQueueToStackAndQueue {
        public static class Node<T> {
            public T value;
            public Node<T> last;
            public Node<T> next;
    
            public Node(T data) {
                value = data;
            }
        }
    
        public static class DoubleEndQueue<T> {
            public Node<T> head;
            public Node<T> tail;
    
            //头端添加节点
            public void addFromHead(T value) {
                Node<T> cur = new Node<>(value);
                if (head == null) {
                    head = cur;
                    tail = cur;
                } else {
                    cur.next = head;
                    head.last = cur;
                    head = cur;
                }
            }
    
            //尾端添加节点
            public void addFromBottom(T value) {
                Node<T> cur = new Node<>(value);
                if (head == null) {
                    head = cur;
                    tail = cur;
                } else {
                    cur.last = tail;
                    tail.next = cur;
                    tail = cur;
                }
            }
    
            //弹出头端节点
            public T popFromHead() {
                if (head == null) {
                    return null;
                }
                Node<T> cur = head;
                if (head == tail) {
                    head = null;
                    tail = null;
                } else {
                    head = head.next;
                    head.last = null;
                    cur.next = null;
                }
                return cur.value;
            }
    
            //弹出尾端节点
            public T popFromBottom() {
                if (head == null) {
                    return null;
                }
                Node<T> cur = tail;
                if (head == tail) {
                    head = null;
                    tail = null;
                } else {
                    tail = tail.last;
                    tail.next = null;
                    cur.last = null;
                }
                return cur.value;
            }
    
            //判断是否为空
            public boolean isEmpty() {
                return head == null;
            }
        }
    
        //构建栈结构
        public static class MyStack<T> {
            //双向链表结构作为属性
            private DoubleEndQueue<T> queue;
    
            //构造器
            public MyStack() {
                queue = new DoubleEndQueue<>();
            }
    
            //入栈
            public void push(T data) {
                queue.addFromHead(data);
            }
    
            //出栈
            public T pop() {
                return queue.popFromHead();
            }
    
            //是否为空
            public boolean isEmpty() {
                return queue.isEmpty();
            }
        }
    
        //构造队列
        public static class MyQueue<T> {
            private DoubleEndQueue<T> queue;
    
            public MyQueue() {
                queue = new DoubleEndQueue<>();
            }
    
            public void push(T data) {
                queue.addFromHead(data);
            }
    
            public T poll() {
                return queue.popFromBottom();
            }
    
            public boolean isEmpty() {
                return queue.isEmpty();
            }
        }
    
        //判断两个Integer节点是否相等
        public static boolean isEqual(Integer o1, Integer o2) {
            if (o1 == null && o2 == null) return true;
            if (o1 == null && o2 != null) return false;
            if (o1 != null && o2 == null) return false;
            return o1.equals(o2);
        }
    
        public static void main(String[] args) {
            int oneTestDataNum = 100;
            int value = 10000;
            int testTimes = 100000;
            for (int i = 0; i < testTimes; i++) {
                Code03_DoubleEndsQueueToStackAndQueue.MyStack<Integer> myStack = new Code03_DoubleEndsQueueToStackAndQueue.MyStack<>();
                Code03_DoubleEndsQueueToStackAndQueue.MyQueue<Integer> myQueue = new Code03_DoubleEndsQueueToStackAndQueue.MyQueue<>();
                Stack<Integer> stack = new Stack<>();
                Queue<Integer> queue = new LinkedList<>();
                for (int j = 0; j < oneTestDataNum; j++) {
                    int nums = (int) (Math.random() * value);
                    if (stack.isEmpty()) {
                        myStack.push(nums);
                        stack.push(nums);
                    } else {
                        if (Math.random() < 0.5) {
                            myStack.push(nums);
                            stack.push(nums);
                        } else {
                            if (!isEqual(myStack.pop(), stack.pop())) {
                                System.out.println("oops!");
                            }
                        }
                    }
                    int numq = (int) (Math.random() * value);
                    if (queue.isEmpty()) {
                        myQueue.push(numq);
                        queue.offer(numq);
                    } else {
                        if (Math.random() < 0.5) {
                            myQueue.push(numq);
                            queue.offer(numq);
                        } else {
                            if (!isEqual(myQueue.poll(), queue.poll())) {
                                System.out.println("oops!");
                            }
                        }
                    }
                }
            }
            System.out.println("finish!");
        }
    }

### 三、数组实现队列 ###

（数组实现栈就比较简单 因为都是入栈出栈只需在一个方向，下一个index索引加1就能满足，其他逻辑类似，而队列，需要判断是index+1还是回到0索引位置）

package class03;
    
    /**
     * 
     */
    //数组实现队列， 栈就比较简单 入栈就直接按需从0索引赋值，出栈也是从最后一个索引arr.length-1开始弹出
    //队列就是先进先进，入栈从0开始，出栈从0开始，而且中间出栈后，0位置空，接着要入栈就得判断下一个位置
    // 是否超边界，是否超大小，如果超大小就肯定满了，如果没有超，就看下个位置会不会越界，会就需要入栈到0位置，
    // 形成一个环形循环数组
    
    public class RingArray {
        public static class MyQueue {
            private int[] arr;
            private int pushi; //随着插入，这个索引就往下，所以表示是 元素边界的end边界
            private int polli; //begin
            private int size;  //存在数组中的元素个数
            private final int limit; //数组的长度设置为常量 不可修改
    
            public MyQueue(int limit) {
                arr = new int[limit];
                pushi = 0;
                polli = 0;
                size = 0;
                this.limit = limit;
            }
    
            public void push(int value) {
                //先判断size元素实际个数是否与数组长度相等 相等就不能入队列了
                if (size == limit) {
                    throw new RuntimeException("队列满，不能添加元素！");
                }
                size++;
                //赋值
                arr[pushi] = value;
                //判断下个索引
                pushi = nextIndex(pushi);
    
            }
    
            public int poll() {
                //先判断size元素实际个数是否为0，0则没有元素 不能出队列
                if (size == 0) {
                    throw new RuntimeException("队列空，不能弹出元素！");
                }
                size--;
                //返回弹出元素，该索引位置的内容无需重新赋值，因为下次元素push到该位置会赋值覆盖的
                int ans = arr[polli];
                //判断下个索引
                polli = nextIndex(polli);
                return ans;
            }
    
            public boolean isEmpty() {
                return size == 0;
            }
    
            //判断元素的下个索引，需要与arr[limit-1]即数组最后一个索引比较，如果小于表示可以接着+1，
            //大于等于就需要循环走到0索引位置
            public int nextIndex(int index) {
                return index < limit - 1 ? ++index : 0;
            }
        }
    }

### 四、通过两个栈结构，来实现获取栈中的最小值 ###

package class03;
    
    import java.util.Stack;
    
    /**
     *
     */
    
    //通过两个栈结构，来实现获取栈中的最小值
    public class GetMinStack {
        public static class MyStack1 {
            private Stack<Integer> stackData;
            private Stack<Integer> stackMin;
    
            public MyStack1() {
                stackData = new Stack<>();
                stackMin = new Stack<>();
            }
    
            public void push(int num) {
                //如果当前最小值为空，那么入栈的值就定为最小值，入最小栈
                if (stackMin.isEmpty()) {
                    stackMin.push(num);
                } else {
                    //如果非空，而当前值小于等于最小栈的最小值，那么就入栈，大于则不用入栈。保证最小栈栈顶是最小值
                    if (num <= this.getmin()) {
                        stackMin.push(num);
                    }
                }
                stackData.push(num);
            }
    
            public int pop() {
                if (stackData.isEmpty()) {
                    throw new RuntimeException("数据栈为空，没有元素！");
                }
                //数据栈出栈
                int ans = stackData.pop();
                //同时要判断是否出栈的是与当前最小栈的栈顶一样 是则需要一起出栈 才能保持始终为最小值栈顶
                if (ans == this.getmin()) {
                    stackMin.pop();
                }
                return ans;
    
            }
    
            public int getmin() {
                if (stackMin.isEmpty()) {
                    throw new RuntimeException("最小栈为空，没有元素！");
                }
                //非空则取栈顶元素即最小值
                return stackMin.peek();
            }
        }
    
        public static void main(String[] args) {
            MyStack1 stack1 = new MyStack1();
            stack1.push(3);
            System.out.println(stack1.getmin());
            stack1.push(4);
            System.out.println(stack1.getmin());
            stack1.push(1);
            System.out.println(stack1.getmin());
            System.out.println(stack1.pop());
            System.out.println(stack1.getmin());
    
            System.out.println("=============");
        }
    }

### 五、两个栈实现队列,队列先进先出，栈先进后出，需要用两个栈来实现 ###

package class03;
    
    import java.util.Stack;
    
    /**
     * 两个栈实现队列,队列先进先出，栈先进后出，需要用两个栈来实现
     */
    public class TwoStacksImplementQueue {
        public static class TwoStacksQueue{
            private Stack<Integer> stackPush;
            private Stack<Integer> stackPop;
            public TwoStacksQueue(){
                stackPush = new Stack<>();
                stackPop = new Stack<>();
            }
            public void add(int num){
                stackPush.push(num);
    
            }
            //出栈注意，假设
            //pop栈有数据就直接出栈。 没数据就需要将现有的push栈数据全部清空入pop栈，在出pop栈
            public int poll(){
                if(stackPop.isEmpty() && stackPush.isEmpty()){
                    throw new RuntimeException("队列为空，没有元素！");
                }
                if(!stackPop.isEmpty()){
                    return stackPop.pop();
                }else{
                    while(!stackPush.empty())
                        stackPop.push(stackPush.pop());
                }
                return stackPop.pop();
            }
            public int peek(){
                if(stackPop.isEmpty() && stackPush.isEmpty()){
                    throw new RuntimeException("队列为空，没有元素！");
                }
                if(!stackPop.isEmpty()){
                    return stackPop.peek();
                }else{
                    while(!stackPush.empty())
                        stackPop.push(stackPush.pop());
                }
                return stackPop.peek();
            }
        }
        public static void main(String[] args) {
            TwoStacksQueue test = new TwoStacksQueue();
            test.add(1);
            test.add(2);
            test.add(3);
            test.add(4);
            System.out.println(test.peek());
            System.out.println(test.poll());
            System.out.println(test.peek());
            System.out.println(test.poll());
            System.out.println(test.peek());
            System.out.println(test.poll());
        }
    }

### 六、两个队列实现一个栈结构 ###

package class03;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 两个队列实现一个栈结构
     */
    public class TwoQueueImplementStack {
        public static class TwoQueueStack<T> {
            private Queue<T> queue;
            private Queue<T> help;
    
            public TwoQueueStack() {
                queue = new LinkedList<>();
                help = new LinkedList<>();
            }
    
            public void push(T value) {
                queue.offer(value);
            }
    
            public T poll() {
                //把队列都弹出到help辅助队列，保留最后一个不弹，用来pop
                while (queue.size() > 1) {
                    help.offer(queue.poll());
                }
                T ans = queue.poll();
                //此时queue为空队列，再把help队列数据放回来
                Queue<T> temp = queue;
                queue = help;
                help = temp;
                return ans;
            }
    
            public T peek() {
                //把队列都弹出到help辅助队列，保留最后一个不弹，用来pop
                while (queue.size() > 1) {
                    help.offer(queue.poll());
                }
                T ans = queue.poll();
                //这里注意要把弹出的最后一个元素入回队列
                help.offer(ans);
                //此时queue为空队列，再把help队列数据放回来
                Queue<T> temp = queue;
                queue = help;
                help = temp;
                return ans;
            }
    
            public boolean isEmpty() {
                return queue.isEmpty();
            }
        }
    
        public static void main(String[] args) {
            System.out.println("test begin");
            TwoQueueStack<Integer> myStack = new TwoQueueStack<>();
            Stack<Integer> test = new Stack<>();
            int testTime = 1000000;
            int max = 1000000;
            for (int i = 0; i < testTime; i++) {
                if (myStack.isEmpty()) {
                    if (!test.isEmpty()) {
                        System.out.println("Oops");
                    }
                    int num = (int) (Math.random() * max);
                    myStack.push(num);
                    test.push(num);
                } else {
                    if (Math.random() < 0.25) {
                        int num = (int) (Math.random() * max);
                        myStack.push(num);
                        test.push(num);
                    } else if (Math.random() < 0.5) {
                        if (!myStack.peek().equals(test.peek())) {
                            System.out.println("Oops");
                        }
                    } else if (Math.random() < 0.75) {
                        if (!myStack.poll().equals(test.pop())) {
                            System.out.println("Oops");
                        }
                    } else {
                        if (myStack.isEmpty() != test.isEmpty()) {
                            System.out.println("Oops");
                        }
                    }
                }
            }
            System.out.println("test finish!");
    
        }
    
    }

### 七、Master公式 ###

形如

T(N)= a \* T(N/b) + O(N^d)(其中的a、b、d都是常数)

的递归函数，可以直接通过Master公式来确定时间复杂度

如果log(b,a)< d，复杂度为O(N^d)

如果 log(b,a)> d，复杂度为O(N^log(b,a))

如果 log(b,a)== d，复杂度为O(N^d \*logN)

注意：

(注意是需要两次子递归的递归元素是同等的，比如中点分开左右两数组，分别递归，此时两个子递归元素都是N/2,时间复杂度O(N/2)+O(N/2),例如归并排序)

归并排序，递归过程还需要进行合并左右数组，需要合并操作时间复杂度为O(N)

此形式符合Master公式，T(N)= 2 \* T(N/2) + O(N^1) ，a=2,b=2,d=1，

**log(2,2) == 1 所以归并排序复杂度为O(N \*logN)**

### 八、哈希表 ###

> 1)哈希表在使用层面上可以理解为一种集合结构  
> 2)如果只有key，没有伴随数据value，可以使用HashSet结构  
> 3)如果既有key，又有伴随数据value，可以使用HashMap结构  
> 4)有无伴随数据，是HashMap和HashSet唯一的区别，实际结构是一回事   
> 5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为 O(1)，但是常数时间比较大  
> 6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小  
> 7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节

### 九、有序表 ###

> 1)有序表在使用层面上可以理解为一种集合结构  
> 2)如果只有key，没有伴随数据value，可以使用TreeSet结构  
> 3)如果既有key，又有伴随数据value，可以使用TreeMap结构  
> 4)有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事  
> 5)有序表把key按照顺序组织起来，而哈希表完全不组织  
> 6)红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同  
> 7)放入如果是基础类型，内部按值传递，内存占用就是这个东西的大小  
> 8)放入如果不是基础类型，内部按引用传递，内存占用是8字节  
> 9)不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

> 1)void put(K key, V value)  
> 将一个(key，value)记录加入到表中，或者将key的记录更新成value。  
> 2)V get(K key)  
> 根据给定的key，查询value并返回。  
> 3)void remove(K key)  
> 移除key的记录。   
> 4)boolean containsKey(K key)  
> 询问是否有关于key的记录。  
> 5)K firstKey()  
> 返回所有键值的排序结果中，最小的那个。  
> 6)K lastKey()  
> 返回所有键值的排序结果中，最大的那个。  
> 7)K floorKey(K key)  
> 返回<=key 离key最近的那个  
> 8)K ceilingKey(K key）  
> 返回>=key 离key最近的那个

哈希表在使用时，增删改查时间复杂度都是O(1)

有序表在使用时，比哈希表功能多，时间复杂度都是O(logN)