算法组-常见的数据结构基础

一、单向链表和双向链表最简单练习

        1）单链表和双向链表如何反转

        2)  删除指定值

        结点类型

//单链表结点
    public static class Node{
        private int val;
        private Node next;
        public Node(int data){
            this.val = val;
 
        }
    }
 
    //双向链表结点
    public static class DoubleNode{
        private int value;
        private DoubleNode last;
        private DoubleNode next;
        public DoubleNode(int data){
            this.value = value;
 
        }
    }

        反转单链表

    /**
     * 反转单链表
     * 一定需要返回值(就是反转后的结点)
     */
    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;
    }

删除单链指定值

    /**
     * 删除指定值，还得设置返回值，因为有可能删除了头部结点，所以需要返回Node
     */
    public static Node removeValue(Node head,int value){
        //head来到第一个不需要删除的位置作为头部
        while (head!=null){
            if (head.val != value){
                break;
            }
            head = head.next;
        }
        // 1 ) head == null
        // 2 ) head != null
        Node pre = head;
        Node cur = head;
        //从头开始往后遍历，如果值相同的话就将指针移动，否则下移，知道结束为止
        while (cur!=null){
            if (cur.val == value){
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

二、栈和队列 

        1）双向链表实现

        2）数组实现

双向列表实现队列

数组实现队列

        核心思想：定义多个变量，例如end，begin，size等待，end：默认为0，每次新加入一个元素就自增1，begin：默认为0，表示每取出一个元素的话，就在原来值的小标取出然后自增1.size：就只需要判断加入的数量就行。相当于解耦！

package com.laoyang.体系班;
 
/**
 * @author:Kevin
 * @create: 2023-10-15 18:06
 * @Description: 数组实现队列
 */
 
public class day3_Array_Queen {
 
    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;
            this.limit = limit;
        }
 
        public void push(int value){
            if (limit == size){
                throw new RuntimeException("队列满了，不能再加了");
            }
            size++;
            arr[pushi] = value;
            //如果pushi没到底部就+1，到底部就置为0
            pushi = nextIndex(pushi);
 
        }
 
        //如果pushi没到底部就+1，到底部就置为0
        private int nextIndex(int i) {
            return i < limit-1 ? i+1 : 0;
        }
 
        public int pop(){
            if (size == 0){
                throw new RuntimeException("队列为空");
            }
            size--;
            int ans = arr[polli];
            polli = nextIndex(polli);
            return ans;
        }
    }
 
 
}

三、栈和队列常见面试题

        1. 实现一个特殊的栈，在基本功能上，返回栈中最小的元素

        要求复杂度都为O（1）

        实现思路：实现两个栈，一个数据栈（正常栈），一个最小栈，

        第一次压入7：压入两个栈中

        第二次压入5：数据栈直接入栈，如果当前数比最小栈的栈顶要小，直接入栈

        第三次压入8：数据站直接入栈，如果当前数不比最小栈栈顶小，重复压入最小栈栈顶5

        以此类推~，同时两个栈，入栈是同步的。

        2. 如何用栈实现队列

        实现思路：

        思路一：定义两个栈，一个push栈，一个pop栈，刚开始入栈时进入push栈中，如果需要往出取的话，就将push栈的值进入pop栈中，然后将pop栈的数据返回给用户。

        前提条件：

                1）必须一次性倒完。

                2）如果pop栈没有拿完，不能倒数据

package com.laoyang.体系班;
 
import java.util.Stack;
 
/**
 * @author:Kevin
 * @create: 2023-10-16 10:43
 * @Description: 栈实现队列
 */
 
public class day3_zhan_Quene {
 
    public static class TwoStacksQueue {
 
        public Stack stackPush;
        public Stack stackPop;
 
        public TwoStacksQueue() {
            stackPop = new Stack();
            stackPush = new Stack();
        }
 
        //push栈向pop栈到数据
        private void pushToPop(){
            if (stackPop.isEmpty()){
                while (!stackPush.isEmpty()){
                    stackPop.push(stackPush.pop());
                }
            }
        }
 
        public void add(int pushint){
            stackPush.push(pushint);
            pushToPop();
 
        }
 
        public int poll(){
            if (stackPush.isEmpty()&&stackPop.isEmpty()){
                throw new RuntimeException("队列为空");
            }
            pushToPop();
            return stackPop.pop();
        }
 
 
    }
 
    public static void main(String[] args) {
        TwoStacksQueue queue = new TwoStacksQueue();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        System.out.println(queue.poll());
 
    }
}

        

        3.如何用队列实现栈

        实现思路：

                两个队列，互相倒数据，首先将插入的数据放入队列一，如果需要出一个数据，就将其他数据放入队列二，然后出栈这个数据，如果又有数据出，就将这个数据留下来，其他数据又放入队列一，来回互相倒。

        

class MyStack {
 
    Queue queue1;
    Queue queue2;
 
    public MyStack() {
        queue1 = new LinkedList();
        queue2 = new LinkedList();
 
    }
    
    public void push(int x) {
        queue2.offer(x);
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
 
        }
        Queue temp = queue1;
        queue1 = queue2;
        queue2 = temp;
 
    }
    
    public int pop() {
        return queue1.poll();
 
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}
 

四、递归

        1. 数组最大值

package com.laoyang.体系班;
 
/**
 * @author:Kevin
 * @create: 2023-10-16 17:19
 * @Description: 递归
 */
 
public class day3_digui {
 
    public static void main(String[] args) {
        System.out.println(getMax(new int[]{1, 2, 3, 4, 5}));
    }
 
    public static int getMax(int[] arr){
        return arrMax(arr,0,arr.length-1);
 
    }
 
    public static int arrMax(int[] arr,int L,int R){
        if (L==R){
            return arr[L];
        }
        int mid = L + ((R-L) >> 1);
        int leftMax = arrMax(arr,L,mid);
        int rightMax = arrMax(arr,mid+1,R);
        return Math.max(leftMax,rightMax);
 
    }
}

五、哈希表（Hashmap）与有序表 （TreeMap）