今天看到这么一句话：他把排序称之为宙的秩序之源。当我们谈论排序算法时，我们实际上是在讨论将混乱转变为有序的艺术。从最简单的冒泡排序到更为高级的快速排序和归并排序，它们如同古老的占星术，通过某种天文般的精确度将数据排列成行。而堆排序，则仿佛是建造金字塔的法老，将数据层层叠加，最终构建出一座伟大的数据结构。

最大流量问题是一个特殊的线性规划问题

针对问题：道路运输能力问题，管道流量问题等等

定义

在连通的带权图的所有生成树中，权值和最小的那颗生成树（包含图中所有顶点的树），称为最小生成树。

针对问题：带权图的最短路径问题。

解法

普里姆（Prim）算法

以 点 为基础，挑选与 已有点 相连的最小边。

克鲁斯卡尔（Kruskal）算法——常用

是以 边 为基础，先将边从小到大排列，从小到大的添加不构成「环路」的边。

两个队列实现栈

首先准备两个队列A、B 可以使用ADD方法，先向A队列进入5个数据（也可以是n个这里用5做例子） 调用POP方法弹出最后一次进入数据（在2个队列中的非空的队列上的前n-1个数据移入空队列，最后一个数据出队列并返回）

非空队列：由来插入数据 空队列：用来倒数据，存数据

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Wang WenLei
 * @date 2024/4/22 11:30
 * @since 1.0
 */

public class Main {

    private static final Queue<Integer> A = new LinkedList<>();
    private static final Queue<Integer> B = new LinkedList<>();

    public static void main(String[] args) {
        add(1);
        add(2);
        add(3);
        add(4);
        add(5);
        System.out.println("前：" + A.toString() + B.toString());
        System.out.println("弹出：" + pop());
        System.out.println("pop后1：" + A.toString() + B.toString());
        add(6);
        System.out.println("add后2：" + A.toString() + B.toString());
        System.out.println(pop());
        System.out.println("add后3：" + A.toString() + B.toString());
    }

    /**
     * 队列模拟栈的压栈操作
     * 在2个队列中的非空的队列上数据
     *
     * @param data 压栈数据
     */
    public static void add(Integer data) {
        // 如果B队列为空，就在A的队列上追加
        if (B.size() == 0) {
            A.add(data);
        }

        // 如果A队列为空，就在B的队列上追加
        if (A.size() == 0) {
            B.add(data);
        }
    }

    /**
     * 队列模拟栈的出栈操作
     * 在2个队列中的非空的队列上的前n-1个数据移入空队列，最后一个数据出队列并返回
     */
    public static Integer pop() {
        // 如果B队列为空，就在A的队列上追加
        if (B.size() == 0) {
            int num = A.size() - 1;
            for (int i = 0; i < num; i++) {
                B.add(A.poll());
            }
            return A.poll();
        }

        // 如果A队列为空，就在B的队列上追加
        if (A.size() == 0) {
            int num = B.size() - 1;
            for (int i = 0; i < num; i++) {
                A.add(B.poll());
            }
            return B.poll();
        }
        return null;
    }

}

问题描述

给定一个主串S及一个模式串P，判断模式串是否为主串的子串；若是，返回匹配的第一个元素的位置（序号从1开始），否则返回0；如S=“abcd”，P=“bcd”，则返回2；S=“abcd”，P=“acb”，返回0。

什么是KMP算法？

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度 O(m+n)。

描述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。 如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0 <= n <= 10^5，0 <= a_i <= 10^9，0 <= k <= 10^9

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

解题思路

使用Hash结构

1. 把所有节点都放在Map里，k使用当前链表节点，v使用new出来的节点
2. 循环Map，每个元素都找他的next和random，分别给value赋值

1.描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0\leq n\leq10000≤n≤1000 要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时， 经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。 以上转换过程如下图所示：

示例1

    输入：
    {1,2,3}
    返回值：
    {3,2,1}

题目

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。 例如： 给出的链表为 1→ 2 → 3 → 4 → 5 → NULL1→2→3→4→5→NULL, m=2,n=4 返回 1→ 4→ 3→ 2→ 5→ NULL1→4→3→2→5→NULL.

数据范围： 链表长度 0 < size <= 10000<size≤1000，0 < m <= n <= size0<m≤n≤size，链表中每个节点的值满足 |val| <= 1000∣val∣≤1000