算法

【体系学习004】一些基础的数据结构

Posted by Hilda on September 21, 2025

1.单链表和双链表反转

单链表反转：

1
2
3
4
5
6
7
8
9
10

public static ListNode reverseListNode(ListNode head) {
    ListNode pre = null, next = null, cur = head;
    while (cur != null) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

双链表反转：

1
2
3
4
5
6
7
8
9
10
11

public static DoubleListNode reverseDoubleListNode(DoubleListNode head) {
    DoubleListNode pre = null, next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        head.last = next;// 多了这个
        pre = head;
        head = next;
    }
    return  pre;
}

2.在链表中删除指定值的所有节点

力扣203题就是这个题：https://leetcode.cn/problems/remove-linked-list-elements/description/

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

/**
 * 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) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            if (cur.val == val) {
                if (pre == null) {// 要删除的节点是头节点
                    head = head.next;
                    cur = head;
                } else {
                    pre.next = cur.next;
                    cur = pre.next;
                }
            } else {
                pre = cur;
                cur = cur.next;
            }
            
        }
        return head;
    }
}

牛客上有一道类似的题，但是是ACM风格：https://www.nowcoder.com/practice/1a5fd679e31f4145a10d46bb8fd3d211

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

import java.util.*;
import java.io.*;

class ListNode {
    int val;
    ListNode next;
    public ListNode(int v) {
        this.val = v;
        this.next = null;
    }
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args)  throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;
            in.nextToken();
            ListNode head = new ListNode((int)in.nval);
            in.nextToken();
            ListNode cur = head;
            for (int i = 1;i < n;i++) {
                cur.next = new ListNode((int)in.nval);
                in.nextToken();
                cur = cur.next;
            }
            int v = (int)in.nval;
            ListNode ans = deleteVal(head, v);
            while (ans != null) {
                out.print(ans.val + " ");
                ans = ans.next;
            }
            

        }
        out.flush();
        br.close();
        out.close();
    }

    public static ListNode deleteVal(ListNode head, int v) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            if (cur.val == v) {
                if (pre == null) {
                    head = head.next;
                    cur = head;
                } else {
                    pre.next = cur.next;
                    cur = pre.next;
                }
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return head;
    }
}

3.栈和队列

力扣225用队列实现栈

225. 用队列实现栈

(一个队列实现栈，其实也可以两个队列，一个作为正式的，一个作为临时队列，这里不写了，参考博客：https://kirsten-1.github.io/2025/03/25/%E7%AE%97%E6%B3%95014/)

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

class MyStack {

    Queue<Integer> q;

    public MyStack() {
        q = new LinkedList<>();
    }
    
    public void push(int x) {
        int size = q.size();
        q.add(x);
        for (int i = 0;i < size;i++) {
            q.add(q.poll());
        }

    }
    
    public int pop() {
        return q.poll();
    }
    
    public int top() {
        return q.peek();
    }
    
    public boolean empty() {
        return q.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();
 */

力扣232用栈实现队列

232. 用栈实现队列

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

class MyQueue {

    Stack<Integer> s1 ;
    Stack<Integer> s2;
 
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        if (!empty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        s1.push(x);
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
    }
    
    public int pop() {
        return s1.pop();
    }
    
    public int peek() {
        return s1.peek();
    }
    
    public boolean empty() {
        return s1.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();
 */

力扣641设计循环双端队列

641. 设计循环双端队列

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

class MyCircularDeque {

    int[] data;
    int limit;
    int size;
    int head;
    int tail;
    public MyCircularDeque(int k) {
        limit = k;
        data = new int[k];
        size = head = tail = 0;
    }
    
    public boolean insertFront(int value) {
        if (isFull()) return false;
        if (size == 0) {
            head = tail = 0;
            
        } else {
            head = head == 0 ? (limit - 1) : (head - 1);
        }
        data[head] = value;
        size++;

        return true;
    }
    
    public boolean insertLast(int value) {
        if (isFull()) return false;
        if (size == 0) {
            head = tail = 0;
        } else {
            tail = tail == (limit - 1) ? 0 : (tail + 1);
        }
        data[tail] = value;
        size++;
        return true;
    }
    
    public boolean deleteFront() {
        if (isEmpty()) return false;
        head = head == (limit - 1) ? 0 : (head + 1);
        size--;
        return true;
    }
    
    public boolean deleteLast() {
        if (isEmpty()) return false;
        tail = tail == 0 ? (limit - 1) : (tail - 1);
        size--;
        return true;
    }
    
    public int getFront() {
        if (isEmpty()) return -1;
        return data[head];
        
    }
    
    public int getRear() {
        if (isEmpty()) return -1;
        return data[tail];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == limit;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

力扣155最小栈

155. 最小栈

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

class MinStack {
    Stack<Integer> data ;
    Stack<Integer> min;


    public MinStack() {
        data = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int val) {
        data.push(val);
        if (min.isEmpty()) {
            min.push(val);
        } else {
            min.push(Math.min(min.peek(), val));
        }
    }
    
    public void pop() {
        data.pop();
        min.pop();
    }
    
    public int top() {
        return data.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

/**
 * 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();
 */

4.用递归行为得到数组中的最大值，并用master公式来估计时间复杂度

用递归行为得到数组中的最大值:

1
2
3
4
5
6
7
8
9
10
11

public int findMax(int[] arr) {
    return f(arr, 0, arr.length - 1);
}

public int f(int[] arr, int L, int R) {
    if (L == R) {
        return arr[L];
    }
    int M = L + ((R - L) >> 1);
    return Math.max(f(arr, L, M), f(arr, M + 1, R));
}

系统栈

系统栈是实现递归机制的底层工具。每次函数调用，无论它是递归的还是非递归的，都会在系统栈上创建一个栈帧（Stack Frame）。

系统栈（或调用栈）是一块特殊的内存区域，用于管理程序的函数调用。它的工作方式遵循“后进先出”（LIFO）的原则。当一个函数被调用时，它的栈帧被压入栈中；当函数执行完毕并返回时，它的栈帧就会从栈中弹出。

一个栈帧通常包含以下信息：

  • 局部变量：该函数中定义的所有局部变量。
  • 函数参数：传递给该函数的参数。
  • 返回地址：函数执行完毕后，程序应该回到哪里继续执行的地址。

如果递归调用没有正确的基准情况，或者递归深度过大，系统栈就会不断压入新的栈帧，直到耗尽可用内存，从而导致栈溢出（Stack Overflow）错误。这是递归编程中需要特别注意的问题。

因此，递归是函数的嵌套调用，而系统栈是管理这些嵌套调用的执行流和内存的工具。两者是相辅相成的关系。

所有递归都可以改成迭代的写法。

5.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(Nlog(b,a))\) 如果 \(log(b,a) == d\)，复杂度为\(O(N^d * logN)\)

6.哈希表

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

7.有序表

  • 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)

CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib spring6 算法题库 Java基础 java集合 ollama工具 python爬虫
    FRIENDS