【算法自由之路】链表、栈、队列、递归、哈希表

【算法自由之路】链表、栈、队列、递归、哈希表

链表

基本结构实现：Node 节点，单链表，双链表

class SingleNodeList{
    
   Node head;
   Node tail;
   class Node{
        object item;
    	Node next;
    }
    
}

class DubboNodeList{
    Node head;
   	Node tail;
    class Node{
        object item;
    	Node next;
    	Node pre;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

基本算法： 链表的反转，删除链表中的某个元素，链表头尾添加删除元素

主要逻辑为临时指针，操作记录历史记录进行反转，删除元素时要考虑边界情况删除头节点问题。

栈、队列

基本结构实现

栈：先进后出

队列：先进先出

使用链表实现栈、队列

栈就是链表只提供尾节点插入和弹出删除功能
队列是链表只提供头节点出队删除，尾节点插入的功能
1
2

使用数组实现栈、队列

这里不考虑扩容问题，先仅提供一个固定大小的构造方法。

对于栈和队列主要是使用多个索引来标识头尾位置进行操作即可，而头尾可以通过其他如 size 变量的维护来解耦关系，使得实现简单易懂。

int size； // 大小
int head; // 当前头部位置
int tail; // 当前尾部位置
int limit; // 最大数据元素限制 size <= limit
1
2
3
4

基本算法

最小数栈，在栈中可以一 O(1) 的时间复杂度返回当前栈的最小值。

//多空间思想，维护一个最小栈，和一个数据栈
Stack data;
Stack min;
// 数据栈 data 正常走栈的操作，min 只入栈当前最小值，如果当前入栈元素大于 min 栈栈顶元素则入栈一个栈顶元素相同值, 否则入栈当前值
// 出栈时同步出栈，获取最小值时，直接返回 min 栈栈顶元素即可，时间复杂度 O(1)
1
2
3
4
5

使用栈实现队列

// 维护两个栈
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;

public class QueueByStack<T> {

    private Stack<T> addStack;

    private Stack<T> pollStack;

    public QueueByStack() {
        this.addStack = new Stack<>();
        this.pollStack = new Stack<>();
    }

    public void add(T t) {
        addStack.add(t);
    }

    public T poll() {
        addToPoll(); // 每次出队前保证 add 全到 pop
        return pollStack.pop();
    }

    public void addToPoll() {
        // 这里遵循 poll 不为空才用往里面倒数据
        if (addStack.empty() || !pollStack.isEmpty()) {
            return;
        }
        while (!addStack.isEmpty()) {
            pollStack.add(addStack.pop());
        }
    }

    @Override
    public String toString() {
        return "QueueByStack{" +
                "addStack=" + addStack +
                ", popStack=" + pollStack +
                '}';
    }

    public static void main(String[] args) {
        QueueByStack<Integer> queueByStack = new QueueByStack<>();
        Queue<Integer> queue = new LinkedList<>();
        Random random = new Random();
        for (int k = 0; k < 100; k++) {
            for (int i = 0; i < random.nextInt(2000); i+=random.nextInt(5)) {
                if (random.nextBoolean() || queue.isEmpty()) {
                    queue.add(i);
                    queueByStack.add(i);
                } else {
                    Integer poll = queue.poll();
                    Integer pop = queueByStack.poll();
                    //System.out.println("right:"+poll+" test:"+pop);
                    if (!poll.equals(pop)) {
                        System.out.println("error");
                        System.out.println(queue);
                        System.out.println(queueByStack);
                        return;
                    }
                }
            }
        }
        System.out.println("success");
    }
}

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

使用队列实现栈

实现思路与上述栈实现队列代码殊途同归，这里不再赘述。
1

递归算法

方法的嵌套调用，实际底层是依赖于 JVM 的线程栈，嵌套调用会不断压入新的栈针，直到某个方法执行完毕返回结果给上一个栈帧。

利用递归调用寻找数组中最大值。

递归的时间复杂度计算，需要满足 T(N) = a*T(N/b) + O(N^d); 即每个子调用规模都相等。

对于满足上式的递归算法有以下结论

log(a,b) > d  则时间复杂度为 O(N^log(a,b))
log(a,b) < d  则时间复杂度为 O(N^d)
log(a,b) == d  则时间复杂度为 O(N^d * log(N))
1
2
3

举个简单的例子，寻找数组最大值

   // 此递归方法含义，在 [i , j] 范围内寻找最大值
    public static int findMax(int[] arr, int L, int R) {
        if (L >= R) {
            return arr[L];
        }
        int mid = L + ((R - L) >> 1);
        int leftMax = findMax(arr, L, mid);
        int rightMax = findMax(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

   // 对数器
    public static int findMax(int[] arr) {
        int max = arr[0];
        if (arr.length == 1) {
            return max;
        }
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        return max;
    }

    public static int[] randomArr() {
        Random random = new Random();
        int length = random.nextInt(100) + 10;
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = random.nextInt(100);
        }
        return arr;
    }


    public static void main(String[] arg) {
        for (int i = 0; i < 1000; i++) {
            int[] randomArr = randomArr();
            int max = findMax(randomArr);
            int max1 = findMax(randomArr, 0, randomArr.length - 1);
            if (max != max1) {
                System.out.println("error max=" + max + " max1=" + max1);
                System.out.println(Arrays.toString(randomArr));
                return;
            }
        }
        System.out.println("success");

    }
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

这个递归方法复杂度 O(n)

哈希表

hashMap 哈希表。Java 哈希表底层是数组实现，通过哈希算法计算哈希值，映射到数组下标，实现查找、添加、删除 O(1)。

哈希冲突通过拉链法解决(常见方法还有 rehash 重哈希)，达到一定阈值进行扩容