经典题型

链表

有序链表合并

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
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;
    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }
    if (p1 != null) {
        p.next = p1;
    }
    if (p2 != null) {
        p.next = p2;
    }
    return dummy.next;
}

给定x分解单链表，使得小于x的数都在x之前

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
ListNode partition(ListNode head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode p1 = dummy1, p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    ListNode p = head;
    while (p != null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // 不能直接让 p 指针前进，
        // p = p.next
        // 断开原链表中的每个节点的 next 指针
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // 连接两个链表
    p1.next = dummy2.next;
    return dummy1.next;
}

返回链表的倒数第k个节点

快慢指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

寻找链表的中间节点

快慢指针法

1
2
3
4
5
6
7
8
9
10
11
12
ListNode middleNode(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
    }
    // 慢指针指向中点
    return slow;
}

判断链表是否包含环

快慢指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

如果链表有环，找到环的入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        // 上面的代码类似 hasCycle 函数
        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }
        // 重新指向头结点
        slow = head;
        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

判断两链表是否相交

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

反转整个链表

  • 递归法
1
2
3
4
5
6
7
8
9
10
// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next); // 除了头结点外，反转其余结点，last 为新的头结点
    head.next.next = head; // 其余节点反转好了，将反转后的链表的尾结点指向头节点
    head.next = null; // 头结点原本指向第二个元素，现在指向空节点
    return last; // 返回新的头结点
}

反转部分链表

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode successor = null; // 后驱节点
ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 reverseN
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}
// 反转以 head 为起点的前 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，反转前 n - 1 个节点
    ListNode last = reverse(head.next, n - 1); // 除了头节点，反转地 2-n 个节点，last 为第 n 个节点，也是新的头节点
    head.next.next = head; // 其余节点反转好了，将反转后的链表的尾结点指向头节点
    head.next = successor; // 让反转之后的 head 节点和后面的节点successor连起来
    return last; // 返回新的头结点
}

k 个一组翻转链表

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
ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    // 区间 [a, b) 包含 k 个待反转元素
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) return head;
        b = b.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverse(a, b);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k);
    return newHead;
}
// 反转区间 [a, b) 的元素，注意是左闭右开
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> originToClone = new HashMap<>();
        // 第一次遍历，先把所有节点克隆出来
        for (Node p = head; p != null; p = p.next) {
            if (!originToClone.containsKey(p)) {
                originToClone.put(p, new Node(p.val));
            }
        }
        // 第二次遍历，把克隆节点的结构连接好
        for (Node p = head; p != null; p = p.next) {
            if (p.next != null) {
                originToClone.get(p).next = originToClone.get(p.next);
            }
            if (p.random != null) {
                originToClone.get(p).random = originToClone.get(p.random);
            }
        }
        // 返回克隆之后的头结点
        return originToClone.get(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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class RemoveDuplicates {
    // Definition for singly-linked list.
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;

        while (current != null) {
            boolean isDuplicate = false;
            while (current.next != null && current.val == current.next.val) {
                isDuplicate = true;
                current = current.next;
            }
            if (isDuplicate) {
                prev.next = current.next;
            } else {
                prev = prev.next;
            }
            current = current.next;
        }
        return dummy.next;
    }
    // Utility function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // Read input
        int n = scanner.nextInt();
        if (n == 0) {
            System.out.println();
            return;
        }
        ListNode head = new ListNode(scanner.nextInt());
        ListNode current = head;
        for (int i = 1; i < n; i++) {
            current.next = new ListNode(scanner.nextInt());
            current = current.next;
        }
        // Process
        head = deleteDuplicates(head);
        // Output result
        printList(head);
    }
}

缓存淘汰策略

LRU缓存

LRU(Least Recently Used)策略是一种常见的缓存淘汰策略，它的核心思想是：如果数据最近被访问过，那么将来被访问的几率也更高。LRU 算法的实现可以通过哈希表和双向链表来完成。

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
// 方法 1
class LRUCache {
    // 缓存的容量
    private int cap;
    // 用LinkedHashMap作为cache，尾部为新使用过的数据，头部为未使用过的数据。
    private LinkedHashMap<Integer, Integer> cache;
    public LRUCache(int capacity) {
        this.cap = capacity;
        cache = new LinkedHashMap<>();
    }
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        makeNew(key);
        return cache.get(key);
    }
    public void put(int key, int value) {
        cache.put(key, value);
        makeNew(key);
        if (cache.size() > this.cap) {
            // 头部的元素是最老的
            int head = cache.keySet().iterator().next();
            cache.remove(head);
        }
    }
    // 让key变为新使用的数据
    private void makeNew(int key) {
        int value = cache.get(key);
        cache.remove(key);
        // 将key添加到LinkedHashMap尾部
        cache.put(key, value);
    }
}
// 方法 2
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    public LRUCache(int capacity) {
        super(capacity, 1f, true);
        this.capacity = capacity;
    }
    // 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(5);
        lruCache.put(1, "apple");
        lruCache.put(2, "banana");
        lruCache.put(3, "pear");
        lruCache.put(4, "watermelon");
        lruCache.put(5, "peach");
        System.out.println(lruCache);
        lruCache.put(6, "orange");
        System.out.println(lruCache);
        lruCache.get(4);
        System.out.println(lruCache);
    }

}

LFU淘汰策略

LFU(Least Frequently Used)策略是根据数据使用的频率来决定淘汰哪一个数据的策略。使用频率最少的数据会被淘汰。

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
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

class LFUCache {
    private final int capacity;  // 缓存的最大容量
    private int minFrequency;  // 当前缓存中最小的频率
    private final Map<Integer, Integer> valueMap;  // 存储键到值的映射
    private final Map<Integer, Integer> frequencyMap;  // 存储键到频率的映射
    private final Map<Integer, LinkedHashSet<Integer>> frequencyListMap;  // 存储频率到具有该频率的键集合的映射
    public LFUCache(int capacity) {
        this.capacity = capacity;  // 初始化缓存容量
        this.minFrequency = 0;  // 初始最小频率为0
        this.valueMap = new HashMap<>();  // 初始化键值映射表
        this.frequencyMap = new HashMap<>();  // 初始化键频率映射表
        this.frequencyListMap = new HashMap<>();  // 初始化频率到键集合的映射表
    }
    public int get(int key) {
        if (!valueMap.containsKey(key)) {  // 如果缓存中不包含该键，返回-1
            return -1;
        }
        int frequency = frequencyMap.get(key);  // 获取该键的当前频率
        frequencyMap.put(key, frequency + 1);  // 更新该键的频率
        frequencyListMap.get(frequency).remove(key);  // 从当前频率的键集合中移除该键

        // 如果当前频率的键集合为空且频率等于最小频率，移除该频率并增加最小频率
        if (frequencyListMap.get(frequency).isEmpty()) {
            frequencyListMap.remove(frequency);
            if (frequency == minFrequency) {
                minFrequency++;
            }
        }
        // 将该键添加到新的频率集合中
        frequencyListMap.computeIfAbsent(frequency + 1, k -> new LinkedHashSet<>()).add(key);
        return valueMap.get(key);  // 返回该键对应的值
    }
    public void put(int key, int value) {
        if (capacity <= 0) {  // 如果缓存容量为0或更小，直接返回
            return;
        }
        if (valueMap.containsKey(key)) {  // 如果键已存在，更新其值，并更新频率
            valueMap.put(key, value);
            get(key);  // 调用get方法来更新该键的频率
            return;
        }
        // 如果缓存已满，执行淘汰操作
        if (valueMap.size() >= capacity) {
            // 获取并移除最小频率集合中的第一个键
            int evictKey = frequencyListMap.get(minFrequency).iterator().next();
            frequencyListMap.get(minFrequency).remove(evictKey);
            if (frequencyListMap.get(minFrequency).isEmpty()) {  // 如果最小频率集合为空，移除该频率
                frequencyListMap.remove(minFrequency);
            }
            valueMap.remove(evictKey);  // 从键值映射表中移除被淘汰的键
            frequencyMap.remove(evictKey);  // 从键频率映射表中移除被淘汰的键
        }
        // 插入新键值对，初始频率为1
        valueMap.put(key, value);
        frequencyMap.put(key, 1);
        minFrequency = 1;  // 插入新键后，最小频率重置为1
        // 将新键添加到频率为1的集合中
        frequencyListMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
    }
}

FIFO淘汰策略

FIFO(First In First Out)策略是根据数据进入缓存的顺序来决定淘汰哪一个数据的策略。最早进入缓存的数据会被淘汰。

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
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class FIFOCache {
    private final int capacity;
    private final Map<Integer, Integer> map;
    private final Queue<Integer> queue;
    public FIFOCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.queue = new LinkedList<>();
    }
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            return;
        }
        if (map.size() >= capacity) {
            int evictKey = queue.poll();
            map.remove(evictKey);
        }
        map.put(key, value);
        queue.add(key);
    }
}

排序算法

链接：https://learn.skyofit.com/archives/1291

复杂度
排序算法总结

概念：

  • 稳定：如果a原本在b前面且a=b，排序之后a仍然在b的前面。
  • 不稳定：如果a原本在b的前面且a=b，排序之后 a 可能会出现在 b 的后面。
  • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
  • 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
  • In-Place：占用常数内存，不占用额外内存。比如：程序里没有创建新数组来保存数据，只用了临时变量。
  • Out-Place：占用额外内存。比如：创建了新的数组来保存或者处理数据。

冒泡排序

基本思想
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为每趟比较将当前数列未排序部分的最大的元素“沉”到数列末端，而小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

  1. 比较相邻的元素。如果前一个比后一个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。为了优化算法，可以设立一个布尔标识，每趟排序开始前设为false，如果该趟排序发生了交换就置为true，如果一趟排序结束标识仍为false表示该趟排序没有发生交换，即数组已经有序，可以提前结束排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int[] bubbleSort(int[] array) {
    if (array.length == 0)
        return array;
    for (int i = 0; i < array.length; i++){  //外层循环一次为一趟排序
        /*设置标识，判断这趟排序是否发生了交换。
       如果未发生交换，则说明数组已经有序，不必再排序了*/
        boolean isSwap = false;
        //内层循环一次为一次相邻比较
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j + 1] < array[j]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                isSwap = true;
            }
        }
        if (!isSwap)
            break;
    }
    return array;
}
  • 时间复杂度：冒泡排序平均时间复杂度为O(n2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n2)。
  • 最好情况：如果待排序元素本来是正序的，那么一趟冒泡排序就可以完成排序工作，比较和移动元素的次数分别是 (n – 1) 和 0，因此最好情况的时间复杂度为O(n)。
  • 最坏情况：如果待排序元素本来是逆序的，需要进行 (n – 1) 趟排序，所需比较和移动次数分别为 n * (n – 1) / 2和 3 * n * (n-1) / 2。因此最坏情况下的时间复杂度为O(n2)。
  • 空间复杂度：冒泡排序使用了常数空间，空间复杂度为O(1)
  • 稳定性：当 array[j] == array[j+1] 的时候，不交换 array[i] 和 array[j]，所以冒泡排序是稳定的。

拓展：鸡尾酒排序
又称定向冒泡排序、搅拌排序等，是对冒泡排序的改进。在把最大的数往后面冒泡的同时，把最小的数也往前面冒泡，同时收缩无序区的左右边界，有序区在序列左右逐渐累积。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void cocktailSort(int[] array) {
   int left = 0,right = array.length-1;
   while(left < right) {
       for(int i = left; i < right; i++)
         if(array[i] > array[i+1])
               swap(array,i,i + 1);
       right--;
       for(int i = right; i > left; i--)
         if(array[i] < array[i-1])
               swap(array,i,i-1);
       left++;
   }
}

鸡尾酒排序是稳定的。它的平均时间复杂度为O(n2)，最好情况是待排序列原先就是正序的，时间复杂度为O(n)，最坏情况是待排序列原先是逆序的，时间复杂度为O(n2)。空间复杂度为O(1)。

选择排序

基本思想
简单选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述
n个记录的简单选择排序可经过(n-1)趟简单选择排序得到有序结果。具体算法描述如下：

  1. 初始状态：无序区为R[1..n]，有序区为空；
  2. 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  3. (n-1)趟结束，数组有序化了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int[] selectionSort(int[] array) {
    if (array.length == 0)
         return array;
    for (int i = 0; i < array.length; i++) {
        int minIndex = i;
        for (int j = i; j < array.length; j++) {
            if (array[j] < array[minIndex]) //找到最小的数
                minIndex = j; //将最小数的索引保存
        }
        int temp = array[minIndex]; //将最小数和无序区的第一个数交换
        array[minIndex] = array[i];
        array[i] = temp;
    }
    return array;
}
  • 时间复杂度：简单选择排序平均时间复杂度为O(n2)，最好时间复杂度为O(n2)，最坏时间复杂度为O(n2)。
  • 最好情况：如果待排序元素本来是正序的，则移动元素次数为 0，但需要进行 n * (n – 1) / 2 次比较。
  • 最坏情况：如果待排序元素中第一个元素最大，其余元素从小到大排列，则仍然需要进行 n * (n – 1) / 2 次比较，且每趟排序都需要移动 3 次元素，即移动元素的次数为3 * (n – 1)次。
    • 需要注意的是，简单选择排序过程中需要进行的比较次数与初始状态下待排序元素的排列情况无关。
  • 空间复杂度：简单选择排序使用了常数空间，空间复杂度为O(1)
  • 稳定性：简单选择排序不稳定，比如序列 2、4、2、1，知道第一趟排序第 1 个元素 2 会和 1 交换，那么原序列中 2 个 2 的相对前后顺序就被破坏了，所以简单选择排序不是一个稳定的排序算法。

直接插入排序

基本思想
直接插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述
一般来说，直接插入排序都采用in-place(原地算法)在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素(已排序)大于新元素，将该元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2~5。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int[] insertionSort(int[] array) {
    if (array.length == 0)
        return array;
    int current;
    for (int i = 1; i < array.length; i++) {
        current = array[i];
        int preIndex = i - 1;
        while (preIndex >= 0 && current < array[preIndex]) {
            array[preIndex + 1] = array[preIndex];
            preIndex--;
        }
        array[preIndex + 1] = current;
    }
    return array;
}
  • 时间复杂度：直接插入排序平均时间复杂度为O(n2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n2)。
  • 最好情况：如果待排序元素本来是正序的，比较和移动元素的次数分别是 (n – 1) 和 0，因此最好情况的时间复杂度为O(n)。
  • 最坏情况：如果待排序元素本来是逆序的，需要进行 (n – 1) 趟排序，所需比较和移动次数分别为 n * (n – 1) / 2和 n * (n – 1) / 2。因此最坏情况下的时间复杂度为O(n2)。
  • 空间复杂度：直接插入排序使用了常数空间，空间复杂度为O(1)
  • 稳定性：直接插入排序是稳定的。

拓展：在直接插入排序中，待插入的元素总是在有序区线性查找合适的插入位置，没有利用有序的优势，考虑使用二分查找搜索插入位置进行优化，即二分插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] BinaryInsertionSort(int[] array) {
    if (array.length == 0)
        return array;
    for(int i = 1;i < array.length;i++) {
        int left = 0;
        int right = i - 1;  // left 和 right 分别为有序区的左右边界 
        int current = array[i];
        while (left <= right) {
            //搜索有序区中第一个大于 current 的位置，即为 current 要插入的位置
            int mid = left + ((right - left) >> 1);
            if(array[mid] > current){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        for(int j = i - 1;j >= left;j--) {
            array[j + 1] = array[j];
        }
        array[left] = current; // left 为第一个大于 current 的位置，插入 current
    }
    return array;
}

二分插入排序是稳定的。它的平均时间复杂度是O(n2)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n2)。

希尔排序

基本思想
1959年Shell发明，第一个突破O(n2)的排序算法，是直接插入排序的改进版。它与直接插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述
先将整个待排元素序列分割成 gap 个增量为 gap 的子序列(每个子序列由位置相差为 gap 的元素组成，整个序列正好分割成 gap 个子序列，每个序列中有 n / gap 个元素)分别进行直接插入排序，然后缩减增量为之前的一半再进行排序，待 gap == 1时，希尔排序就变成了直接插入排序。因为此时序列已经基本有序，直接插入排序在元素基本有序的情况下(接近最好情况)，效率是很高的。gap初始值一般取 len / 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int[] ShellSort(int[] array) {
    int len = array.length;
    if(len == 0)
        return array;
    int current, gap = len / 2;
    while (gap > 0) {
        for (int i = gap; i < len; i++) {
            current = array[i];
            int preIndex = i - gap;
            while (preIndex >= 0 && array[preIndex] > current) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }
            array[preIndex + gap] = current;
        }
        gap /= 2;
    }
    return array;
}
  • 时间复杂度：希尔排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlog2n)，最坏时间复杂度为O(nlog2n)。希尔排序的时间复杂度与增量序列的选取有关。
  • 空间复杂度：希尔排序使用了常数空间，空间复杂度为O(1)
  • 稳定性：由于相同的元素可能在各自的序列中插入排序，最后其稳定性就会被打乱，比如序列 2、4、1、2，所以希尔排序是不稳定的。

归并排序

基本思想
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

  1. 把长度为 n 的输入序列分成两个长度为 n / 2 的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。
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
// 归并排序
public static int[] MergeSort(int[] array) {
    if (array.length < 2) return array;
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    return merge(MergeSort(left), MergeSort(right));
}
// 将两段有序数组结合成一个有序数组
public static int[] merge(int[] left, int[] right) {
   int[] result = new int[left.length + right.length];
   int i = 0,j = 0,k = 0;
   while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result[k++] = left[i++];
        } else {
            result[k++] = right[j++];
        }
    }
    while (i < left.length) {
        result[k++] = left[i++];
    }
    while (j < right.length) {
        result[k++] = right[j++];
    }
    return result;
}
  • 时间复杂度：归并排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它在任何情况下时间复杂度均是O(nlogn)。
  • 空间复杂度：归并排序空间复杂度为O(n)
  • 稳定性：归并排序是稳定的。

快速排序

基本思想
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述
快速排序使用分治法来把一个数列分为两个子数列。具体算法描述如下：

  1. 从数列中挑出一个元素，称为 “基准”(pivot)；
  2. 重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面(相同的数可以到任一边)，该基准就处于数列的中间位置。这称为分区(partition)操作；
  3. 递归地(recursive)对小于基准值元素的子数列和大于基准值元素的子数列进行快速排序。

代码实现
快速排序最核心的步骤就是partition操作，即从待排序的数列中选出一个数作为基准，将所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面(相同的数可以到任一边)，该基准就处于数列的中间位置。partition函数返回基准的位置，然后就可以对基准位置的左右子序列递归地进行同样的快排操作，从而使整个序列有序。

两种方法：左右指针法、挖坑法
左右指针法：

  1. 将数组的最后一个数 right 作为基准数 key。
  2. 分区过程：从数组的首元素 begin 开始向后找比 key 大的数(begin 找大)；end 开始向前找比 key 小的数(end 找小)；找到后交换两者(swap)，直到 begin >= end 终止遍历。最后将 begin(此时begin == end)和最后一个数交换( 这个时候 end 不是最后一个位置)，即 key 作为中间数(左区间都是比key小的数，右区间都是比key大的数)
  3. 再对左右区间重复第二步，直到各区间只有一个数。
    左右指针法
    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
    public class Demo {
        public static void main(String[] args) {
            int[] a = {3, 5, 8, 1, 2, 9, 4, 7, 6};
            sort(a, 0, a.length - 1);
            for(int i = 0; i < a.length; i++){
                System.out.print(a[i] + ",");
            }
        }
        // left 数列左边界 right 数列右边界
        public static void sort(int[] array,int left,int right) {
            int p = left;
            int q = right;
            int key = right;
            if(left >= right)
                return;
            while( p < q ) {
                //p找大
                while(p < q && array[p] <= array[key])
                    p++;
                //q找小
                while(p < q && array[q] >= array[key])
                    q--;
                if(p < q)
                    swap(array, p, q);
            }
            swap(array, p, key);
            sort(array, left, p - 1);
            sort(array, q + 1, right);
        }
        // 交换数组内两个元素
        public static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    挖坑法：
  4. 定义两个指针 left 指向起始位置，right 指向最后一个元素的位置，然后指定一个基准 key(right)，作为坑。
  5. left 寻找比基准(key)大的数字，找到后将 left 的数据赋给 right，left 成为一个坑，然后 right 寻找比基数(key)小的数字，找到将 right 的数据赋给 left，right 成为一个新坑，循环这个过程，直到 begin 指针与 end指针相遇，然后将 key 填入那个坑(最终：key的左边都是比key小的数，key的右边都是比key大的数)，然后进行递归操作。
    挖坑法
    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
    // 快速排序方法 left 数列左边界 right 数列右边界
    public static void Quicksort(int array[], int left, int right) {
        if (left < right){
            int pos = partition(array, left, right);
            Quicksort(array, left, pos - 1);
            Quicksort(array, pos + 1, right);
        }
    }
    // partition操作
    public static int partition(int[] array,int left,int right) {
        int key = array[right];//初始坑
        while(left < right) {
            //left找大
            while(left < right && array[left] <= key )
                left++;
            array[right] = array[left];//赋值，然后left作为新坑
            //right找小
            while(left <right && array[right] >= key)
                right--;
            array[left] = array[right];//right作为新坑
        }
        array[left] = key;
        /*将key赋值给left和right的相遇点，保持key的左边都是比key小的数，key的右边都是比key大的数*/
        return left;//最终返回基准
    }
优化

之前选择基准的策略都是固定基准，即固定地选择序列的右边界值作为基准，但如果在待排序列几乎有序的情况下，选择的固定基准将是序列的最大(小)值，快排的性能不好(因为每趟排序后，左右两个子序列规模相差悬殊，大的那部分最后时间复杂度很可能会达到O(n2))。

优化一：随机基准
每次随机选取基准值，而不是固定选取左或右边界值。将随机选取的基准值和右边界值进行交换，然后就回到了之前的解法。
只需要在 partition 函数前增加如下操作即可：

1
2
3
4
//随机选择 left ~ right 之间的一个位置作为基准
int random = (int) (left + Math.random() * (right - left + 1));
//把基准值交换到右边界
swap(array, random, right);

优化二：三数取中法
取第一个数，最后一个数，第(N/2)个数即中间数，三个数中数值中间的那个数作为基准值。

举个例子，对于int[] array = { 2，5，4，9，3，6，8，7，1，0}，2、3、0分别是第一个数，第(N/2)个是数以及最后一个数，三个数中3最大，0最小，2在中间，所以取2为基准值。

实现getMid函数即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 三数取中，返回array[left]、array[mid]、array[right]三者的中间者下标作为基准
public static int getMid(int[] array,int left,int right) {
    int mid = left + ((right - left) >> 1);
    int a = array[left];
    int b = array[mid];
    int c = array[right];
    if ((b <= a && a <= c) || (c <= a && a <= b)) { //a为中间值
        return left;
    }
    if ((a <= b && b <= c) || (c <= b && b <= a)) { //b为中间值
        return mid;
    }
    if ((a <= c && c <= b) || (b <= c && c <= a)) { //c为中间值
        return right;
    }
    return left;
}

优化三：当待排序序列的长度分割到一定大小后，使用插入排序
在子序列比较小的时候，直接插入排序性能较好，因为对于有序的序列，插排可以达到O(n)的复杂度，如果序列比较小，使用插排效率要比快排高。

实现方式也很简单，快排是在子序列元素个数为 1 时才停止递归，可以设置一个阈值n，假设为5，则大于5个元素，子序列继续递归，否则选用插排。

此时QuickSort()函数如下：

1
2
3
4
5
6
7
8
9
public static void Quicksort(int array[], int left, int right) {
    if(right - left > 5){
        int pos = partition(array, left, right);
        Quicksort(array, left, pos - 1);
        Quicksort(array, pos + 1, right);
    }else{
        insertionSort(array);
    }
}

优化四：三路划分
如果待排序列中重复元素过多，也会大大影响排序的性能，这是因为大量相同元素参与快排时，左右序列规模相差极大，快排将退化为冒泡排序，时间复杂度接近O(n2)。这时候，如果采用三路划分，则会很好的避免这个问题。

三路划分的思想是利用 partition 函数将待排序列划分为三部分：第一部分小于基准v，第二部分等于基准v，第三部分大于基准v。这样在递归排序区间的时候，就不必再对第二部分元素均相等的区间进行快排了，这在待排序列存在大量相同元素的情况下能大大提高快排效率。
三路划分示意图

红色部分为小于基准v的序列，绿色部分为等于基准v的序列，白色部分由于还未被 cur 指针遍历到，属于大小未知的部分，蓝色部分为大于基准v的序列。

left 指针为整个待排区间的左边界，right 指针为整个待排区间的右边界。less 指针指向红色部分的最后一个数(即小于v的最右位置)，more 指针指向蓝色部分的第一个数(即大于v的最左位置)。cur 指针指向白色部分(未知部分)的第一个数，即下一个要判断大小的位置。

算法思路：

  1. 由于最初红色和蓝色区域没有元素，初始化 less = left – 1，more = right + 1，cur = left。整个区间为未知部分(白色)。
  2. 如果当前 array[cur] < v，则 swap(array,++less,cur++)，即把红色区域向右扩大一格(less指针后移)，把 array[cur] 交换到该位置，cur 指针前移判断下一个数。
  3. 如果当前 array[cur] = v，则不必交换，直接 cur++
  4. 如果当前 array[cur] > v，则 swap(array,–more,cur)，即把蓝色区域向左扩大一格(more指针前移)，把 array[cur] 交换到该位置。特别注意！此时cur指针不能前移，这是因为交换到cur位置的元素来自未知区域，还需要进一步判断array[cur]。
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
public static int[] partition(int[] array,int left,int right){
    int v = array[right]; //选择右边界为基准
    int less = left - 1; // < v 部分的最后一个数
    int more = right + 1; // > v 部分的第一个数
    int cur = left;
    while(cur < more){
        if(array[cur] < v){
            swap(array,++less,cur++);
        }else if(array[cur] > v){
            swap(array,--more,cur);
        }else{
            cur++;
        }
    }
    return new int[]{less + 1,more - 1};  //返回的是 = v 区域的左右下标
}
// 交换数组内两个元素
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
public static void Quicksort(int array[], int left, int right) {
    if (left < right) {
        int[] p = partition(array,left,right);
        Quicksort(array,left,p[0] - 1); //避开重复元素区间
        Quicksort(array,p[1] + 1,right);
    }
}
  • 时间复杂度：快速排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n2)。
  • 最好情况：基准选择得当，partition函数每次恰好能均分序列，其递归树的深度就为logn，时间复杂度为O(nlogn)。
  • 最坏情况：选择了最大或者最小数字作为基准，每次划分只能将序列分为一个元素与其他元素两部分，此时快速排序退化为冒泡排序，如果用树画出来，得到的将会是一棵单斜树，即所有的结点只有左(右)结点的树，树的深度为 n，时间复杂度为O(n2)。
  • 空间复杂度：快速排序的空间复杂度主要考虑递归时使用的栈空间。在最好情况下，即partition函数每次恰好能均分序列，空间复杂度为O(logn)；在最坏情况下，即退化为冒泡排序，空间复杂度为O(n)。平均空间复杂度为O(logn)。
  • 稳定性：快速排序是不稳定的。

堆排序

基本思想
堆排序是一种树形选择排序方法，它利用了堆这种数据结构。在排序的过程中，将array[0，…，n-1]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的关系，在当前无序区中选择关键字最大(最小)的元素。

算法描述

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为(n-1)，则整个排序过程完成。
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
//声明全局变量，用于记录数组array的长度；
static int len;
// 堆排序算法
public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len == 0) return array;
        //1.构建一个大根堆
        buildMaxHeap(array);
        //2.循环将堆顶(最大值)与堆尾交换，删除堆尾元素，然后重新调整大根堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--; //原先的堆尾进入有序区，删除堆尾元素
            adjustHeap(array, 0); //重新调整大根堆
        }
        return array;
 }
// 自顶向下调整以 i 为根的堆为大根堆
public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (2 * i + 1 < len && array[2 * i + 1] > array[maxIndex])
            maxIndex = 2 * i + 1;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (2 * i + 2 < len && array[2 * i + 2] > array[maxIndex])
            maxIndex = 2 * i + 2;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
 }
 // 自底向上构建初始大根堆
 public static void buildMaxHeap(int[] array) {
        //从最后一个非叶子节点开始自底向上构造大根堆
        for (int i = (len - 2) / 2; i >= 0; i--) {
            adjustHeap(array, i);
        }
 }
 // 交换数组内两个元素
public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
  • 拓展：
    • 插入元素：只需要把待插入的元素放置在堆尾，然后 len++ 把其纳入堆，然后调用 adjustHeap 函数重新调整堆即可。
    • 删除堆顶元素：只需要把堆顶元素交换到堆尾，然后 len– 把其移出堆，然后调用 adjustHeap 函数重新调整堆即可。
  • 时间复杂度：堆排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。堆排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它在任何情况下时间复杂度均是O(nlogn)。
  • 空间复杂度：堆排序使用了常数空间，空间复杂度为O(1)。
  • 稳定性：堆排序是不稳定的。

计数排序

基本思想
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

  1. 找出待排序的数组中最大和最小的元素；
  2. 统计数组中每个值为 i 的元素出现的次数，存入数组C的第i项；
  3. 对所有的计数累加(从C中的第一个元素开始，每一项和前一项相加)；
  4. 反向填充目标数组：将每个元素 i 放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
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
public static int[] CountingSort(int[] array) {
    if (array.length == 0) return array;
    int bias, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
        max = Math.max(max, array[i]);
        min = Math.min(min, array[i]);
    }
   //计算偏移量，将 min ~ max 映射到 bucket 数组的 0 ~ (max - min) 位置上
    bias = -min;
    int[] bucket = new int[max - min + 1];
    Arrays.fill(bucket, 0);
    for (int i = 0; i < array.length; i++) {
        bucket[array[i] + bias]++;
    }
    int index = 0, i = 0;
    while (index < array.length) {
        if (bucket[i] != 0) {
            array[index] = i - bias;
            bucket[i]--;
            index++;
        } else
            i++;
    }
    return array;
}
  • 时间复杂度：计数排序平均时间复杂度为O(n + k)，最好时间复杂度为O(n + k)，最坏时间复杂度为O(n + k)。n 为遍历一趟数组计数过程的复杂度，k 为遍历一趟桶取出元素过程的复杂度。
  • 空间复杂度：计数排序空间复杂度为O(k)，k为桶数组的长度。
  • 稳定性：计数排序是稳定的。

桶排序

基本思想
桶排序与计数排序很相似，不过现在的桶不单计数，是实实在在地放入元素。按照映射函数将数据分配到不同的桶里，每个桶内元素再分别排序(可能使用别的排序算法)，最后拼接各个桶中排好序的数据。映射函数人为设计，但要保证桶 i 中的数均小于桶 j (i < j)中的数，即必须桶间必须有序，桶内可以无序，可以考虑按照数的区间范围划分桶。下面代码的桶映射函数为：(i – min) / arr.length。

算法描述

  1. 设置一个定量的数组当作空桶；
  2. 遍历输入数据，并且把数据一个一个放到对应的桶里去；
  3. 对每个不是空的桶的桶内元素进行排序(可以使用直接插入排序等)；
  4. 从不是空的桶里把排好序的数据拼接起来。
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
public static int[] bucketSort(int[] array){
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < array.length; i++){
        max = Math.max(max, array[i]);
        min = Math.min(min, array[i]);
    }
    /*桶映射函数：自己设计，要保证桶 i 的数均小于桶 j (i < j)的数，即必须桶间必须有序，桶内可以无序。这里桶映射函数为：(i - min) / arr.length*/
    int bucketNum = (max - min) / array.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    //将每个元素放入桶
    for(int i = 0; i < array.length; i++){
        int num = (array[i] - min) / (array.length);
        bucketArr.get(num).add(array[i]);
    }
    //对每个桶进行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
   int k = 0;
   for(int i = 0; i < bucketArr.size(); i++){
      for(int j = 0;j < bucketArr.get(i).size();j++) {
           array[k++] = bucketArr.get(i).get(j);
      }
  }
  return array;
}
  • 时间复杂度：桶排序平均时间复杂度为O(n + k)，最好时间复杂度为O(n + k)，最坏时间复杂度为O(n2)。
  • 空间复杂度：桶排序空间复杂度为O(n + k)。
  • 稳定性：桶排序是稳定的。

基数排序

基本思想
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

  1. 取得数组中的最大数，并取得位数；
  2. array 为原始数组，从最低位开始取每个位组成 radix 数组；
  3. 对 radix 进行计数排序(利用计数排序适用于小范围数的特点)；
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
public static int[] RadixSort(int[] array) {
     if (array == null || array.length < 2)
        return array;
        // 1.先算出最大数的位数；
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
    }
    int maxDigit = 0;
    while (max != 0) {
            max /= 10;
            maxDigit++;
    }
    int div = 1;
    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
    for (int i = 0; i < 10; i++)
        bucketList.add(new ArrayList<Integer>());
        //2.进行maxDigit趟分配
    for (int i = 0; i < maxDigit; i++,div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] / div) % 10;
                bucketList.get(num).add(array[j]);
            }
        //3.收集
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    array[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
   }
   return array;
}
  • 时间复杂度：基数排序平均时间复杂度为O(n * k)，最好时间复杂度为O(n * k)，最坏时间复杂度为O(n * k)。
  • 空间复杂度：基数排序空间复杂度为O(n + k)。
  • 稳定性：基数排序是稳定的。

二分查找

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
public class BinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止整形的(left + right)/2溢出
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 未找到目标值
    }
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(array, target);
        System.out.println("目标值的索引: " + result);
    }
}

// 递归实现
public class BinarySearch {
    public static int binarySearch(int[] array, int target, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            return binarySearch(array, target, mid + 1, right);
        } else {
            return binarySearch(array, target, left, mid - 1);
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(array, target, 0, array.length - 1);
        System.out.println("目标值的索引: " + result);
    }
}

递归删除文件夹

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
import java.io.File;
public class FileDeleter {
    public static void main(String[] args) {
        // 示例：删除路径为"example"的文件或目录
        String path = "example";
        boolean result = deleteRecursively(new File(path));
        if (result) {
            System.out.println("删除成功: " + path);
        } else {
            System.out.println("删除失败: " + path);
        }
    }

    /**
     * 递归删除文件或目录
     * @param file 要删除的文件或目录
     * @return 如果成功删除，则返回true；否则返回false
     */
    public static boolean deleteRecursively(File file) {
        if (!file.exists()) {
            System.out.println("文件不存在: " + file.getAbsolutePath());
            return false;
        }
        // 如果是目录，则递归删除目录中的内容
        if (file.isDirectory()) {
            File[] files = file.listFiles();
            if (files != null) {
                for (File child : files) {
                    if (!deleteRecursively(child)) {
                        return false;
                    }
                }
            }
        }
        // 删除文件或空目录
        return file.delete();
    }
}

无重复最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        // 滑动窗口
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            // 增大窗口
            right++;
            // 窗口变化后对数据进行处理
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 是否需要缩小窗口
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 窗口变化后对数据进行处理
                window.put(d, window.get(d) - 1);
            }
            // 缩小窗口后保证window内没有重复元素
            res = Math.max(right - left, res);
        }
        return res;
    }
}

两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

三数之和

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
class Solution {
    // 从 nums[start] 开始，计算有序数组 nums 中所有和为 target 的二元组
    private List<List<Integer>> towSum(int[] nums, int start, int target) {
        int low = start, high = nums.length - 1;
        // Arrays.sort(nums); // 先排序
        List<List<Integer>> res = new ArrayList<>();
        while (low < high) {
            int sum = nums[low] + nums[high];
            int left = nums[low], right = nums[high]; // 用来标记左右元素，对比重复元素
            if (sum < target) {
                while (low < high && nums[low] == left) low++;
            } else if (sum > target) {
                while (low < high && nums[high] == right) high--;
            } else {
                res.add(new ArrayList<>(Arrays.asList(left, right)));
                while (low < high && nums[low] == left) low++;
                while (low < high && nums[high] == right) high--;
            }
        }
        return res;
    }
    public List<List<Integer>> threeSum(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums); // 先排序
        List<List<Integer>> res = new ArrayList<>();
        // 先穷举第一个数
        for (int i = 0; i < n; i++) {
            // 对 target - nums[i] 计算 twoSum
            List<List<Integer>> twoSumRes = towSum(nums, i+1, target -nums[i]);
            // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
            for (List<Integer> tuple : twoSumRes) {
                tuple.add(nums[i]);
                res.add(tuple);
            }
            // 跳过第一个数字重复的情况
            while (i < n-1 && nums[i] == nums[i+1]) i++;
        }
        return res;
    }
}

最接近的三数之和

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
import java.util.*;
public class Solution {
    public int ClosestSum (int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        int delta = Integer.MAX_VALUE;
        for (int i = 0; i < n - 2; i++) {
            // 固定nums[i],从i+1开始
            int sum = nums[i] + ClosestSum2(nums, i + 1, target - nums[i]);
            if (Math.abs(delta) > Math.abs(target - sum)) {
                delta = target - sum;
                if (delta == 0) {
                    break;
                }
            }
        }
        return target - delta;
    }
    // 最接近的两数之和
    private int ClosestSum2 (int[] nums, int start, int target) {
        int low = start;
        int high = nums.length - 1;
        int delta = Integer.MAX_VALUE;
        while (low < high) {
            int sum = nums[low] + nums[high];
            if (Math.abs(delta) > Math.abs(target - sum)) {
                delta = target - sum;
                if (delta == 0) {
                    break;
                }
            }
            if (sum < target) {
                low++;
            } else {
                high--;
            }
        }
        return target - delta;
    }
}

接雨水

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
// 暴力解法，备忘录优化
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int res = 0;
        // 备忘录记录每个位置左右柱子高度的最大值
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        l_max[0] = height[0];
        r_max[n-1] = height[n-1];
        // 从左到右计算l_max
        for (int i = 1; i < n; i++) {
            l_max[i] = Math.max(height[i], l_max[i-1]);
        }
        // 从右往左计算r_max
        for (int i = n-2; i >= 0; i--) {
            r_max[i] = Math.max(height[i], r_max[i+1]);
        }
        // 计算答案
        for (int i = 1; i < n-1; i++) {
            res += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return res;
    }
}
// 双指针法
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        int res = 0;
        int left = 0, right = height.length - 1;
        int l_max = 0, r_max = 0;
        while (left < right) {
            l_max = Math.max(l_max, height[left]);
            r_max = Math.max(r_max, height[right]);
            if (l_max < r_max) {
                res += l_max - height[left];
                left++;
            } else {
                res += r_max - height[right];
                right--;
            }
        }
        return res;
    }
}

滑动窗口最大值

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
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n-k+1];
        int resIndex = 0;
        // pq 存储元素值及索引
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return b[0] - a[0];
            }
        });
        for (int i = 0; i < n; i++) {
            // 将当前元素及其索引添加到 pq 中
            pq.offer(new int[]{nums[i], i});
            // 根据 index 移除掉超出的元素
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            // 当窗口大小达到 k 时，记录当前窗口的最大值
            if (i >= k - 1) {
                res[resIndex++] = pq.peek()[0];
            }
        }
        return res;
    }
}

判断是否是质数

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 动态规划
public int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // 定义：dp[i] 记录以 nums[i] 为结尾的「最大子数组和」
    int[] dp = new int[n];
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    // dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
    }
    // 得到 nums 的最大子数组
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int sum = 0;
        // 滑动窗口
        while (right < n) {
            sum += nums[right];
            // 滑动窗口缩小条件
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left];
                // 缩小窗口
                left++;
            }
            // 增大窗口
            right++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

最长回文子串

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

    public String palindrome(String s, int l, int r) {
        while (l >= 0 && r <= s.length() -1 && s.charAt(l) == s.charAt(r)) {
            l --;
            r ++;
        }
        // 注意这里的l+1，原因是前面的while循环在s.charAt(l) == s.charAt(r)执行之前会l--和r++，在不满足前面条件时，已经进行了l--和r++，所以需要加回来。
        return s.substring(l+1, r);
    }
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i ++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);
            // res = longest(res, s1, s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }
}

最长回文子序列

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
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // 定义dp[i][j]为 s[i..j]之间的最长回文子序列
        int[][] dp = new int[n][n];
        // base case
        // 每个字符处，最长回文子序列为其本身，长度1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        // i > j处，不存在子序列，全部为0
        for (int i = n-2; i >= 0; i--) {
            for (int j = i+1; j < n; j++) {
                // 状态转移函数
                if (s.charAt(i) == s.charAt(j)) {
                    // 如果s在i处的字符和s在j处的字符相等，则两字符同时加入dp[i+1][j-1],长度+2
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    // 如果不相等，则两字符不能同时出现在最长回文子序列中，把两个字符都加入，看看哪个更长
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }

            }
        }
        return dp[0][n-1];
    }
}

最长公共子序列

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
class Solution {
    // 备忘录
    private int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        memo = new int[text1.length()][text2.length()];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(text1, 0, text2, 0);
    }
    // 定义dp[s1, i, s2, j]为s1[i..]和s2[j..]的最长公共子序列
    private int dp(String s1, int i, String s2, int j) {
        // base case
        // 相当于是s1 最右边的空串 和s2 最右边的空串的最长公共子序列，为0
        if (i == s1.length() || j == s2.length()) return 0;
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 状态转移函数
        if (s1.charAt(i) == s2.charAt(j)) {
            // 如果s1在i处的字符和s2在j处的字符相等，则该字符必定属于最长公共子序列，长度+1，s1、s2都前进向下一字符比较
            memo[i][j] = 1 + dp(s1, i+1, s2, j+1);
        } else {
            // 如果s1在i处的字符和s2在j处的字符不相等，三种情况:
            // 1. s1在i处的字符不属于最长公共子序列，但s2所在j处的字符属于最长公共子序列，则s1前进至下一字符
            // 2. s2在j处的字符不属于最长公共子序列，但s1所在i处的字符属于最长公共子序列，则s2前进至下一字符
            // 3. s1在i处的字符和s2在j处的字符都不属于最长公共子序列，但这种情况下最长公共子序列的长度肯定没有前两种长，忽略dp(s1, i+1, s2, j+1)
            memo[i][j] = Math.max(dp(s1, i+1, s2, j), dp(s1, i, s2, j+1));
        }
        return memo[i][j];
    }
}

二叉树

二叉树前序遍历转链表

二叉树的先序遍历，然后按照前序顺序将其转化为一个链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    private static Node trans(TreeNode root) {
        Node dummy = new Node(-1), p = dummy;
        traverse(root, p);
        return dummy.next;
    }
    private static void traverse(TreeNode root, Node p) {
        if (root == null)
            return ;
        Node node = new Node(root.val, null);
        p.next = node;
        p = p.next;
        traverse(root.left, p);
        traverse(root.right, p);
    }
}

有序数组转二叉平衡搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 递归构造平衡二叉搜索树
        return dfs(nums, 0, nums.length - 1);
    }
    private TreeNode dfs(int[] nums, int low, int high) {
        if (low > high) {
            return null;
        }
        int mid = low + (high - low)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums, low, mid-1);
        root.right = dfs(nums, mid+1, high);
        return root;
    }
}

根据前序和中序遍历构造二叉树

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
class Solution {
    // 存储 inorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    private TreeNode build(int[] preOrder, int preStart, int preEnd, int[] inOrder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preOrder[preStart];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 左子树的节点数量
        int leftSize = index - inStart;
        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        root.left = build(preOrder, preStart + 1, preStart + leftSize, inOrder, inStart, index - 1);
        root.right = build(preOrder, preStart + leftSize + 1, preEnd, inOrder, index + 1, inEnd);
        return root;
    }
}

根据中序和后序遍历构造二叉树

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
class Solution {
    // 存储 inorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }
    // build 函数的定义：
    // 后序遍历数组为 postorder[postStart..postEnd]，
    // 中序遍历数组为 inorder[inStart..inEnd]，
    // 构造二叉树，返回该二叉树的根节点 
    TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd) {
            return null;
        }
        // root 节点对应的值就是后序遍历数组的最后一个元素
        int rootVal = postorder[postEnd];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 左子树的节点个数
        int leftSize = index - inStart;
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);
        root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
}

根据前序和后序遍历构造二叉树

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
class Solution {
    // 存储 postorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            valToIndex.put(postorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1,
                    postorder, 0, postorder.length - 1);
    }
    // 定义：根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]
    // 构建二叉树，并返回根节点。
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // root.left 的值是前序遍历第二个元素
        // 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点
        // 确定 preorder 和 postorder 中左右子树的元素区间
        int leftRootVal = preorder[preStart + 1];
        // leftRootVal 在后序遍历数组中的索引
        int index = valToIndex.get(leftRootVal);
        // 左子树的元素个数
        int leftSize = index - postStart + 1;
        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        // 根据左子树的根节点索引和元素个数推导左右子树的索引边界
        root.left = build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index);
        root.right = build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1);
        return root;
    }
}

迭代实现二叉树前序遍历

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
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            result.add(current.val); // 前序遍历的操作
            // 将右子树和左子树添加到栈中，注意顺序(栈是后进先出)
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
        return result;
    }
}

迭代实现二叉树中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.add(current.val); // 中序遍历的操作
        current = current.right;
    }
    return result;
}

迭代实现二叉树后续遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        // result.addFirst(node.val);
        result.add(0, current.val); // 后序遍历的操作，在结果列表的开头插入节点值
        // 先左后右的顺序入栈，保证出栈顺序为根右左，即后序遍历的顺序
        if (current.left != null) {
            stack.push(current.left);
        }
        if (current.right != null) {
            stack.push(current.right);
        }
    }
    return result;
}

二叉树的广度优先遍历

深度优先遍历有三种，前中后序遍历。如上。
广度优先遍历是层序遍历，即按照层级从上到下、从左到右逐层访问节点的遍历方式。

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
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public class BinaryTree {
    public void breadthFirstTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 将根节点入队
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // 出队
            System.out.print(node.val + " "); // 访问节点
            // 左右子节点依次入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    public static void main(String[] args) {
        // 构造二叉树示例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        
        BinaryTree bt = new BinaryTree();
        System.out.println("Breadth-First Traversal:");
        bt.breadthFirstTraversal(root);
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                // 左右子树进队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

二叉树的最近公共祖先(LCA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return find(root, p.val, q.val);
    }
    // 在二叉树中寻找 val1 和 val2 的最近公共祖先节点
    TreeNode find(TreeNode root, int val1, int val2) {
        if (root == null) {
            return null;
        }
        // 前序位置
        if (root.val == val1 || root.val == val2) {
            // 如果遇到目标值，直接返回
            return root;
        }
        TreeNode left = find(root.left, val1, val2);
        TreeNode right = find(root.right, val1, val2);
        // 后序位置，已经知道左右子树是否存在目标值
        if (left != null && right != null) {
            // 当前节点是 LCA 节点
            return root;
        }
        return left != null ? left : right;
    }
}

二叉树的最大路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    private int ans = Integer.MIN_VALUE; // 不能定义为static
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node) {
        // 没有节点，和为0
        if (node == null) return 0;
        int leftVal = dfs(node.left); // 左子树最大链和
        int rightVal = dfs(node.right); // 右子树最大链和
        ans = Math.max(ans, leftVal + rightVal + node.val); // 两条链拼接
        return Math.max(Math.max(leftVal, rightVal) + node.val, 0); // 当前子树的最大链和
    }
}

二叉树最大宽度

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
// 层序遍历思路
class Solution {
    // 记录节点和对应编号
    class Pair {
        TreeNode node;
        int id;
        public Pair( TreeNode node, int id) {
            this.node = node;
            this.id = id;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 记录最大的宽度
        int maxWidth = 0;
        // 标准 BFS 层序遍历算法
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(root, 1));
        // 从上到下遍历整棵树
        while (!q.isEmpty()) {
            int sz = q.size();
            int start = 0, end = 0;
            // 从左到右遍历每一行
            for (int i = 0; i < sz; i++) {
                Pair cur = q.poll();
                TreeNode curNode = cur.node;
                int curId = cur.id;
                // 记录当前行第一个和最后一个节点的编号
                if (i == 0) {
                    start = curId;
                }
                if (i == sz - 1) {
                    end = curId;
                }
                // 左右子节点入队，同时记录对应节点的编号
                if (curNode.left != null) {
                    q.offer(new Pair(curNode.left, curId * 2));
                }
                if (curNode.right != null) {
                    q.offer(new Pair(curNode.right, curId * 2 + 1));
                }
            }
            // 用当前行的宽度更新最大宽度
            maxWidth = Math.max(maxWidth, end - start + 1);
        }
        return maxWidth;
    }
}
// 递归遍历思路
class Solution2 {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        traverse(root, 1, 1);
        return maxWidth;
    }
    // 记录最左侧节点的编号
    ArrayList<Integer> firstId = new ArrayList<>();
    int maxWidth = 1;
    // 二叉树遍历函数
    void traverse(TreeNode root, int id, int depth) {
        if (root == null) {
            return;
        }
        if (firstId.size() == depth - 1) {
            // 因为代码是先 traverse(root.left) 后 traverse(root.right)，
            // 所以第一次到达这个深度一定是最左侧的节点，记录其编号
            firstId.add(id);
        } else {
            // 这个深度的其他节点，负责计算更新当前深度的最大宽度
            maxWidth = Math.max(maxWidth, id - firstId.get(depth - 1) + 1);
        }
        traverse(root.left, id * 2, depth + 1);
        traverse(root.right, id * 2 + 1, depth + 1);
    }
}

多叉树查找某个值

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
// 定义多叉树的节点类
class TreeNode {
    int value;
    List<TreeNode> children;

    public TreeNode(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    // 添加子节点的方法
    public void addChild(TreeNode child) {
        this.children.add(child);
    }
}

public class MultiWayTree {
    // 在多叉树中查找值的方法
    public static boolean search(TreeNode root, int target) {
        // 如果根节点为空，返回false
        if (root == null) {
            return false;
        }

        // 如果找到目标值，返回true
        if (root.value == target) {
            return true;
        }

        // 遍历子节点，递归查找
        for (TreeNode child : root.children) {
            if (search(child, target)) {
                return true;
            }
        }

        // 如果没有找到，返回false
        return false;
    }

    public static void main(String[] args) {
        // 创建多叉树
        TreeNode root = new TreeNode(1);
        TreeNode child1 = new TreeNode(2);
        TreeNode child2 = new TreeNode(3);
        TreeNode child3 = new TreeNode(4);
        root.addChild(child1);
        root.addChild(child2);
        root.addChild(child3);
        child1.addChild(new TreeNode(5));
        child1.addChild(new TreeNode(6));
        child2.addChild(new TreeNode(7));
        child3.addChild(new TreeNode(8));

        // 查找某个值
        int target = 7;
        boolean found = search(root, target);
        System.out.println("Found target " + target + ": " + found);
    }
}

ArrayList实现最大堆

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
import java.util.ArrayList;

public class MaxHeap {
    private ArrayList<Integer> heap;
    public MaxHeap() {
        heap = new ArrayList<>();
    }
    public void insert(int value) {
        heap.add(value);
        heapifyUp(heap.size() - 1);
    }
    public int extractMax() {
        if (heap.isEmpty()) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = heap.get(0);
        int last = heap.remove(heap.size() - 1);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            heapifyDown(0);
        }
        return max;
    }
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap.get(index) > heap.get(parentIndex)) {
                swap(index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }
    private void heapifyDown(int index) {
        int size = heap.size();
        while (index < size) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int largestIndex = index;

            if (leftChildIndex < size && heap.get(leftChildIndex) > heap.get(largestIndex)) {
                largestIndex = leftChildIndex;
            }
            if (rightChildIndex < size && heap.get(rightChildIndex) > heap.get(largestIndex)) {
                largestIndex = rightChildIndex;
            }

            if (largestIndex != index) {
                swap(index, largestIndex);
                index = largestIndex;
            } else {
                break;
            }
        }
    }
    private void swap(int index1, int index2) {
        int temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        System.out.println("Max element: " + maxHeap.extractMax()); // 输出 20
        System.out.println("Max element: " + maxHeap.extractMax()); // 输出 10
        System.out.println("Max element: " + maxHeap.extractMax()); // 输出 5
    }
}

最长有效括号

保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

  • 对于遇到的每个 ‘(’ ，将它的下标放入栈中
  • 对于遇到的每个 ‘)’ ，先弹出栈顶元素表示匹配了当前右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    • 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
      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
      class Solution {
          public int longestValidParentheses(String s) {
              int maxans = 0;
              // 使用栈来存储括号的位置，保持栈底元素是最后一个没有被匹配的右括号的下标
              Deque<Integer> stack = new LinkedList<Integer>();
              stack.push(-1); // 先在栈中加入-1，作为基准位置，用于计算有效长度
              for (int i = 0; i < s.length(); i++) {
                  // 如果当前字符是 '('，将它的位置压入栈中
                  if (s.charAt(i) == '(') {
                      stack.push(i);
                  } else {
                      // 如果当前字符是 ')'，从栈中弹出一个位置
                      stack.pop();
                      // 如果栈为空，说明当前的 ')' 没有匹配的 '('，将当前位置压入栈中
                      if (stack.isEmpty()) {
                          stack.push(i);
                      } else {
                          // 否则，计算当前有效括号的长度，并更新最大长度
                          maxans = Math.max(maxans, i - stack.peek());
                      }
                  }
              }
              // 返回最长有效括号的长度
              return maxans;
          }
      }

遍历HashMap

七种

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
HashMap<Integer, String> map = new HashMap<>();
// ForEach EntrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}
// ForEach KeySet
for (Integer key : map.keySet()) {
    System.out.println(key + ":" + map.get(key));
}
// 迭代器EntrySet
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    System.out.println(entry.getKey() + ":" + entry.getValue());
}
// 迭代器KeySet
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
    Integer key = iterator.next();
    System.out.println(key + ":" + map.get(key));
}
// Lambda
map.forEach((key, value) -> {
    System.out.println(key);
    System.out.println(value);
});
// Streams API 单线程
map.entrySet().stream().forEach(entry -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});
// Streams API 多线程
map.entrySet().parallelStream().forEach(entry -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});

遍历Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Set<Integer> row = new HashSet<>();
row.add(1);
row.add(2);
row.add(3);
// 增强for循环
for (Integer number : row) {
    System.out.println(number);
}
// 迭代起
Iterator<Integer> iterator = row.iterator();
while (iterator.hasNext()) {
    Integer number = iterator.next();
    System.out.println(number);
}
// forEach+Lambda表达式
row.forEach(number -> System.out.println(number));
// Streams API 单线程
row.stream().forEach(System.out::println);

岛屿数量

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
class Solution {
    int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};  // 方向数组，分别代表上、下、左、右
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 新发现一个岛屿，结果+1
                    res++;
                    // 使用dfs将这个岛屿淹没
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    // boolean[][] visited; 如果需要是否访问的话
    private void dfs(char[][] grid, int i, int j) { // 从 (i, j) 开始，将与之相邻的陆地都变成海水
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) return; // 超出索引边界
        if (grid[i][j] == '0') return; // 已经是水了
        // if (visited[i][j]) return;
        grid[i][j] = '0'; // 将(i, j)变成海水
        for (int[] dir : dirs) {
            dfs(grid, i + dir[0], j + dir[1]);
        }
    }
}

前缀树(Trie)

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
class Trie {
    private Trie[] children; // 指向子节点的指针数组
    private boolean isEnd; // 记录当前Trie节点是否为叶子节点
    public Trie() {
        children = new Trie[26]; // 仅包含26个小写英文字母
        isEnd = false;
    }
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

全排列

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
class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>(); // 记录「路径」
        boolean[] used = new boolean[nums.length]; //「路径」中的元素会被标记为 true，避免重复使用
        backtrack(nums, track, used);
        return res;
    }
    private void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) { // 排除不合法的选择
                // nums[i] 已经在 track 中，跳过
                continue;
            }
            // 做选择
            track.add(nums[i]);
            used[i] = true;
            // 进入下一层决策树
            backtrack(nums, track, used);
            // 取消选择
            track.removeLast();
            used[i] = false;
        }
    }
}

数组的子集

给你一个整数数组 nums ，数组中的元素互不相同 。返回该数组所有可能的子集(幂集)。 解集不能包含重复的子集。你可以按任意顺序返回解集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        List<Integer> track = new ArrayList<>();
        backtrack(nums, 0, track);
        return res;
    }
    private void backtrack(int[] nums, int start, List<Integer> track) {
        res.add(new ArrayList<>(track));
        for (int i = start; i < nums.length; i++) {
            track.add(nums[i]); // 做选择
            backtrack(nums, i+1, track); // 回溯
            track.remove(track.size() - 1); // 撤销选择
        }
    }
}

创建三个线程有序打印1-100

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
public class ConcurrentDemo {
    private static final int MAX_NUMBER = 100;  // 定义最大数字为100
    private static int number = 1;  // 当前要打印的数字，初始值为1
    private static final Object lock = new Object();  // 锁对象，用于线程间的通信
    public static void main(String[] args) {
        // 创建三个线程，每个线程使用不同的threadId（0, 1, 2）
        Thread t1 = new Thread(new PrintTask(1));
        Thread t2 = new Thread(new PrintTask(2));
        Thread t3 = new Thread(new PrintTask(0));
        // 启动线程
        t1.start();
        t2.start();
        t3.start();
    }
    static class PrintTask implements Runnable {
        private int threadId;  // 线程的标识符，用于控制打印顺序
        public PrintTask(int threadId) {
            this.threadId = threadId;
        }
        @Override
        public void run() {
            while (true) {
                synchronized (lock) {  // 锁定lock对象，保证同一时刻只有一个线程可以访问
                    // 如果当前数字不能被对应线程处理，则等待
                    while (number % 3 != threadId) {
                        try {
                            lock.wait();  // 当前线程等待，释放锁
                        } catch (InterruptedException e) {
                            Thread.currentThread().interrupt();  // 处理线程中断
                        }
                    }
                    // 如果当前数字超过最大值，通知其他线程并结束循环
                    if (number > MAX_NUMBER) {
                        lock.notifyAll();  // 通知其他所有线程
                        break;  // 退出循环，结束线程
                    }
                    // 打印当前数字并自增
                    System.out.println("Thread-" + threadId + " prints: " + number++);
                    // 唤醒其他等待的线程
                    lock.notifyAll();
                }
            }
        }
    }
}

模拟死锁

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
public class DeadLockSample {
    private final Object lock1 = new Object();
    private final Object lock2 = new Object();
    public void createDeadLock() {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread1 get lock1");
                // 让线程1休眠，确保线程2可以获取到lock2
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                synchronized (lock2) {
                    System.out.println("Thread1 try get lock2.");
                }
            }
        });
        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {
                System.out.println("Thread2 get lock2");
                // 让线程2休眠，确保线程1可以获取到lock2
                try {
                    Thread.sleep(50);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                synchronized (lock1) {
                    System.out.println("Thread2 try get lock1.");
                }
            }
        });
        thread1.start();
        thread2.start();
    }
    public static void main(String[] args) {
        DeadLockSample deadLockSample = new DeadLockSample();
        deadLockSample.createDeadLock();
    }
}

实现生产者消费者模型

使用BlockingQueue

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
public class ProducerConsumerExample {
    // 定义缓冲区的容量
    private static final int BUFFER_CAPACITY = 10;
    // 创建一个共享缓冲区
    private final BlockingQueue<Integer> buffer = new LinkedBlockingQueue<>(BUFFER_CAPACITY);
    public static void main(String[] args) {
        ProducerConsumerExample example = new ProducerConsumerExample();
        // 启动生产者线程
        new Thread(example.new Producer()).start();
        // 启动消费者线程
        new Thread(example.new Consumer()).start();
    }
    // 生产者类
    class Producer implements Runnable {
        @Override
        public void run() {
            int value = 0;
            while (true) {
                try {
                    produce(value++);
                    Thread.sleep(1000); // 模拟生产过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void produce(int value) throws InterruptedException {
            // 将产品放入缓冲区，若缓冲区满则等待
            buffer.put(value);
            System.out.println("Produced: " + value);
        }
    }
    // 消费者类
    class Consumer implements Runnable {
        @Override
        public void run() {
            while (true) {
                try {
                    consume();
                    Thread.sleep(1500); // 模拟消费过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void consume() throws InterruptedException {
            // 从缓冲区中取出产品，若缓冲区空则等待
            int value = buffer.take();
            System.out.println("Consumed: " + value);
        }
    }
}

使用wait()和notify()

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
public class ProducerConsumerExample {
    // 定义缓冲区的容量
    private static final int BUFFER_CAPACITY = 10;
    // 创建一个共享缓冲区
    private final Queue<Integer> buffer = new LinkedList<>();
    private final Object lock = new Object();
    public static void main(String[] args) {
        ProducerConsumerExample example = new ProducerConsumerExample();

        // 启动生产者线程
        new Thread(example.new Producer()).start();

        // 启动消费者线程
        new Thread(example.new Consumer()).start();
    }
    // 生产者类
    class Producer implements Runnable {
        @Override
        public void run() {
            int value = 0;
            while (true) {
                try {
                    produce(value++);
                    Thread.sleep(1000); // 模拟生产过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void produce(int value) throws InterruptedException {
            synchronized (lock) {
                // 如果缓冲区已满，等待消费者消费
                while (buffer.size() == BUFFER_CAPACITY) {
                    System.out.println("Buffer is full, producer is waiting...");
                    lock.wait();
                }
                // 将产品放入缓冲区
                buffer.add(value);
                System.out.println("Produced: " + value);
                // 通知消费者有新的产品
                lock.notifyAll();
            }
        }
    }
    // 消费者类
    class Consumer implements Runnable {
        @Override
        public void run() {
            while (true) {
                try {
                    consume();
                    Thread.sleep(1500); // 模拟消费过程
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }
        private void consume() throws InterruptedException {
            synchronized (lock) {
                // 如果缓冲区为空，等待生产者生产
                while (buffer.isEmpty()) {
                    System.out.println("Buffer is empty, consumer is waiting...");
                    lock.wait();
                }
                // 从缓冲区中取出产品
                int value = buffer.poll();
                System.out.println("Consumed: " + value);
                // 通知生产者有空位
                lock.notifyAll();
            }
        }
    }
}

CompletableFuture实现异步调用

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
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;
public class AsyncExample {
    public static void main(String[] args) {
        // 创建一个CompletableFuture来执行异步任务
        CompletableFuture<String> future = CompletableFuture.supplyAsync(() -> {
            // 模拟一个长时间运行的任务
            try {
                Thread.sleep(2000); // 休眠2秒
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            return "任务完成";
        });
        // 注册一个回调函数，当任务完成时获取结果
        future.thenAccept(result -> {
            System.out.println("异步任务结果: " + result);
        });
        // 主线程继续执行其他操作
        System.out.println("主线程继续执行...");
        // 阻塞主线程，直到异步任务完成(可选)
        try {
            // 这一步会阻塞主线程，直到异步任务完成
            String result = future.get();
            System.out.println("异步任务完成后获取的结果: " + result);
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }
    }
}

最长重复子串(不会)

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
86
87
88
class Solution {
    public String longestDupSubstring(String s) {
        Random random = new Random();
        // 生成两个进制
        int a1 = random.nextInt(75) + 26;
        int a2 = random.nextInt(75) + 26;
        // 生成两个模
        int mod1 = random.nextInt(Integer.MAX_VALUE - 1000000007 + 1) + 1000000007;
        int mod2 = random.nextInt(Integer.MAX_VALUE - 1000000007 + 1) + 1000000007;
        int n = s.length();
        // 先对所有字符进行编码
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = s.charAt(i) - 'a';
        }
        // 二分查找的范围是[1, n-1]
        int l = 1, r = n - 1;
        int length = 0, start = -1;
        while (l <= r) {
            int m = l + (r - l + 1) / 2;
            int idx = check(arr, m, a1, a2, mod1, mod2);
            if (idx != -1) {
                // 有重复子串，移动左边界
                l = m + 1;
                length = m;
                start = idx;
            } else {
                // 无重复子串，移动右边界
                r = m - 1;
            }
        }
        return start != -1 ? s.substring(start, start + length) : "";
    }
    public int check(int[] arr, int m, int a1, int a2, int mod1, int mod2) {
        int n = arr.length;
        long aL1 = pow(a1, m, mod1);
        long aL2 = pow(a2, m, mod2);
        long h1 = 0, h2 = 0;
        for (int i = 0; i < m; ++i) {
            h1 = (h1 * a1 % mod1 + arr[i]) % mod1;
            h2 = (h2 * a2 % mod2 + arr[i]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
        }
        // 存储一个编码组合是否出现过
        Set<Long> seen = new HashSet<Long>();
        seen.add(h1 * mod2 + h2);
        for (int start = 1; start <= n - m; ++start) {
            h1 = (h1 * a1 % mod1 - arr[start - 1] * aL1 % mod1 + arr[start + m - 1]) % mod1;
            h2 = (h2 * a2 % mod2 - arr[start - 1] * aL2 % mod2 + arr[start + m - 1]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
            long num = h1 * mod2 + h2;
            // 如果重复，则返回重复串的起点
            if (!seen.add(num)) {
                return start;
            }
        }
        // 没有重复，则返回-1
        return -1;
    }
    public long pow(int a, int m, int mod) {
        long ans = 1;
        long contribute = a;
        while (m > 0) {
            if (m % 2 == 1) {
                ans = ans * contribute % mod;
                if (ans < 0) {
                    ans += mod;
                }
            }
            contribute = contribute * contribute % mod;
            if (contribute < 0) {
                contribute += mod;
            }
            m /= 2;
        }
        return ans;
    }
}

A*算法

A*(A-star)算法是一种启发式搜索算法，常用于图搜索和路径规划问题。它结合了广度优先搜索和贪心最佳优先搜索的优点，使用启发式估计函数来指导搜索路径。

下面是一个简单的A*算法的Java实现，用于在二维网格上寻找从起点到终点的最短路径。假设网格中的每个节点是一个单元格，可以是可通行或不可通行的。

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
86
87
88
89
90
91
92
93
94
import java.util.*;
// 表示网格中的一个节点，包含节点的坐标、g 值(从起点到该节点的代价)、h 值(启发式估计值)和指向父节点的引用。
class Node implements Comparable<Node> {
    public int x, y;
    public int g, h;
    public Node parent; // 指向父节点的引用
    public Node(int x, int y, int g, int h, Node parent) {
        this.x = x;
        this.y = y;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }
    public int getF() {
        return g + h;
    }
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.getF(), other.getF());
    }
}
public class AStarAlgorithm {
    private static final int[] DIR_X = {-1, 1, 0, 0};
    private static final int[] DIR_Y = {0, 0, -1, 1};
    // aStar 方法执行 A* 搜索。它使用优先队列(基于节点的 F 值排序)来选择当前节点，并检查四个可能的移动方向(上下左右)。
    public List<Node> aStar(int[][] grid, Node start, Node goal) {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Set<Node> closedList = new HashSet<>();
        openList.add(start);
        while (!openList.isEmpty()) {
            Node current = openList.poll();
            if (current.x == goal.x && current.y == goal.y) {
                return constructPath(current);
            }
            closedList.add(current);
            for (int i = 0; i < 4; i++) {
                int newX = current.x + DIR_X[i];
                int newY = current.y + DIR_Y[i];
                if (isValid(grid, newX, newY) && !isInClosedList(closedList, newX, newY)) {
                    int newG = current.g + 1;
                    int newH = heuristic(newX, newY, goal.x, goal.y);
                    Node neighbor = new Node(newX, newY, newG, newH, current);
                    if (!isInOpenList(openList, neighbor)) {
                        openList.add(neighbor);
                    }
                }
            }
        }
        return Collections.emptyList(); // No path found
    }
    // isValid 方法检查移动是否在网格范围内且该位置可通行。
    private boolean isValid(int[][] grid, int x, int y) {
        return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 0;
    }
    // isInClosedList 方法检查节点是否在 closedList 中。
    private boolean isInClosedList(Set<Node> closedList, int x, int y) {
        return closedList.stream().anyMatch(node -> node.x == x && node.y == y);
    }
    // isInOpenList 方法检查节点是否在 openList 中。
    private boolean isInOpenList(PriorityQueue<Node> openList, Node node) {
        return openList.stream().anyMatch(n -> n.x == node.x && n.y == node.y);
    }
    // heuristic 方法计算节点到目标节点的启发式估计值。这里使用的是曼哈顿距离。
    private int heuristic(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2); // Manhattan distance
    }
    // constructPath 方法从目标节点回溯构建路径。
    private List<Node> constructPath(Node node) {
        List<Node> path = new ArrayList<>();
        while (node != null) {
            path.add(node);
            node = node.parent;
        }
        Collections.reverse(path);
        return path;
    }
    // Main 方法：定义网格、起点和终点，运行 A* 算法并打印路径。
    public static void main(String[] args) {
        int[][] grid = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };
        Node start = new Node(0, 0, 0, 0, null);
        Node goal = new Node(4, 4, 0, 0, null);
        AStarAlgorithm aStar = new AStarAlgorithm();
        List<Node> path = aStar.aStar(grid, start, goal);
        for (Node node : path) {
            System.out.println("Node: (" + node.x + ", " + node.y + ")");
        }
    }
}

设计模式

单例模式(Singleton Pattern)

单例模式确保一个类只有一个实例，并提供一个全局访问点。

  • 饿汉式：饿汉式单例模式在类加载时就完成实例化，线程安全，简单但可能会造成资源浪费。
  • 懒汉式：懒汉式单例模式在第一次调用 getInstance 方法时创建实例，线程不安全，需要额外处理同步。
  • 线程安全的懒汉式
    • 同步方法：在 getInstance 方法上加 synchronized 关键字，保证线程安全，但是效率低。
    • 双重检查锁定：在 getInstance 方法内部进行双重检查，保证只有第一次调用时才会加锁，提高效率。
  • 静态内部类：利用静态内部类来实现懒加载和线程安全。
  • 枚举：枚举实现单例模式是最简洁、安全的实现方式，可以防止反射和序列化攻击。
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
// 饿汉式
public class Singleton {
    private static final Singleton instance = new Singleton();
    private Singleton() {}
    public static Singleton getInstance() {
        return instance;
    }
}

// 懒汉式
public class Singleton {
    private static Singleton instance;
    private Singleton() {}
    public static Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

// 线程安全的懒汉式-同步方法
public class Singleton {
    private static Singleton instance;
    private Singleton() {}
    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

// 线程安全的懒汉式-双重检查锁定
public class Singleton {
    // 单例模式中用于保存实例的字段，被声明为volatile，确保对该变量的写入操作会立即反映到所有线程中，这样可以防止可能发生的指令重排序问题。
    private volatile static Singleton uniqueInstance;
    // 私有的构造方法确保该类不能在外部被初始化，只能通过getUniqueInstance()方法获取实例
    private Singleton() {
    }
    // 双重检查锁定的机制，实现对外提供的获取单例实例的方法。
    public static Singleton getInstance() {
        // 第一层检查：首先检查 uniqueInstance 是否为 null。如果不是 null，意味着实例已经被创建，则直接返回这个实例。
        if (uniqueInstance == null) {
            // 类对象加锁，表示进入同步代码前要获得 Singleton类 的锁
            synchronized (Singleton.class) {
                // 第二层检查：在同步代码块内再次检查 uniqueInstance 是否为 null。
                // 这种双重检查是为了在等待锁的线程获取到锁后再次确认实例是否已经被创建，因为在等待锁的过程中可能有其他线程已经创建了实例。
                if (uniqueInstance == null) {
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
    public static void main(String[] args) {
        System.out.println(getInstance());
    }

}

// 静态内部类
public class Singleton {
    private Singleton() {}
    private static class SingletonHolder {
        private static final Singleton INSTANCE = new Singleton();
    }
    public static Singleton getInstance() {
        return SingletonHolder.INSTANCE;
    }
}

// 枚举
public enum Singleton {
    // 注意 上面不是 class 是 enum
    INSTANCE;
    public void someMethod() {
        // do something
    }
    public static void main(String[] args) {
        Singelton singleton = Singleton.INSTANCE;
        singleton.someMethod();
    }
}

工厂模式(Factory Pattern)

工厂模式定义了一个用于创建对象的接口，但由子类决定实例化哪个类。它使得类的实例化延迟到子类。

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
// 产品接口
interface Product {
    void use();
}
// 具体产品A
class ProductA implements Product {
    @Override
    public void use() {
        System.out.println("Using Product A");
    }
}
// 具体产品B
class ProductB implements Product {
    @Override
    public void use() {
        System.out.println("Using Product B");
    }
}
// 工厂类
class ProductFactory {
    public static Product createProduct(String type) {
        if (type.equals("A")) {
            return new ProductA();
        } else if (type.equals("B")) {
            return new ProductB();
        }
        throw new IllegalArgumentException("Unknown product type");
    }
}
// 使用
public class FactoryPatternDemo {
    public static void main(String[] args) {
        Product product = ProductFactory.createProduct("A");
        product.use();
    }
}

适配器模式(Adapter Pattern)

适配器模式将一个类的接口转换成客户希望的另一个接口，使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

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
// 目标接口
interface Target {
    void request();
}
// 需要适配的类
class Adaptee {
    public void specificRequest() {
        System.out.println("Specific request");
    }
}
// 适配器
class Adapter implements Target {
    private Adaptee adaptee;
    public Adapter(Adaptee adaptee) {
        this.adaptee = adaptee;
    }
    @Override
    public void request() {
        adaptee.specificRequest();
    }
}
// 使用
public class AdapterPatternDemo {
    public static void main(String[] args) {
        Adaptee adaptee = new Adaptee();
        Target target = new Adapter(adaptee);
        target.request();
    }
}

装饰者模式(Decorator Pattern)

装饰者模式允许向一个现有的对象添加新的功能，同时又不改变其结构。

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
// 组件接口
interface Component {
    void operation();
}
// 具体组件
class ConcreteComponent implements Component {
    @Override
    public void operation() {
        System.out.println("ConcreteComponent operation");
    }
}
// 抽象装饰者
abstract class Decorator implements Component {
    protected Component component;
    public Decorator(Component component) {
        this.component = component;
    }
    @Override
    public void operation() {
        component.operation();
    }
}
// 具体装饰者A
class ConcreteDecoratorA extends Decorator {
    public ConcreteDecoratorA(Component component) {
        super(component);
    }
    @Override
    public void operation() {
        super.operation();
        System.out.println("ConcreteDecoratorA additional operation");
    }
}
// 具体装饰者B
class ConcreteDecoratorB extends Decorator {
    public ConcreteDecoratorB(Component component) {
        super(component);
    }
    @Override
    public void operation() {
        super.operation();
        System.out.println("ConcreteDecoratorB additional operation");
    }
}
// 使用
public class DecoratorPatternDemo {
    public static void main(String[] args) {
        Component component = new ConcreteComponent();
        Component decoratedComponentA = new ConcreteDecoratorA(component);
        Component decoratedComponentB = new ConcreteDecoratorB(decoratedComponentA);
        decoratedComponentB.operation();
    }
}

策略模式(Strategy Pattern)

策略模式定义了一系列算法，并将每一个算法封装起来，使它们可以相互替换。策略模式使得算法可独立于使用它的客户而变化。

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
// 策略接口
interface Strategy {
    int doOperation(int num1, int num2);
}
// 具体策略A
class OperationAdd implements Strategy {
    @Override
    public int doOperation(int num1, int num2) {
        return num1 + num2;
    }
}
// 具体策略B
class OperationSubtract implements Strategy {
    @Override
    public int doOperation(int num1, int num2) {
        return num1 - num2;
    }
}
// 具体策略C
class OperationMultiply implements Strategy {
    @Override
    public int doOperation(int num1, int num2) {
        return num1 * num2;
    }
}
// 上下文
class Context {
    private Strategy strategy;
    public Context(Strategy strategy) {
        this.strategy = strategy;
    }
    public int executeStrategy(int num1, int num2) {
        return strategy.doOperation(num1, num2);
    }
}
// 使用
public class StrategyPatternDemo {
    public static void main(String[] args) {
        Context context = new Context(new OperationAdd());
        System.out.println("10 + 5 = " + context.executeStrategy(10, 5));
        context = new Context(new OperationSubtract());
        System.out.println("10 - 5 = " + context.executeStrategy(10, 5));
        context = new Context(new OperationMultiply());
        System.out.println("10 * 5 = " + context.executeStrategy(10, 5));
    }
}

观察者模式(Observer Pattern)

观察者模式定义对象间的一种一对多的依赖关系，使得每当一个对象改变状态，则所有依赖于它的对象都会得到通知并被自动更新。

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
import java.util.ArrayList;
import java.util.List;
// 观察者接口
interface Observer {
    void update(String message);
}
// 具体观察者
class ConcreteObserver implements Observer {
    private String name;
    public ConcreteObserver(String name) {
        this.name = name;
    }
    @Override
    public void update(String message) {
        System.out.println(name + " received: " + message);
    }
}
// 被观察者接口
interface Subject {
    void registerObserver(Observer observer);
    void removeObserver(Observer observer);
    void notifyObservers();
}
// 具体被观察者
class ConcreteSubject implements Subject {
    private List<Observer> observers = new ArrayList<>();
    private String message;
    @Override
    public void registerObserver(Observer observer) {
        observers.add(observer);
    }
    @Override
    public void removeObserver(Observer observer) {
        observers.remove(observer);
    }
    @Override
    public void notifyObservers() {
        for (Observer observer : observers) {
            observer.update(message);
        }
    }
    public void setMessage(String message) {
        this.message = message;
        notifyObservers();
    }
}
// 使用
public class ObserverPatternDemo {
    public static void main(String[] args) {
        ConcreteSubject subject = new ConcreteSubject();
        Observer observer1 = new ConcreteObserver("Observer 1");
        Observer observer2 = new ConcreteObserver("Observer 2");
        subject.registerObserver(observer1);
        subject.registerObserver(observer2);
        subject.setMessage("Hello Observers!");
    }
}

漏桶算法(Leaky Bucket)

漏桶算法是一种流量整形(Traffic Shaping)和速率限制算法，用于控制数据传输速率。它通过固定容量的桶来限制数据的传输速率，当数据到达时，将数据放入桶中，然后以固定速率从桶中取出数据进行传输。

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
import java.util.concurrent.atomic.AtomicInteger;

public class LeakyBucket {
    private final int capacity;
    private final int rate;
    private AtomicInteger water;

    public LeakyBucket(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = new AtomicInteger(0);

        // 定期漏水
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(1000 / rate);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
                water.decrementAndGet();
            }
        }).start();
    }

    public boolean grant() {
        int currentWater = water.get();
        if (currentWater < capacity) {
            water.incrementAndGet();
            return true;
        }
        return false;
    }
}

令牌桶算法(Token Bucket)

令牌桶算法是一种流量整形(Traffic Shaping)和速率限制算法，用于控制数据传输速率。它通过固定容量的桶来限制数据的传输速率，当数据到达时，需要获取令牌才能进行传输。

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
import java.util.concurrent.atomic.AtomicInteger;

public class TokenBucket {
    private final int capacity;
    private final int refillRate;
    private AtomicInteger tokens;
    private final long refillInterval;

    public TokenBucket(int capacity, int refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = new AtomicInteger(capacity);
        this.refillInterval = 1000 / refillRate;

        // 定期添加令牌
        new Thread(() -> {
            while (true) {
                try {
                    Thread.sleep(refillInterval);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
                tokens.updateAndGet(current -> Math.min(capacity, current + 1));
            }
        }).start();
    }

    public boolean grant() {
        int currentTokens = tokens.get();
        if (currentTokens > 0) {
            tokens.decrementAndGet();
            return true;
        }
        return false;
    }
}

限流队列

结合漏桶算法和消息队列，实现一个限流队列，用于控制任务的执行速率。

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
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class RateLimiterQueue {
    private final LeakyBucket rateLimiter;
    private final BlockingQueue<Runnable> taskQueue;

    public RateLimiterQueue(int capacity, int rate, int queueSize) {
        this.rateLimiter = new LeakyBucket(capacity, rate);
        this.taskQueue = new LinkedBlockingQueue<>(queueSize);
        
        new Thread(() -> {
            while (true) {
                try {
                    Runnable task = taskQueue.take();
                    if (rateLimiter.grant()) {
                        new Thread(task).start();
                    } else {
                        // 限流，重新加入队列
                        taskQueue.offer(task);
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }).start();
    }
    public void submitTask(Runnable task) {
        if (!taskQueue.offer(task)) {
            System.out.println("任务队列已满，拒绝任务");
        }
    }
    public static void main(String[] args) {
        RateLimiterQueue rateLimiterQueue = new RateLimiterQueue(100, 10, 1000);

        for (int i = 0; i < 10000; i++) {
            final int taskId = i;
            rateLimiterQueue.submitTask(() -> {
                System.out.println("处理任务：" + taskId);
                // 模拟任务处理时间
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
    }
}