线段树

线段树SegmentTree

并查集

点击蓝字，了解详情！

种类并查集

概念

一.什么是种类并查集？

顾名思义就是把一个集合中的元素根据他们不同的关系进行分类与合并。朋友的朋友就是朋友（普通并查集）

，但敌人的敌人也是朋友（维护这种关系就是种类并查集了）。例如：有一伙人他们要拔河（分成两个队），如果小a与小b是敌对关系，那么就不能在一个队，如果小a与小c是朋友，那么他们就在一个队；(朋友的朋友就是朋友，敌人的敌人也是朋友。

) 种类并查集的作用就是不让两个有敌对关系的人在同一个队伍

二.种类并查集的应用

把朋友放在同一集合里，把敌人放另一集合里。放一起会打架开两倍pre数组，一倍放朋友，二倍放敌人。如果关系再多点那就再开大点呗。

例题：蓝桥侦探（middle）

import java.io.*;
public class demo77_种类并查集_蓝桥侦探 {
    static int N = 500000;
    static int M = 500000;
    static int n, m;
    static int[] pre = new int[2 * N + 5];
    static int[] rank = new int[2 * N + 5];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);//大臣的数量
        m = Integer.parseInt(first[1]);//口供的数量
        init(n);
        int x, y;
        for (int i = 0; i < m; i++) {
            String[] temp = br.readLine().split(" ");
            x = Integer.parseInt(temp[0]);
            y = Integer.parseInt(temp[1]);
            if (find(x) != find(y)) {
                join(x, y + n);
                join(x + n, y);
            } else {
                System.out.println(x);
                break;
            }
        }
    }
    static void init(int n) {
        for (int i = 0; i < 2 * n + 5; i++) {//两种关系 --> 开两倍
            pre[i] = i;
            rank[i] = i;
        }
    }
    static int find(int x) {
        if (pre[x] == x) return x;
        return pre[x] = find(pre[x]);
    }
    static void join(int x, int y) {
        x = find(x);
        y = find(y);
        if (rank[x] > rank[y]) pre[y] = x;
        else {
            if (rank[x] == rank[y]) rank[y]++;
            pre[x] = y;
        }
    }
}

常用函数

1.Integer.toString(int par1,int par2),par1表示要转成字符串的数字，par2表示要转成的进制表示
        Integer.toString(22),表示把22转成10进制表示的字符串
        Integer.toString(22,2),表示把22转成2进制表示的字符串
2. Integer.parseInt(String)
        将String字符类型数据转换为Integer整型数据,遇到一些不能被转换为整型的字符时，会抛出异常。
3. String.valueOf() 
用法如下: 
        　　int i = 10; 
        　　String str = String.valueOf(i); 
        　　这时候 str 就会是 "10"
（1）String.valueOf(Object obj) : 将 obj 对象转换成 字符串, 等于 obj.toString() 
                        // int、float、double、char、boolean、long类型等
（2）String.valueOf(char[] data) : 将 char 数组 data 转换成字符串 
（3）String.valueOf(char[] data, int offset, int count) : 将 char 数组 data 中 由 data[offset] 开始取 count 个元素 转换成字符串         
4.str.charAt(i);的作用
 String str = "leetcode";
则   str.charAt(0) 为"l"
                str.charAt(1) 为"e"
                str.charAt(2) 为"e"

二分

“二分“==“二分查找“ ？“yes“：“no“；

单调栈

单调栈图文详解（附Java模板）

常用集合

`你会发现，所有容器几乎都是 add或者push添加元素，pop或者remove之类的删除元素 ， find()之类的查找元素 ，只不过底层实现可能不同 `
### ArrayList：底层是一个数组，擅长数据的查找（访问）
### LinkedList：底层链表，擅长数据的修改（包括数据添加和删除）
### Queue：队列
>Queue<Node> queue = new LinkedList<>();
队列常用方法
　add        增加一个元索                           如果队列已满，则抛出一个IIIegaISlabEepeplian异常
　remove   移除并返回队列头部的元素     如果队列为空，则抛出一个NoSuchElementException异常
　element  返回队列头部的元素                如果队列为空，则抛出一个NoSuchElementException异常
　offer       添加一个元素并返回true           如果队列已满，则返回false
　poll         移除并返问队列头部的元素      如果队列为空，则返回null
　peek       返回队列头部的元素                如果队列为空，则返回null
　put         添加一个元素                           如果队列满，则阻塞
　take        移除并返回队列头部的元素     如果队列为空，则阻塞
   drainTo(list)   一次性取出队列所有元素
知识点： remove、element、offer 、poll、peek 其实是属于Queue接口。 
### HashSet：集合
>public boolean retainAll(Collection c)
此方法将集合c作为包含要从该集合保留的元素的参数。
例如：
tempSet.retainAll(allAreas);//求出tempSet 和   allAreas 集合的交集, 交集会赋给 tempSet
### Map ：键值对
>元素查询的操作：
Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：是否包含指定的key
boolean containsValue(Object value)：是否包含指定的value
int size()：返回map中key-value对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数对象obj是否相等
```java
@Test
public void test2() {
    Map map = new HashMap();
    map.put("AA", 123);
    map.put("ZZ", 251);
    map.put("CC", 110);
    map.put("RR", 124);
    map.put("FF", 662);
    System.out.println(map);//{AA=123, ZZ=251, CC=110, RR=124, FF=662}
    //Object get(Object key)：获取指定key对应的value
    System.out.println(map.get("AA"));//123
    //boolean containsKey(Object key)：是否包含指定的key
    System.out.println(map.containsKey("ZZ"));//true
    //boolean containsValue(Object value)：是否包含指定的value
    System.out.println(map.containsValue(123));//true
    //int size()：返回map中key-value对的个数
    System.out.println(map.size());//5
    //boolean isEmpty()：判断当前map是否为空
    System.out.println(map.isEmpty());//false
    //boolean equals(Object obj)：判断当前map和参数对象obj是否相等
    Map map1 = new HashMap();
    map1.put("AA", 123);
    map1.put("ZZ", 251);
    map1.put("CC", 110);
    map1.put("RR", 124);
    map1.put("FF", 662);
    System.out.println(map.equals(map1));//true
}

将map集合中的所有value取出，放入Collection集合中

//Collection中Type的类型，取决于map中value的类型

Collection values = map.values();

System.out.println(values);//[女儿国国王, 黑熊精, 黄毛怪, 黑熊精]

map集合的迭代

            /**方式一：
             * 遍历map中的数据，但是map本身没有迭代器，所以需要先转换成set集合
             * Set<Key>:把map中的所有key值存入到set集合当中--keySet()*/
            //4.1将map集合中的key值取出存入set集合中，集合的泛型就是key的类型Integer
            Set<Integer> keySet = map.keySet();
            //4.2想要遍历集合就需要获取集合的迭代器
            Iterator<Integer> it = keySet.iterator();
            //4.3循环迭代集合中的所有元素
            while(it.hasNext()){//判断是否有下一个元素可以迭代
                Integer key = it.next();//拿到本轮循环中获取到的map的key
                String value = map.get(key);
                System.out.println("{"+key+","+value+"}");
            }
            /**方式二：
             * 遍历map集合，需要把map集合先转成set集合
             * 是把map中的一对键值对key&value作为一个Entry<K,V>整体放入set
             * 一对K,V就是一个Entry*/
            Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
            //获取迭代器
            Iterator<Map.Entry<Integer, String>> it2 = entrySet.iterator();
            while(it2.hasNext()){//判断是否有下一个元素可迭代
                //本轮遍历到的一个Entry对象
                Map.Entry<Integer, String> entry = it2.next();
                Integer key = entry.getKey();//获取Entry中的key
//                Integer key2 = it2.next().getKey();//效果同上
                String value = entry.getValue();//获取Entry中的value
                System.out.println("{"+key+","+value+"}");
            }

PriorityQueue：优先队列（堆）

PriorityQueue<Integer> heap = new PriorityQueue<>();// 默认情况下是小根堆
//也可以用比较器来改变排序方法，从而达到自定义大小根堆的目的
PriorityQueue<Integer> smallHeap = new PriorityQueue<>((a, b) -> a - b);
PriorityQueue<Integer> bigHeap = new PriorityQueue<>((a, b) -> b - a);
//接下来遍历堆，大根堆是从大到小的，小跟堆是从小到大的
for (Integer integer : heap) {
    System.out.print(integer + " ");
}
//你可以自定义排序方式，通过实现 Comparator 接口，并将其作为参数传递给 PriorityQueue 的构造函数，从而在堆中实现自定义的排序。例如：
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});
//lamda例如:
PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> o1.len - o2.len);
这样就实现了从大到小的自定义排序。

1、PriorityQueue概述

Java PriorityQueue 实现了 Queue 接口，不允许放入 null 元素；其通过堆实现，具体说是

通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不

大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue 的底层实现，

数组初始大小为11；也可以用一棵完全二叉树表示。

优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次

取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判

可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较

（Comparator，类似于C++的仿函数）。

2、常用方法总结

public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构
public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构
public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出null
public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator<E> iterator(); //迭代器

3、堆结构调整

每次插入或删除元素后，都对队列进行调整，使得队列始终构成最小堆（或最大堆）。

具体调整如下：

插入元素后，从堆底到堆顶调整堆；
删除元素后，将队尾元素复制到队头，并从堆顶到堆底调整堆。
小根堆结构调整插入（ add()和offer()方法）元素后，向上调整堆：

//siftUp()
private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

删除（ remove()和poll()方法）元素后，向下调整堆：

//siftDown()
private void siftDown(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
        int child = (k << 1) + 1;//leftNo = parentNo*2+1
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;//然后用c取代原来的值
        k = child;
    }
    queue[k] = x;
}

4、应用：topK问题

topK问题是指：从海量数据中寻找最大的前k个数据，比如从1亿个数据中，寻找最大的1万个数。

使用优先队列，能够很好的解决这个问题。先使用前1万个数构建最小优先队列，以后每取

一个数，都与队头元素进行比较，若大于队头元素，就将队头元素删除，并将该元素添加到

优先队列中；若小于队头元素，则将该元素丢弃掉。如此往复，直至所有元素都访问完。最

后优先队列中的1万个元素就是最大的1万个元素。

例1：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。你需要找的是数组

排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

public class Main {
   public static void main(String[] args) {
       //int[] arr = new int[]{3,2,1,5,6,4};
       int[] arr = new int[]{3,2,3,1,2,4,5,5,6};
       int k = 4;
       test(arr,k);
   }
   /**
    * 方法三：PriorityQueue 优先队列思想
    * 返回数组第k个最大数据
    * @param nums
    * @param k
    */
   public static int findKthLargest3(int[] nums, int k){   //时间复杂度：O(NlogK)，遍历数据 O(N)，堆内元素调整 O(K)，空间复杂度：O(K)
       int len = nums.length;
       // 使用一个含有 k 个元素的最小堆
       // k 堆的初始容量，(a,b) -> a -b 比较器
       PriorityQueue<Integer> minTop = new PriorityQueue<>(k,(a, b) -> a -b);
       for (int i = 0; i < k; i++){
           minTop.add(nums[i]);
       }
       for (int i = k; i < len; i++){
           Integer topEle = minTop.peek();  // 返回队头元素（不删除），失败时前者抛出null
           // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
           if (nums[i] > topEle){
               minTop.poll();  // 获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构
               minTop.offer(nums[i]);  // 在队尾插入元素，插入失败时抛出false，并调整堆结构
           }
       }
       return minTop.peek();
   }
   public static void test(int[] input,int key){
       long begin = System.currentTimeMillis();
       int result = findKthLargest3(input,key);
       System.out.println("result = " + result);
       long end = System.currentTimeMillis();
       System.out.println();
       System.out.println("耗时:" + (end - begin) + "ms");
       System.out.println("--------------------");
   }
}

运行结果：

例2：

求数组nums={6,14,71,21,9,18,1,4,23,0,45,66} 中最大的5个数

import java.util.PriorityQueue;
public class Main {
        static int[] nums={6,14,71,21,9,18,7,4,23,0,45,66};
        public static void main(String[] args) {
                topK();
        }
        public static void topK() {
                PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
                for(int i=0; i<5; i++) {
                        queue.add(nums[i]);
                }
                for(int i=5; i<12; i++) {
                        if(nums[i] > queue.element()) {
                                queue.remove();
                                queue.add(nums[i]);
                        }
                }
                while(!queue.isEmpty()) {
                        int Ele=queue.remove();
                        System.out.print(Ele+" ");
                }
        }
}

运行结果：

Sort

1.2.3 时间复杂度为O（n^2），4和5的时间复杂度是O（n lgN）

（1）冒泡排序：每一轮都会把大的数字往后挪

（2）插入排序：每一轮把当前的元素往前比较，然后插入到对应的位置

（3）选择排序：每一轮找到剩下空间中最小的值，然后把它放到区间的最前面

（4）堆排序：每次弹出堆顶元素，然后用剩下的元素调整堆，不停重复这个过程

（5）快速排序

每一轮找到一个基准位置（一般选择最开头的元素），然后把比基准大的元素放到基准的右边，把比基准小的元素放到基准的左边，这样的话就会以基准为界，形成两个区间
对这两个区间，重复上面的操作
不停的递归，最终形成数组有序

BubbleSort

package java_wuji.JXY.algorithm;
import java.util.Arrays;
public class BubbleSort {
    public static void main(String[] args) {
      int[] arr = {3, 9, -1, 10, 20};
        //测试冒泡排序
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void bubbleSort(int[] arr) {
        // 冒泡排序 的时间复杂度 O(n^2), 自己写出
        int temp; // 临时变量
        boolean flag = false; // 标识变量，表示是否进行过交换
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // 如果前面的数比后面的数大，则交换
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag) { // 在一趟排序中，一次交换都没有发生过
                break;
            } else {
                flag = false; // 重置flag!!!, 进行下次判断
            }
        }
    }
}

SelectSort

package java_wuji.JXY.algorithm;
import java.util.Arrays;
//选择排序
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 90, 123};
        selectSort(arr);
    }
    //选择排序
    public static void selectSort(int[] arr) {
        //选择排序时间复杂度是 O(n^2)
        for (int i = 0; i < arr.length - 1; i++) {//length - 1 是因为，当倒数第二次排序时，最后一个一定是最大值
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) { // 说明假定的最小值，并不是最小
                    min = arr[j]; // 重置min
                    minIndex = j; // 重置minIndex
                }
            }
            // 将最小值，放在arr[i], 即交换
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            System.out.println("第" + (i + 1) + "轮后~~");
            System.out.println(Arrays.toString(arr));
        }
    }
}

QuickSort

package java_wuji.JXY.algorithm;
import java.util.Arrays;
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70, -1, 900, 4561};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("arr=" + Arrays.toString(arr));
    }
    public static void quickSort(int[] arr, int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        int mid = arr[(left + right) / 2];
        int temp; //临时变量，作为交换时使用
        //while循环的目的是让比mid 值小放到左边
        //比mid 值大放到右边
        while (l < r) {
            while (arr[l] < mid) l += 1;//在mid的左边一直找,找到大于等于mid值,才退出，最坏的情况就是找到mid本身
            while (arr[r] > mid) r -= 1;//在mid的右边一直找,找到小于等于mid值,才退出
            if (l >= r) break;//如果l >= r说明mid 的左右两的值，已经按照左边全部是小于等于mid值，右边全部是大于等于mid值 --> 满足，break
            temp = arr[l];//找到两个需要交换的数 --> 交换
            arr[l] = arr[r];
            arr[r] = temp;
            //以下两个判断：由于上面的l += 1操作，如果交换完毕后，l/r下标等于中轴了，代表左/右边已经全部小/大于中轴值，则让r/l一直前/后移与中轴值进行比较
            //如果交换完后，发现这个arr[l] == mid值 相等 r--， 前移   形成l>=r的条件，以便退出循环
            if (arr[l] == mid) r--;
            //如果交换完后，发现这个arr[r] == mid值 相等 l++， 后移   形成l>=r的条件，以便退出循环
            if (arr[r] == mid) l++;
        }
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出！！！！！！！！！！因为相等的话会跳过while循环，无限递归
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) quickSort(arr, left, r);
        //向右递归
        if (right > l) quickSort(arr, l, right);
    }
}

InsertSort

package java_wuji.JXY.algorithm;
import java.util.Arrays;
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 89};
        System.out.println("从下标为1的数开始进行插入排序，每次向前找插入点，未满足条件的往后面覆盖（移动），过程如下：");
        insertSort(arr); //调用插入排序算法
//        System.out.println(Arrays.toString(arr));
    }
    //插入排序   向前比较
    public static void insertSort(int[] arr) {
        int insertVal, insertIndex;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];//定义待插入的数
            insertIndex = i - 1; // 即arr[i]前面这个数的下标
          /*
          给insertVal 找到插入的位置，说明：
          1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
          2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
          3. 就需要将 arr[insertIndex] 后移
          */
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]   没找到要插入的点，把当前的值覆盖掉后面的值（移动）
                insertIndex--;//继续向前找
            }
            // 当退出while循环时，说明插入的位置找到, insertIndex + 1
            //这里我们判断是否需要赋值
            if (insertIndex + 1 != i) arr[insertIndex + 1] = insertVal;
            System.out.println("第" + i + "轮插入");
            System.out.println(Arrays.toString(arr));
        }
    }
}

HeapSort

package java_wuji.JXY.algorithm;
import java.util.PriorityQueue;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 90, 123};
        heapSort(arr);
    }
    //堆排序
    public static void heapSort(int[] arr) {
        //选择排序时间复杂度是 O(nlogN)
        PriorityQueue<Integer> heap = new PriorityQueue<>(arr.length, (a, b) -> (b - a));//大根堆
        for (int i : arr)
            heap.offer(i);
        while (!heap.isEmpty())
            System.out.print(heap.poll()+" ");
    }
}

StackQueue

用栈来实现队列

package java_wuji.JXY.algorithm;
import java.util.Stack;
public class StackQueue {
    static Stack<Integer> inStack = new Stack<>();
    static Stack<Integer> outStack = new Stack<>();
    // 入队
    static void push(int value) {
        inStack.push(value);
    }
    // 出队
    // (1）outStack为空，把inStack里的所有元素倒入到outStack内，然后pop，注意不需要倒回去！！
    // (2) outStack不为空，直接从outStack里pop
    static int pop() {
        if (outStack.isEmpty())
            while (!(inStack.isEmpty()))
                outStack.push(inStack.pop());
        return outStack.pop();
    }
    public static void main(String[] args) {
        StackQueue sq = new StackQueue();
        sq.push(1);
        sq.push(2);
        sq.push(3);
        System.out.println(sq.pop());//1
        sq.push(4);
        System.out.println(sq.pop());//2
    }
}

双指针

public class LinkedListTest {
    public static class LinkedNode {
        public int value;
        public LinkedNode next;
    }
    public static void print(LinkedNode head) {
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }
    //判断是否有环 --- 双指针！！！
    public static boolean isCycle(LinkedNode head) {
        LinkedNode fast = head;
        LinkedNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    //返回倒数第k个节点的值(无环)
    public static int getNthFromEnd(LinkedNode head, int k) {
        LinkedNode fast = head;
        LinkedNode slow = head;
        //先让他们间隔k-1个距离，即：规定好初始时的间隔
        for (int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }
        //当fast指向最后一个结点时结束循环
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.value;
    }
    //合并两个有序无环单链表，返回新链表的头结点
    public static LinkedNode mergedTwoSortedLinkedList(LinkedNode l1, LinkedNode l2) {
        LinkedNode preHead = new LinkedNode();
        LinkedNode prev = preHead;
        while (l1 != null && l2 != null) {
            if (l1.value <= l2.value) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return preHead.next;
    }
    public static void main(String[] args) {
        LinkedNode node1 = new LinkedNode();
        node1.value = 1;
        LinkedNode node2 = new LinkedNode();
        node2.value = 2;
        LinkedNode node3 = new LinkedNode();
        node3.value = 3;
        LinkedNode node4 = new LinkedNode();
        node4.value = 4;
        node1.next = node2;
//        node2.next = node3;
        node3.next = node4;
//        node4.next = node1;//形成环
//        print(node1);
//        System.out.println(isCycle(node1));
//        System.out.println(getNthFromEnd(node1, 2));
        LinkedNode node = mergedTwoSortedLinkedList(node1, node3);
        print(node);
    }
}

TopK

package java_wuji.JXY.algorithm;
import java.util.PriorityQueue;
public class HeapTopK {
    public static void main(String[] args) {
        //int[] arr = new int[]{3,2,1,5,6,4};
        int[] arr = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k = 4;
        test(arr, k);
    }
    /**
     * 方法三：PriorityQueue 优先队列思想
     * 返回数组第k个最大数据
     *
     * @param nums
     * @param k
     */
    public static int findKthLargest3(int[] nums, int k) {   //时间复杂度：O(NlogK)，遍历数据 O(N)，堆内元素调整 O(K)，空间复杂度：O(K)
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆
        // k 堆的初始容量，(a,b) -> a -b 比较器
        PriorityQueue<Integer> minTop = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minTop.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            Integer topEle = minTop.peek();  // 返回队头元素（不删除），失败时前者抛出null
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topEle) {
                minTop.poll();  // 获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构
                minTop.offer(nums[i]);  // 在队尾插入元素，插入失败时抛出false，并调整堆结构
            }
        }
        return minTop.peek();
    }
    public static void test(int[] input, int key) {
        long begin = System.currentTimeMillis();
        int result = findKthLargest3(input, key);
        System.out.println("result = " + result);
        long end = System.currentTimeMillis();
        System.out.println();
        System.out.println("耗时:" + (end - begin) + "ms");
        System.out.println("--------------------");
    }
}

总结

算法路漫漫，最难的是坚持，希望本文能帮助到大家！

参考文献不太好例举，因为这些内容是平时日积月累下来的，

Java算法笔记（六）

线段树

并查集