小林coding数据结构与算法

WARNING

这方面基础有些薄弱，专门来复习复习

来源与小林coding中的文章，结合自己的情况做笔记

跳转至小林coding

手撕CAS

/**
 * @author York
 * @className SpinLockDemo
 * @date 2024/09/14 22:00
 * @description 手撕CAS 利用AtomicReference原子引用
 */
public class SpinLockDemo {

    AtomicReference<Thread> bookAtomicReference = new AtomicReference<>();

    public void lock(){
        Thread thread = Thread.currentThread();
        System.out.println(thread.getName() + "------come in...");
        while (!bookAtomicReference.compareAndSet(null, thread)) {
        }
    }

    public void unlock(){
        Thread thread = Thread.currentThread();
        bookAtomicReference.compareAndSet(thread,null);
        System.out.println(thread.getName() + "------come out...");
    }

    public static void main(String[] args) {
        SpinLockDemo spinLockDemo = new SpinLockDemo();
        new Thread(() -> {
            spinLockDemo.lock();
            try {TimeUnit.SECONDS.sleep(2);} catch (InterruptedException e){ e.printStackTrace();}
            spinLockDemo.unlock();
        }).start();
        // 为了让上面那个线程先持有锁, 让下面的锁争用
        try {TimeUnit.MILLISECONDS.sleep(500);} catch (InterruptedException e){ e.printStackTrace();}

        new Thread(() -> {
            spinLockDemo.lock();
            System.out.println(Thread.currentThread().getName() + " says:------I got it...");
            spinLockDemo.unlock();
        }).start();
    }
}

如何使用两个栈实现队列？

使用两个栈实现队列的方法如下:

1. 准备两个栈，分别称为 stackPush 和 stackPop 。
2. 当需要入队时，将元素压入 stackPush 栈。
3. 当需要出队时，先判断 stackPop 是否为空，如果不为空，则直接弹出栈顶元素;如果为空，则将stackpush 中的所有元素依次弹出并压入 stackPop 中，然后再从 stackPop 中弹出栈顶元素作为出队元素。
4. 当需要査询队首元素时，同样需要先将 stackPush 中的元素转移到 stackPop 中，然后取出 stackPop的栈顶元素但不弹出。
5. 通过上述方法，可以实现用两个栈来模拟队列的先进先出(FIFO)特性。

这种方法的时间复杂度为O(1)的入队操作，均摊时间复杂度为0(1)的出队和査询队首元素操作

import java.util.Stack;

class MyQueue{
    private Stack<Integer> stackPush;
    private Stack<Integer> stackPop;
    
    public MyQueue(){
        this.stackPush = new Stack<>();
        this.stackPop = new Stack<>();
    }
    
    public void push(int x){
        this.stackPush.puhs(x);
    }
    
    
    public int pop(){
        // 先看出栈是否有元素，这代表上一次出栈的时候头部还未全部弹出
        // 它们还属于头部元素
        if(this.stackPop.isEmpty()){
           while(!this.stackPush.isEmpty()){
               this.stackPop.push(this.stackPush.pop());
           } 
        }
        // 这时就是一个公共操作了，从出栈中弹出一个，这就是队首
        return this.stackPop.pop();
    }
    
    public int peek(){
        if(this.stackPop.isEmpty()){
           while(!this.stackPush.isEmpty()){
               this.stackPop.push(this.stackPush.pop());
           } 
        }
        return this.stackPop.peek();
    }
    
    public boolean empty(){
        return this.stackPush.isEmpty() && this.stackPop.isEmpty();
    }
    
}

平衡二叉树结构是怎么样的？

使用二叉树搜索树的目的之一是缩短插入、删除、修改和査找(插入、删除、修改都包括查找操作)节点的时间。

关于查找效率，如果一棵树的高度为h，在最坏的情况，查找一个关键字需要对比h次，查找时间复杂度不超过 O(h)。一棵理想的二叉搜索树所有操作的时间可以缩短到 O(logn)(n 是节点总数)。

然而 0(h) 的时间复杂度仅为 理想情况。在最坏情况下，搜索树有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树，那么它的性质就和链表一样，所有操作(增删改査)的时间是O(n)。

可以发现操作的复杂度与树的高度h有关，由此引出了平衡树，通过一定操作维持树的高度(平衡性)来降低操作的复杂度。

所谓的平衡树是指一种改进的二叉査找树，顾名思义平衡树就是将二叉查找树平衡均匀地分布，这样的好处就是可以减少二又查找树的深度。

一般情况下二又查找树的查询复杂度取决于目标节点到树根的距离(即深度)当节点的深度普遍较大时，查询的平均复杂度就会上升，因此为了实现更高效的查询就有了平衡树。

平衡二叉树平衡的特性:

• 左右两个子树的高度差(平衡因子)的绝对值不超过1
• 左右两个子树都是一棵平衡二叉树
• 非平衡二叉树(左)和平衡二叉树(右)如下图所示:

分析:

• 图一是一个平衡二又树，它满足平衡二又树的定义。
• 图二不是平衡二叉树，其原因并不是不满足平衡因子的条件，而是因为它不满足二叉搜索树的构成条件，这提醒我们平衡二又树首先要是一棵二又搜索树。
• 图三满足平衡二叉树的构成条件。
• 图 4 中的节点(8)平衡因子为 3，不满足平衡二又树的要求。

红黑树说一下，跳表说一下？

红黑树(Red-Black Tree)

是一种自平衡的二又搜索树，它在插入和删除操作后能够 通过旋转和重新着色来保持树的平衡 。红黑树的特点如下:

1. 每个节点都有一个颜色，红色或黑色,
2. 根节点是黑色的。
3. 每个叶子节点(NIL节点)都是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 从根节点到叶子节点或空子节点的每条路径上，黑色节点的数量是相同的。

红黑树通过这些特性来保持树的平衡，确保最长路径不超过最短路径的两倍，从而保证了在最坏情况下的搜索、插入和删除操作的时间复杂度都为O(logN)。

红黑树插入节点的过程，具有自平衡性：

跳表（Skip List）

是一种基于链表的数据结构，它通过多层索引来加速搜索操作

跳表的特点如下:

1. 跳表中的数据是有序的。
2. 跳表中的每个节点都包含一个指向下一层和右侧节点的指针。

跳表通过多层索引的方式来加速搜索操作。最底层是一个普通的有序链表，而上面的每一层都是前一层的子集，每个节点在上一层都有一个指针指向它在下一层的对应节点。这样，在搜索时 可以通过跳过一些节点，直接进入目标区域，从而减少搜索的时间复杂度。

跳表的平均搜索、插入和删除操作的时间复杂度都为0(logN)，与红黑树相比，跳表的实现更加简单，但空间复杂度稍高。跳表常用于需要高效搜索和插入操作的场景，如数据库、缓存等。

时间复杂度：

搜索操作的时间复杂度:O(log n)，其中n是跳表中元素的数量。这是因为跳表中使用多级索引，可以通过跳跃的方式快速定位到目标元素所在的位置，从而将搜索的时间复杂度降低到对数级别。

插入和删除操作的时间复杂度:0(log n)，其中n是跳表中元素的数量。与搜索操作类似，插入和删除操作也可以通过跳跃的方式快速定位到需要插入或删除的位置，并进行相应的操作。因此，插入和删除的时间复杂度也是对数级别的，

二叉树搜索最坏的时间复杂度，为什么会这样？以及用什么结果解决？

先说结论，每次插入的元素是二叉查找树中最大（或者最小，就是要么一直最大，要么一直最小）的元素，二叉查找树就退化成一个链表，时间复杂度自然就是O(n)

为了解决这种问题，于是提出了 平衡二叉查找树（AVL树）

比起二叉查找树添加添加条件约束：每个节点的左子树和右子树的高度差不能超过1，即整个树是平衡二叉查找树的话，他的每个子树也是平衡二叉查找树，下图展示自平衡的过程

B+树和B树有什么不一样，B+树的叶子节点和非叶子节点有什么不一样，非叶子节点会不会存数据？

• 检索路径：B树在查找数据时，可能在非叶子节点找到目标数据，路径长度不固定。即查找时可以在任意一个节点终止。B+树中所有数据都在叶子节点，查找数据时必须走到叶子节点，路径长度固定(均等)。即查找总是要到叶子节点结束
• 叶子节点结构：B树中叶子节点之间没有特别的链接，彼此独立。B+树中叶子节点通过指针连接，形成一个有序链表，便于范围查询和顺序访问。
• 非叶子节点内容：B树中非叶子节点存储数据和索引。B+树中非叶子节点只存储索引，不存储实际数据。因此，当数据量比较大时，相对于B树，B+树的层高更少，查找效率也就更高
• 高效地范围查询：B+树叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而B树在进行范围查询时需要进行中序遍历，性能较差。

堆是什么？

首先，堆是一颗完全二叉树（也被称为 二叉堆）。堆中节点的值都大于等于（或者小于等于，这时称为 小顶堆）其子节点的值，这时称为 大顶堆

LRU是什么？如何实现？

LRU即，最近最少使用，是一种缓存淘汰算法，当缓存空间已满时，优先淘汰最长时间未被访问的数据，实现是 哈希表+双向链表

之前我们背八股的时候，遇到 LinkedHashMap，他天生可以作为LRU算法的数据结构，因为他的一个属性 accessOrder 打开以后就会在访问时不断地更新链表的顺序结构

// 创建一个带有 LRU 机制的 LinkedHashMap
LinkedHashMap<K, V> lruCache = new LinkedHashMap<>(initialCapacity, loadFactor, true);
// 第三个参数 true 表示按访问顺序（Access Order）排列节点，这样最近访问的节点会被移到队列的末尾，从而启用 LRU 功能。

最近访问的节点会被移到队列的末尾（这个是LinkedHashMap的实现，不是说必须得在末尾）

需要重写removeEldestEntry 方法

// 为了实现 LRU 缓存，当缓存达到某个大小时，需要移除最少使用的元素。通过重写 LinkedHashMap 的 removeEldestEntry 方法，可以自动删除最不常用的元素：
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > MAX_ENTRIES;  // 当缓存大小超过设定的最大值时，删除最老的元素
}

具体实现步骤如下:

• 使用哈希表存储数据的键值对，键为缓存的键，值为对应的节点。
• 使用双向链表存储数据节点，链表头部为最近访问的节点，链表尾部为最久未访问的节点。当数据被访问时，如果数据存在于缓存中，则将对应节点移动到链表头部；如果数据不存在于缓存中则将数据添加到缓存中，同时创建一个新节点并插入到链表头部
• 当缓存空间已满时，需要淘汰最久未访问的节点，即链表尾部的节点

上面这种思想方式，LRU 算法可以在 O(1)的时间复杂度内实现数据的插入、查找和删除操作。每次访问数据时，都会将对应的节点移动到链表头部，保证链表头部的节点是最近访问的数据，而链表尾部的节点是最久未访问的数据。当缓存空间不足时，淘汰链表尾部的节点即可

布隆过滤器怎么设计？时间复杂度？

问题引出

在开发过程中，经常要判断一个元素是否在一个集合中。假设你现在要给项目添加IP黑名单功能，此时你手上有大约 1亿个恶意IP的数据集，有一个IP发起请求，你如何判断这个IP在不在你的黑名单中?

类似这种问题用Java自己的Collection和Map很难处理，因为它们存储元素本身，会造成内存不足，而我们只关心元素存不存在，对于元素的值我们并不关心，具体值是什么并不重要

「布隆过滤器」可以用来解决类似的问题，具有运行快速，内存占用小的特点，它是一个保存了很长的级制向量，同时结合 Hash 函数实现的。而高效插入和査询的代价就是，它是一个基于概率的数据结构，只能告诉我们一个元素绝对不在集合内，对于存在集合内的元素有一定的误判率。

布隆过滤器中 总是会存在误判率，因为哈希碰撞是不可能百分百避免的。布隆过滤器对这种误判率称之为「假阳性概率」，即:False Positive Probability，简称为 fpp。在实践中使用布隆过滤器时可以自己定义个 fpp，然后就可以根据布隆过滤器的理论计算出需要多少个哈希函数和多大的位数组空间。需要注意的是这个 fpp 不能定义为 100%，因为无法百分保证不发生哈希碰撞。

下图表示向布隆过滤器中添加元素 ww.123.com 和 ww.456.com 的过程，它使用了 func1 和 func2 两个简单的哈希函数。

基本原理如下:

1. 初始化：当我们创建一个布隆过滤器时，我们首先创建一个全由0组成的位数组(bit array)。

   同时，我们还需选择几个独立的哈希函数，每个函数都可以将集合中的元素映射到这个位数组的某个位置。

2. 添加元素：在布隆过滤器中添加一个元素时，我们会将此元素通过所有的哈希函数进行映射，得到在位数组中的几个位置，然后将这些位置标记为1。

3. 查询元素：如果我们要检查一个元素是否在集合中，我们同样使用这些哈希函数将元素映射到位数组中的几个位置，如果所有的位置都被标记为1，那么我们就可以说该元素可能在集合中。如果有任何一个位置不为1，那么该元素肯定不在集合中，

通过其原理可以知道，我们可以提高数组长度以及 hash 计算次数来降低误报率，但是相应的 CPU、内存的消耗也会相应地提高，会增加存储和计算的开销。因此，布隆过滤器的使用需要在误判率和性能之间进行权衡。

布隆过滤器有以下两个特点:

• 只要返回数据不存在，则肯定不存在
• 返回数据存在，不一定存在

布隆过滤器的误判率主要来源于「哈希碰撞」。因为位数组的大小有限，不同的元素可能会被哈希到相同的位置，导致即使某个元素并未真正被加入过滤器，也可能因为其他已经存在的元素而让所有哈希函数映射的位都变为了1，从而误判为存在。这就是布降过滤器的 “假阳性“ 错误。在有限的数组长度中存放大量的数据，即便是再完美的 Hash 算法也会有冲突，所以有可能两个完全不同的 A、8两个数据最后定位到的位置是一模一样的。这时拿B进行查询时那自然就是误报了

布隆过滤器的时间复杂度和空间复杂度：对于一个m(比特位个数)和k(哈希函数个数)值确定的布隆过滤器，添加和判断操作的时间复杂度都是 0(k)，这意味着每次你想要插入一个元素或者查询一个元素是否在集合中，只需要使用k个哈希函数对该元素求值，然后将对应的比特位标记或者检查对应的比特位即可。

排序算法

• 冒泡排序：通过相邻元素的比较和交换，每次将最大(或最小)的元素逐步“冒泡“到最后(或最前)
• 插入排序：将待排序元素逐个插入到已排序序列的合适位置，形成有序序列。
• 选择排序(Selection 0Sort)：通过不断选择未排序部分的最小(或最大)元素，并将其放置在已排序部分的末尾(或开头)。
• 快速排序(Quick Sort)：通过选择一个基准元素，将数组划分为两个子数组，使得左子数组的元素都小于(或等于)基准元素，右子数组的元素都大于(或等于)基准元素，然后对子数组进行递归排序。
• 归并排序(Merge Sort)：将数组不断分割为更小的子数组，然后将子数组进行合并，合并过程中进行排序。
• 堆排序(Heap Sort)：通过将待排序元素构建成一个大顶堆(或小顶堆)，然后将堆顶元素与末尾元素交换，再重新调整堆，重复该过程直到排序完成。

讲一下冒泡排序算法

每一轮的任务就是把当前轮中的最大值放在当前轮的最后一个位置，比如原数组有 n 个元素，那么需要重复操作 n - 1 轮，这样最后的结果就是从小到大排列的（反之就是把最小的放在最前面）

所以冒泡的关键就在于每一轮当中，如何把当前轮最大的（或最小的）移动到最后（最前），只需要简单的交换即可。拿从小到大排列来说，随着从左向右遍历的进行，一轮中循环的每一次（循环变量是靠前的索引，每次控制当前索引以及后一个）都是较大的在后，这样就可以保证在这一轮循环中的第一次以后，索引处都指的是上一次循环的最大值，这个最大值在动态的变化过程中，体现在最后就是这一轮的最大数被移动到了最后一个位置。

public void bubbleSort(int[] arr){
    int n = arr.length;
    
    for(int i = 0; i < n -1; i++){
        for(int j = 0; j < n - 1 -i; j++){
            if(arr[j] > arr[j + 1]){
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

讲一下快排原理

快排使用了 分治策略 的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

快排的过程简单的说只有三步:

• 首先从序列中选取一个数作为基准数
• 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边(一次快排partition)
• 然后分别对基准的左右两边重复以上的操作，直到数组完全排序

具体按以下步骤实现:

1. 创建两个指针分别指问数组的最左端以及最右端
2. 在数组中 任意 取出一个元素作为基准数
3. 左指针开始向右移动，遇到比基准大的停止
4. 右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
5. 重复3，4，直到左指针超过右指针（其实就是两个指针发生了 交叉，这个时候也就说明了在基准值的两侧已经是小于基准的和大于基准的两部分了），此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
6. 然后分别对基准的左右两边重复以上的操作，直到数组完全排序

注意这里的基准该如何选择？最简单的一种做法是每次都是选择 最左边的 元素作为基准，但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过 Math.random()来随机选取一个数作为基准。

// 快速排序主方法
public static void quickSort(int[] array, int left, int right) {
    if (left < right) {
        // 获取分区点
        int partitionIndex = partition(array, left, right);

        // 分别对左右部分递归排序
        quickSort(array, left, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, right);
    }
}

// 分区方法：实现按步骤进行分区
private static int partition(int[] array, int left, int right) {
    // 任意选择一个基准数（这里选择最右边的元素）
    int pivot = array[right];
    int i = left;  // 左指针
    int j = right - 1;  // 右指针

    while (i <= j) {
        // 3. 左指针向右移动，直到找到比基准数大的元素
        while (i <= j && array[i] <= pivot) {
            i++;
        }

        // 4. 右指针向左移动，直到找到比基准数小的元素
        while (i <= j && array[j] >= pivot) {
            j--;
        }

        // 交换左右指针的元素
        if (i < j) {
            swap(array, i, j);
        }
    }

    // 5. 当两个指针交叉时，将基准数放在正确位置，即左指针位置
    swap(array, i, right);

    // 返回基准数的位置索引
    return i;
}

// 交换数组中两个元素
private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

快排时间复杂度

快速排序的流程如下:

• 从数组中选择一个基准元素(通常是数组中间位置的元素)。
• 将数组分成两部分，小于基准元素的放在左边，大于基准元素的放在右边。
• 递归地对左右两部分进行快速排序。

快速排序的时间复杂度为0(n log n)，其中n为数组的长度。最坏情况下时间复杂度为O(n^2)，发生在每次选择的基准元素都是最大或最小值时。平均情况下时间复杂度为0(n log n)，效率较高。

快排为什么时间复杂度最差是0(n^2)

主要是因为在每次划分时选择的基准元素不合适导致的。当每次选择的基准元素都是当前子数组中的最大或最小元素时，就会导致每次划分只能减少一个元素，而不是均匀地分成两部分，从而造成时间复杂度达到O(n^2)。

这种情况通常发生在数组已经有序或基本有序的情况下。为了避免最坏情况发生，可以通过 随机选择基准元素 或者 使用三数取中法 等策略来提高快速排序的性能。

快排这么强，那冒泡排序还有必要吗?

冒泡排序在一些特定场景下仍然有其优势，比如:

• 对于小规模数据或基本有序的数据，冒泡排序可能比快速排序更简单、更直观。
• 冒泡排序是稳定排序算法，相对于快速排序的不稳定性，在某些情况下可能更适合要求稳定性的场景
• 冒泡排序是原地排序算法，不需要额外的空间，适合空间复杂度要求严格的场景

堆排序算法原理，稳定吗？

堆的要求:

• 必须是完全二叉树
• 堆中的每一个节点，都必须大于等于(或者小于等于)其子树中 每个节点 的值，

堆通常是使用 一维数组 进行保存，节省空间，不需要存左右子节点的指针，通过下标就可定位左右节点和父节点。在起始位置为0的数组中:

父节点i的左子节点在*(2i+1)* 的位置

父节点i的右子节点在 (2i+2) 的位置

子节点i的父节点在 (i-1)/2 向下取整的位置

我们可以把堆排序的过程大致分为两大步骤，分别是 建堆 和 排序。

建堆:建堆操作就是将一个无序的数组转化为最大堆的操作，首先将数组原地建一个堆。“原地”的含义就是不借助另一个数组，就在原数组上操作。我们的实现思路是从后往前处理数据，并且每个数据都是从上向下调整。

排序:建堆结束后，数组中的数据已经按照大顶堆的特性进行组织了，数组中的第一个元素就是堆顶也就是最大的元素。我们把它和最后一个元素交换，那最大的元素就放到了下标为n的位置，时末尾元素就是最大值，将剩余元素重新堆化成一个大顶堆。继续重复这些步骤，直至数组有序排列

假设我们有一个数组[4,10,3,5,1]，堆排序的过程如下:

1. 构建最大堆:[10,5,3,4, 1]
2. 交换堆顶元素与最后一个元素:[1,5,3,4,10]
3. 调整剩余元素为堆:[5,4,3,1]
4. 再次交换堆顶元素与最后一个元素:[1,4,3,5]
5. 调整剩余元素为堆:[4,3, 1]
6. 继续上述过程直到排序完成:[1,3,4,5, 10]

public static void heapSort(int[] array) {
    int n = array.length;

    // 1. 建堆操作（从最后一个非叶子节点开始向前构建最大堆）
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }

    // 2. 排序：将堆顶元素（最大值）与末尾元素交换，调整剩余部分
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大值（堆顶）与数组末尾元素交换
        swap(array, 0, i);

        // 调整剩下的部分为堆
        heapify(array, i, 0);
    }
}

// 堆化函数，将以 i 为根节点的子树调整为最大堆
private static void heapify(int[] array, int n, int i) {
    int largest = i;  // 假设当前节点 i 是最大值
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2;  // 右子节点

    // 如果左子节点存在并且大于根节点，更新最大值
    if (left < n && array[left] > array[largest]) {
        largest = left;
    }

    // 如果右子节点存在并且大于当前最大值，更新最大值
    if (right < n && array[right] > array[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，交换并递归堆化受影响的子树
    if (largest != i) {
        swap(array, i, largest);
        heapify(array, n, largest);
    }
}

// 交换数组中的两个元素
private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

现在我们来分析一下堆排序的时间复杂度、空间复杂度以及稳定性。整个堆排序的过程中，只需要个别的临时存储空间，所以 堆排序是原地排序算法。

堆排序包括建堆和排序两个操作，建堆的时间复杂度是0(n)，排序过程时间复杂度是O(nlogN)。所以堆排序的整个时间复杂度是0(nlogN)。

因为在排序的过程中，存在将堆的最后一个节点跟堆顶互换的操作，所以有 可能会改变值相同数据的原始相对顺序，所以堆排序不是稳定的排序算法。例如，假设我们有两个相同的元素A和B，且A在B前面。在构建和调整堆的过程中，B可能被移动到A的前面，从而破坏了它们原来的相对顺序。