• 数据结构 — — 常见链表问题、栈、队列问题、哈希表、有序表

    数据结构 — — 常见链表问题、栈、队列问题

    在日常刷题和面试过程中，链表问题还是占有一定的分量的，下面是一些简单常见的链表题目

    1 链表问题

    1.1 链表反转问题

    1.1 单链表反转

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    1.2 双链表反转

    原理同单链表一致，只不过多了一个last【head.last = next】

        //定义双链表
    public static class DoubleNode{
        public int val;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int val){
            this.val = val;
        }
    }

    public static DoubleNode reverseDoubleList(DoubleNode head){
        DoubleNode next = null;
        DoubleNode pre = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    1.2 删除链表中的指定元素

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //如果链表的头与要删除的元素值相同
        while(head != null){
            if(head.val != val){
                break;
            }
            head = head.next;
        }
        //链表头的val与要删除的val不同
        ListNode pre = head;
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val){
                //值相等，就跳一个
                pre.next = cur.next;
            } else {
                //值不等，直接等
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    2 栈、队列问题

    栈：先进后出【弹夹】
    队列：先进先出【水管】

    2.1 栈、队列的实际实现

    2.1.1 用栈实现队列

    核心：用两个栈，一个pop，一个push，定义两个栈转换的方法

    //用栈实现队列
class MyQueue {

    //push栈
    public Stack<Integer> stackPush;
    //pop栈
    public Stack<Integer> stackPop;
    
    public MyQueue() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }
    
    //push栈向pop栈倒数据
    private void pushToPop(){
        if(stackPop.empty()){
            while(!stackPush.empty()){
                stackPop.push(stackPush.pop());
            }
        }
    }
    
    public void push(int x) {
        stackPush.push(x);
        //数据进入栈后，马上转到pop栈
        pushToPop();
    }
    
    public int pop() {
        if(stackPop.empty() && stackPush.empty()){
            throw new RuntimeException("queue is empty!");
        }
        //数据转移
        pushToPop();
        return stackPop.pop();
    }
    
    public int peek() {
        if(stackPop.empty() && stackPush.empty()){
            throw new RuntimeException("queue is empty!");
        }
        pushToPop();
        return stackPop.peek();
    }
    
    public boolean empty() {
        pushToPop();
        return stackPop.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    2.1.2 用队列实现栈

    思路：主要是用两个队列，一个是做辅助的help，只要当涉及到pop、peek等操作的时候才会用到

    //用队列实现栈
class MyStack {
    public Queue<Integer> queue;
    public Queue<Integer> help;

    public MyStack() {
        queue = new LinkedList<Integer>();
        help = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        queue.offer(x);
    }
    //queue :5 4 3 2 1
    //help:
    public int pop() {
        while(queue.size() > 1){
            help.offer(queue.poll());
        }
        //queue: 5
        //help: 4 3 2 1
        int res = queue.poll();//要返回的最终结果
        Queue<Integer> temp = queue;
        queue = help;
        help = temp;
        //queue:4 3 2 1
        //help: 5
        return res;
    }
    
    public int top() {
        while(queue.size() > 1){
            help.offer(queue.poll());
        }
        int res = queue.poll();
        help.offer(res);
        Queue<Integer> temp = queue;
        queue = help;
        help = temp;
        return res;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    2.2 最小栈

    思路：主要是用两个栈，一个用来存数据stackData，一个用来存最小值信息

    //最小栈
class MinStack {
    
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public MinStack() {
        stackData = new Stack<Integer>();
        stackMin = new Stack<Integer>();
    }
    
    public void push(int val) {
        if(stackMin.isEmpty()){
            //存放最小值的栈为空，直接放入val
            stackMin.push(val);
        } else if(val <= getMin()){
            //如果stackMin不为null，比较，比min小就压栈
            stackMin.push(val);
        }
        stackData.push(val);
    }
    
    public void pop() {
        if(stackData.isEmpty()){
            throw new RuntimeException("your stak is empty");
        }
        int val = stackData.pop();
        if(val == getMin()){
            //将要弹出的值与最小值相同，stackMin也应当对应弹出
            stackMin.pop();
        }
        // return val;
    }
    
    public int top() {
        if(stackData.isEmpty()){
            throw new RuntimeException("your stack is empty");
        }
        int val = stackData.pop();
        stackData.push(val);
        return val;
    }
    
    public int getMin() {
        if(stackMin.isEmpty()){
            throw new RuntimeException("your stack is empty");
        }
        int val = stackMin.pop();
        stackMin.push(val);
        return val;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    3 拓展【Master公式、hash表、有序表】

    3.1 Master公式

    在常见算法题中，我们难免会遇到很多递归的问题，那么这时我们该如何估计时间复杂度呢？
    Master公式就能很好帮我们估计。

    Master公式：
    T(N) = a* T(N/b) + O(N ^d) （其中，a、b、d都是常数）的递归函数，我们可以直接通过Master公式来确定时间复杂度
    例如：在[0,N]范围上求最大值，使用递归（分为left与right）：T(N) = 2 * T(N/2) + O(1)

    因为每次是分两半，因此：b=2，因为有两部分，因此a=2，O（1）是因为有一个比较的流程
    假如是分为1/3、2/3，结果就为：T(N) = T(N/3) + T(2N/3) + O(1)

    • 如果log(b,a) < d,复杂度为：O（N^d）
    • 如果log(b,a) > d, 复杂度为：O(N^log(b,a))
    • 如果log(b,a) == d,复杂度为：O(N^d * logN)
      log(b,a)表示：log以b为底，a的对数
      因此，上面二分的时间复杂度为：O(logN)

    3.2 哈希表

    1. 使用层面上理解为集合结构
    2. 如果key，没有伴随value，使用HashSet
    3. key、value都有，用HashMap
    4. 有无伴随的value，是HashMap与HashSet唯一区别，实际结构是一样的【HashSet底层就是HashMap】
    5. 使用哈希表的增（put）、删（remove）、改（put）、查（get）操作，可以认为时间复杂度为O(1)，但是常数时间比较大
    6. 放入hash表的东西，如果是Integer、Double、String这种，内部按值传递，内存占用是这个东西的大小
    7. 放入hash表的东西，如果不是基础类型（User、Emp等），内部按引用传递，内存占用是8Byte

    3.3 有序表

    1. 有序表在使用层面上可以理解为一种集合结构
    2. 如果只有key，没有value，使用TreeSet
    3. 如果既有key，又有value，使用TreeMap
    4. TreeSet、TreeMap底层结构也是一回事，只是看有无伴随数据
    5. 有序表把key按照顺序组织起来，而哈希表完全不组织【排序】
    6. 红黑树、AVL数、size-balance-tree和跳表都是有序表结构，只是底层具体实现不同【Java默认使用的是红黑树】
    7. 放入基础数据类型，内部按值传递；否则按引用传递，占8字节

    不管是什么具体实现，只要是有序表，都有一下固定的基本功能和固定时间复杂度：

    1. void put(K key, V value):新增、更新
    2. V get(K key):查询给定key
    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)

  • 相关阅读:
    哈希的使用
    MMDetection安装流程与测试
    windows系统mysql服务启动失败
    【LittleXi】地址空间三题
    第二课第一周第8节 风险得分计算+作业解析
    测试docker GPU性能损失
    .net第三章-- C#语句的组成与使用
    SpringCloud 三种服务调用方式详解
    12李沐动手学深度学习v2/数据复杂度与模型容量选择不当造成的 过拟合和欠拟合现象
    【C语言初阶】一、初识C语言
  • 原文地址：https://blog.csdn.net/weixin_45565886/article/details/126206272