StaticProxy & DynamicProxy

🙂本文主要是作者对动态代理以及静态代理简单实现 不包括CGLIB
😋如有错误欢迎请指正，获取源码可访问以下地址或联系作者邮箱
📕源码地址：https://gitee.com/dsxriiiii/l3x

静态代理

定义接口：

public interface Service {
    void doSomething();
}

实现接口的目标类：

public class ServiceImpl implements Service {
    @Override
    public void doSomething() {
        System.out.println("执行目标方法");
    }
}

创建静态代理类：

public class ServiceProxy implements Service {
    private Service target;

    public ServiceProxy(Service target) {
        this.target = target;
    }

    @Override
    public void doSomething() {
        System.out.println("在执行目标方法前进行一些操作");
        target.doSomething();
        System.out.println("在执行目标方法后进行一些操作");
    }
}

使用静态代理：

public class Main {
    public static void main(String[] args) {
        Service service = new ServiceImpl();
        Service proxy = new ServiceProxy(service);
        proxy.doSomething();
    }
}

动态代理

实现接口

public interface Service {
    void doSomething();
}

实现类

public class ServiceImpl implements Service {
    @Override
    public void doSomething() {
        System.out.println("我是动态代理の实现类(∪.∪ )...zzz");
    }
}

动态代理实现类

继承接口，实现invoke方法

public class DynamicProxyService implements InvocationHandler {
    private final Object target;

    public DynamicProxyService(Object target) {
        this.target = target;
    }
    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        System.out.println("动态代理实现类执行操作 before");
        System.out.println("动态代理方法名称：" + method.getName());
        Object invoke = method.invoke(target, args);
        System.out.println("动态代理实现类执行操作 after");
        return invoke;
    }
}

动态代理

public class DynamicProxyMain {
    public static void main(String[] args) {
        Service service = new ServiceImpl();
        Service proxy = (Service) Proxy.newProxyInstance(
                //指定类加载器
                service.getClass().getClassLoader(),
                //指定代理实现接口
                service.getClass().getInterfaces(),
                //代理对象要做的事情
                new DynamicProxyService(service));
        proxy.doSomething();
    }
}

执行结果

动态代理实现类执行操作 before
动态代理方法名称：doSomething
我是动态代理の实现类(∪.∪ )...zzz
动态代理实现类执行操作 after

排序算法总结

冒泡排序

时间复杂度：最优情况下O(n) 最坏情况下为O(n^2)
空间复杂度O(1)

确定最后一位的位置 每一次更新j的范围

/**
 * @Author DSXRIIIII
 * @Project mounts
 * @Package cn.dsxriiiii.ScenarioQuestion.Sort
 * @Date 2024/8/22 10:30
 * @Description: 冒泡排序
 * 每一次的遍历都会确定数组的【最后一位】的位置
 * j的区间范围为[0,n - 1] -> [0,n - 2] -> [0,n - 3]
 */
public class L3xBubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length - 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

//优化方案
/**
 * 冒泡排序
 * @param arr
 * @return arr
 */
public static int[] bubbleSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // Set a flag, if true, that means the loop has not been swapped,
        // that is, the sequence has been ordered, the sorting has been completed.
        boolean flag = true;
        for (int j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
       // Change flag
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
    return arr;
}

选择排序

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定排序

确定边界值 每一次内循环都会确认一个位置

/**
 * @Author DSXRIIIII
 * @Project mounts
 * @Package cn.dsxriiiii.ScenarioQuestion.Sort
 * @Date 2024/8/22 10:52
 * @Description: 选择排序
 * 每一次都可以确定最小值/最大值
 * i负责确认交换的位置 j确认最小/大值的坐标位置
 * 最后交换位置即可
 */
public class L3xSelectSort {
    public static void selectionSort(int[] arr) {
        // 外层循环，控制已排序部分的边界，i 从 0 到数组长度减 1，每一轮确定一个最小元素并放在正确位置
        for (int i = 0; i <= arr.length - 1; i++) {
            // 假设当前索引 i 对应的元素为最小元素，记录其索引为 min
            int min = i;
            // 内层循环，从 i + 1 开始遍历未排序部分，寻找最小元素
            for (int j = i + 1; j <= arr.length - 1; j++) {
                // 如果当前遍历到的元素比已假设的最小元素小
                if(arr[j] < arr[min]){
                    // 更新最小元素的索引为 j
                    min = j;
                }
            }
            // 将找到的最小元素与当前未排序部分的第一个元素（即索引为 i 的元素）交换位置
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        selectionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

快速排序

时间复杂度：最优情况下O(n(logn)) 最坏情况下为O(n^2)
空间复杂度：O(logn)

找到基准位置进行排序 将小的放左边 大的放右边

/**
 * @Author DSXRIIIII
 * @Project mounts
 * @Package cn.dsxriiiii.ScenarioQuestion.Sort
 * @Date 2024/8/21 17:36
 * @Description: 实现快速排序
 * 1.按照基准数排序
 * 2.如下的例子是对第一个数为基准
 * 3.小于基准数的值放到左边 大于基准数的值放到右边
 */
public class L3xQuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if(low < high){
            int location = partition(arr,low,high);
            quickSort(arr,low,location - 1);
            quickSort(arr,location + 1,high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 将 low 位置的元素作为划分的基准值 loc
        int loc = arr[low];
        // cur 表示从 low + 1 开始，第一个大于等于基准值的元素位置
        int cur = low + 1;
        // 遍历从 low + 1 到 high 的所有元素
        for (int i = low + 1; i <= high; i++) {
            // 如果当前元素小于基准值
            if(arr[i] < loc){
                // 将当前元素与 cur 位置的元素交换，使得小于基准值的元素都在 cur 左边
                swap(arr,i,cur);
                // cur 向右移动一位，表示下一个大于等于基准值的位置
                cur++;
            }
        }
        // 将基准值与 cur - 1 位置的元素交换，使得基准值处于正确的位置
        swap(arr,cur - 1,low);
        // 返回基准值的最终位置
        return cur - 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

插入排序

时间复杂度：最优情况下O(n) 最坏情况下为O(n^2)
空间复杂度O(1)

/**
 * @Author DSXRIIIII
 * @Project mounts
 * @Package cn.dsxriiiii.ScenarioQuestion.Sort
 * @Date 2024/8/22 11:17
 * @Description: 插入排序
 * 找到一个元素cur 找到比cur大的位置不断地往后排
 * 将cur插入到比他大的数的前面 
 * arr[index] = arr[index - 1]; 将index所处位置比较大的元素往后移->index--
 * 最后将cur元素插入到index的位置
 */
public class L3xInsertSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        // 遍历整个数组，从第一个元素开始认为是已排序部分，逐渐扩大已排序部分
        for (int i = 0; i < n; i++) {
            // 将当前要插入的元素保存到 cur
            int cur = arr[i];
            // index 用于标记当前要插入的位置
            int index = i;
            // 当 index 大于 0 且前一个位置的元素大于当前元素时，进行移动操作
            while (index > 0 && arr[index - 1] > cur) {
                // 将较大的元素向后移动一位
                arr[index] = arr[index - 1];
                // index 递减，继续向前比较
                index--;
            }
            // 找到合适位置后，将当前元素插入
            arr[index] = cur;
        }
    }
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        insertionSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

归并排序

时间复杂度O(nlogn) 空间复杂度O(n)

递归算法，注意递归结束的处理方式

/**
 * @Author DSXRIIIII
 * @Project mounts
 * @Package cn.dsxriiiii.ScenarioQuestion.Sort
 * @Date 2024/8/22 9:51
 * @Description: 归并排序
 * 1.为什么每一次k都是从0开始 因为每次arr都是一个切片
 * 2.栈溢出的情况 当数组长度为1的时候没有返回就会一直递归导致栈溢出
 */
public class L3xMergeSort {
    private static void MergeSort(int[] arr){
        if (arr.length <= 1) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];
//        for (int i = 0; i < mid; i++) {
//            left[i] = arr[i];
//        }
        //等价于下面这行代码
        System.arraycopy(arr, 0, left, 0, mid);
        for (int i = mid ; i < arr.length; i++) {
            right[i - mid] = arr[i];
        }
        MergeSort(left);
        MergeSort(right);
        Merge(arr,left,right);
    }

    private static void Merge(int[] arr, int[] left, int[] right) {
        // i 是左子数组的索引
        int i = 0;
        // k 是合并后数组 arr 的索引
        int k = 0;
        // j 是右子数组的索引
        int j = 0;

        // 当左子数组和右子数组都还有元素未处理时
        while (i < left.length && j < right.length) {
            // 如果左子数组当前元素小于右子数组当前元素
            if (left[i] < right[j]) {
                // 将左子数组当前元素放入合并后的数组 arr，并移动左子数组和合并后数组的索引
                arr[k++] = left[i++];
            } else {
                // 将右子数组当前元素放入合并后的数组 arr，并移动右子数组和合并后数组的索引
                arr[k++] = right[j++];
            }
        }

        // 当左子数组还有剩余元素时
        while (i < left.length) {
            // 将左子数组剩余元素依次放入合并后的数组 arr，并移动左子数组和合并后数组的索引
            arr[k++] = left[i++];
        }

        // 当右子数组还有剩余元素时
        while (j < right.length) {
            // 将右子数组剩余元素依次放入合并后的数组 arr，并移动右子数组和合并后数组的索引
            arr[k++] = right[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        MergeSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

堆排序

时间复杂度O(nlogn)
空间复杂度O(1)
每一次确定堆顶元素将其排列到最后一个位置
将元素一一比较并且浮现到最上层

/**
 * @Author DSXRIIIII
 * @Project mounts
 * @Package cn.dsxriiiii.ScenarioQuestion.Sort
 * @Date 2024/8/22 11:53
 * @Description: 堆排序
 * 每一次处理大顶堆确定最大的元素已经浮现到堆的根结点
 * 把根结点与最后一位交换 这样最大值就会排序到最后一位
 */
public class L3xHeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 构建最大堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 逐个提取最大元素并重新调整堆
        for (int i = n - 1; i >= 0; i--) {
            // 将最大元素（堆顶）与当前未排序部分的最后一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 对交换后的堆进行调整
            heapify(arr, i, 0);
        }
    }

    private static void heapify(int[] arr, int n, int i) {
        // 初始化当前节点 i 为最大元素的索引
        int largest = i;
        // 左子节点索引
        int left = 2 * i + 1;
        // 右子节点索引
        int right = 2 * i + 2;
        // 如果左子节点存在且大于当前最大元素
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        // 如果右子节点存在且大于当前最大元素
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果最大元素不是当前节点 i，则交换并递归调整
        if (largest!= i) {
            int temp = arr[largest];
            arr[largest] = arr[i];
            arr[i] = temp;
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        heapSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

1.线程池基本概念

线程池（Thread Pool）是⼀种基于池化思想管理线程的共具

2.为什么引入线程池

线程过多会带来额外的开销，其中包括创建销毁线程的开销、调度线程的开销等等，同时也降低了计算机的整体性能。线程池维护多个线程，等待监督管理者分配可并发执行的任务。这种做法，一方面避免了处理任务时创建销毁线程开销的代价，另一方面避免了线程数量膨胀导致的过分调度问题，保证了对内核的充分利用。

2.1.池化思想

1. 内存池(Memory Pooling)：预先申请内存，提升申请内存速度，减少内存碎⽚。
2. 连接池(Connection Pooling)：预先申请数据库连接，提升申请连接的速度，降低系统的开销。
3. 实例池(Object Pooling)：循环使⽤对象，减少资源在初始化和释放时的昂贵损耗
   

   3.ThreadPoolExecutor基本设置

   3.1ThreadPoolExecutor创建时参数信息

• corePoolSize（核心线程数）：线程池维护线程的最少数量

• maximumPoolSize（最大线程数）：线程池中允许的最大线程数。

• keepAliveTime（存活时间）：当线程数大于核心线程数时，这是多余空闲线程在终止前等待新任务的最长时间。注意，只有当线程数大于 corePoolSize 时，这个参数才会生效。

• unit（时间单位）：keepAliveTime 参数的时间单位，例如 TimeUnit.SECONDS、TimeUnit.MINUTES 等。

• workQueue（工作队列）：用于保存等待执行的任务的阻塞队列。这个队列的容量、是否有界等特性会直接影响线程池的行为。Java 提供了几种阻塞队列的实现，如 ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue 等。

• threadFactory（线程工厂）：用于创建新线程的工厂，它允许应用程序定制线程的创建过程。通过自定义的 ThreadFactory，你可以设置线程的优先级、守护线程状态、名称等。如果不指定，则使用默认的线程工厂。

• handler（拒绝策略）：当线程池和队列都满了，无法再处理新任务时，就会用到拒绝策略。Java 提供了四种拒绝策略的实现：

  1. AbortPolicy：直接抛出 RejectedExecutionException 异常。
  2. CallerRunsPolicy：使用调用者的线程来执行任务。
  3. DiscardOldestPolicy：丢弃队列中最老的任务，然后尝试重新提交被拒绝的任务。
  4. DiscardPolicy：直接丢弃无法处理的任务，不抛出异常也不执行。
     

     3.2ThreadPoolExecutor执行情况

• 回收线程时机：线程数 > corePoolSize（核心线程数）

• 创建线程时机：队列满了，并且已创建的线程数 < maximumPoolSize（最大线程数）

• 存活时间参数生效：线程数 > corePoolSize（核心线程数）也就是线程销毁的死亡倒计时

  3.3ThreadPoolExecutor运行状况

• RUNNING 接受新提交任务 也能处理阻塞队列的任务

• SHUTDOWN 不接受新提交的任务 但是可以处理阻塞队列已保存的任务

• STOP 不接受新任务 也不处理队列中的任务 会中断处理任务的进程

• TIDYING 所有任务都已终止 workerCount有效线程数为0

• TERMINATED 执行terminated方法执行完成后进入该状态

4.ThreadPoolExecutor是如何运行

⛏任务区

1. 提交任务,执行任务分配

2. 选择任务分配方式

   • 缓冲执行
   • 直接执行
   • 任务拒绝
     

     ⚙线程区

3. 线程分配

4. 线程回收

   4.1线程池运行机制

   线程池如何维护自身状态

   线程池的运行状态是伴随线程池的运行，由内部进行维护的，线程池将运行状态 runState 和 线程数量 workerCount 维护在一起

   private final AtomicInteger ctl = new AtomicInteger(ctlOf(RUNNING, 0))

   AtomicInteger类型保存 线程池信息 高3位保存线程池运行状态 低29位保存线程数量

   private static int runStateOf(int c)     { return c & ~CAPACITY; } //计算当前运⾏状态
   private static int workerCountOf(int c)  { return c & CAPACITY; }  //计算当前线程数量
   private static int ctlOf(int rs, int wc) { return rs | wc; }   //通过状态和线程数⽣成ctl

   线程池如何管理任务

   任务执行机制

   任务调度

   💡所有的任务调度都是由execute()方法执行完成的 执行过程

5. 检查线程池运行状态，如果不是RUNNING 直接拒绝，线程池要保证在RUNNING的状态下执行任务。

6. 如果workerCount < corePoolSize，则创建并启动⼀个线程来执行新提交的任务。

7. 如果workerCount >= corePoolSize，且线程池内的阻塞队列未满，则将任务添加到该阻塞队列中。

8. 如果workerCount >= corePoolSize && workerCount < maximumPoolSize，且线程池内的阻塞队列已满，则创建并启动⼀个线程来执行新提交的任务。

9. 如果workerCount >= maximumPoolSize，并且线程池内的阻塞队列已满, 则根据拒绝策略来处理该任务, 默认处理方式就是直接抛出异常

任务缓冲

使用阻塞队列作为缓冲区，生产者和消费者通过队列实现任务读取

ArrayBlockingQueue :数组实现的有界阻塞队列，FIFO排序，支持公平锁和非公平锁
LinkedBlockingQueue :链表实现 FIFO排序 默认长度为Integer.MAX_VALUE
PriorityBlockingQueue :支持线程优先级队列，可以自定义实现compareTo()方法排序
DelayQueue :基于PriorityBlockingQueue，创建元素时指定时间获取当前元素
SynchronousQueue :不存储元素的阻塞队列，每一个put操作都需要等待take操作 否则不能添加元素，支持公平锁和非公平锁
LinkedTransferQueue :链表构成的无界阻塞队列，相比其他队列多了transfer和tryTransfer方法
LinkedBlockingDeque :一个由链表结构组成的双向阻塞队列，头尾都可以增删元素，多线程并发时，可以将锁的竞争最多降低到一般

任务申请

第一种情况：线程初始创建的时候， 是任务直接由新创建的线程执行
第二种情况：线程获取任务绝大多数情况， 线程从任务 队列中获取任务然后执行，执⾏完任务的空闲线程会再次去从队列中申请任务再去执行

线程池获取任务 getTask 这部分进行了多次判断，为的是控制线程的数量，使其符合线程池的状态。如果线程池现在不应该持有那么多线程，则会返回 null 值。工作线程 Worker 会不断接收新任务去执行，而当工作线程 Worker 接收不到任务的时候，就会开始被回收。

任务拒绝

拒绝策略
AbortPolicy :丢弃任务并且抛出RejectedExecutionException异常,线程池默认拒绝策略，反馈程序运行状态
DiscardPolicy :丢弃任务并且不会抛出异常
DiscardOldestPolicy :丢弃队列最前面的任务，重新提交被拒绝的任务，就是是否丢弃老任务
CallerRunsPolicy :当任务添加到线程池中被拒绝时，不是将任务丢弃，也不是抛出异常，而是将任务回退到调用者线程中执行。这种策略可以看作是一种调节机制，既不会抛弃任务，也不会因为线程池无法接受新任务而抛出异常，而是尝试在调用者线程中直接执行这些任务，从而减轻线程池的压力

线程池如何管理线程

Worker线程管理

Worker线程 : 线程池为了掌握线程的状态并维护线程的生命周期，设计了线程池内的工作线程Worker

private final class Worker extends AbstractQueuedSynchronizer implements Runnable{
    final Thread thread;//Worker持有的线程
    Runnable firstTask;//初始化的任务，可以为null
}

Worker线程初始化了一个 Thread 和 firstTask ,如果 firstTask 不为空，那么 Thread 线程就会立即执行初始化任务，对应核心线程创建，如果为空则会创建线程执行任务列表的任务，即非核心线程的创建
Worker是通过继承 AQS ，使⽤ AQS 来实现独占锁这个功能。没有使用可重入锁 ReentrantLock ，而是使用 AQS ，使用非可重入式锁的特性反映线程现在的执行状态

可重入性: 是指一个线程可以多次获取同一个锁。在Java的ReentrantLock中，就体现了这种可重入性。当一个线程已经持有锁时，它可以再次请求该锁而不会被阻塞，直到它释放锁为止。这种特性非常有用，因为它允许一个线程在执行过程中递归地调用需要相同锁保护的方法，而不会导致死锁
不可重入性：如果Worker类中的AQS实现不是可重入的，那么这意味着一旦一个线程获得了锁，它就不能再次获得该锁，直到它释放了锁。这与ReentrantLock的可重入性相反。在不可重入锁的情况下，如果线程尝试在已经持有锁的情况下再次获取锁，它将被阻塞或导致死锁（取决于具体的实现和锁的策略）。

线程池使用⼀张 Hash表 去持有线程的引用，这样可以通过添加引用、移除引用这样的操作来控制线程的生命周期。这个时候重要的就是如何判断线程 是否在运行，使用 AQS 获取不可重入锁，如果获取成功，即可进行线程回收操作

Worker线程的增加

增加Worker线程是通过 addWorker 方法，该方法只关心增加线程，不考虑哪个阶段增加的线程，该方法有两个参数：firstTask 、core
firstTask ：指定线程执行的第一个任务，可以为null
core : true:新增线程时会判断当前活动线程数是否少于corePoolSize，表示创建的是核心线程，false:新增线程时判断当前线程数是否少于maximumPoolSize，表示创建的是非核心线程

Worker线程销毁

线程池中线程的销毁依赖 JVM 自动的回收，线程池做的工作是根据当前线程池的状态维护一定数量的线程引用，防止这部分线程被 JVM 回收，当线程池决定哪些线程需要回收时，只需要将其引用消除即可。Worker 被创建出来后，就会不断地进行轮询，然后获取任务去执行，核心线程可以无限等待获取任务，非核心线程要限时获取任务。当Worker 无法获取到任务，也就是获取的任务为空时，循环会结束，Worker会主动消除自身在线程池内的引用。调用 processWorkerExit 方法执行销毁过程

Worker执行任务过程

5.业务实现

5.1创建自定义线程池

@Bean("threadPoolExecutor01") //指定线程池名称
public ThreadPoolExecutor threadPoolExecutor01(ThreadPoolConfigProperties properties) {
    RejectedExecutionHandler handler;
    switch (properties.getPolicy()){ //选择策略
        case "DiscardPolicy":
            handler = new ThreadPoolExecutor.DiscardPolicy();
            break;
        case "DiscardOldestPolicy":
            handler = new ThreadPoolExecutor.DiscardOldestPolicy();
            break;
        case "CallerRunsPolicy":
            handler = new ThreadPoolExecutor.CallerRunsPolicy();
            break;
        default:
            handler = new ThreadPoolExecutor.AbortPolicy();
            break;
    }

    // 创建线程池
    // 可以配置Properties参数并注入 
    // 记得添加@EnableConfigurationProperties(ThreadPoolConfigProperties.class)注解
    return new ThreadPoolExecutor(properties.getCorePoolSize(),//核心线程数
            properties.getMaxPoolSize(), //最大线程数
            properties.getKeepAliveTime(), //最长等待任务时间
            TimeUnit.SECONDS, //时间单位
            new LinkedBlockingQueue<>(properties.getBlockQueueSize()), //等待队列
            Executors.defaultThreadFactory(), //线程工厂
            handler); //处理策略
}

XxlJob🧾

📕本文基础介绍XxlJob是如何使用的
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://gitee.com/dsxriiiii/l3x

导入依赖

<dependency>
  <groupId>com.xuxueli</groupId>
  <artifactId>xxl-job-core</artifactId>
  <version>2.4.1</version>
</dependency>

设置配置信息

@Slf4j
@Configuration
public class XxlJobConfig {

    @Value("${xxl.job.admin.addresses}")
    private String adminAddresses;
    @Value("${xxl.job.accessToken}")
    private String accessToken;
    @Value("${xxl.job.executor.appname}")
    private String appname;
    @Value("${xxl.job.executor.address}")
    private String address;
    @Value("${xxl.job.executor.ip}")
    private String ip;
    @Value("${xxl.job.executor.port}")
    private int port;
    @Value("${xxl.job.executor.logpath}")
    private String logPath;
    @Value("${xxl.job.executor.logretentiondays}")
    private int logRetentionDays;

    @Bean
    public XxlJobSpringExecutor xxlJobExecutor() {
        log.info(">>>>>>>>>>> xxl-job config init.");
        XxlJobSpringExecutor xxlJobSpringExecutor = new XxlJobSpringExecutor();
        xxlJobSpringExecutor.setAdminAddresses(adminAddresses);
        xxlJobSpringExecutor.setAppname(appname);
        xxlJobSpringExecutor.setAddress(address);
        xxlJobSpringExecutor.setIp(ip);
        xxlJobSpringExecutor.setPort(port);
        xxlJobSpringExecutor.setAccessToken(accessToken);
        xxlJobSpringExecutor.setLogPath(logPath);
        xxlJobSpringExecutor.setLogRetentionDays(logRetentionDays);
        return xxlJobSpringExecutor;
    }
}

配置文件信息

Admin：
xxl.job.admin.addresses: 调度中心的地址，用于执行器通过该地址注册和反注册。
xxl.job.admin.contextPath: 调度中心的上下文路径。
xxl.job.admin.port: 调度中心的端口号。
xxl.job.accessToken: 执行器与调度中心之间通信的令牌，用于安全验证。
xxl.job.admin.database*: 数据库相关的配置，包括驱动类、URL、用户名和密码等。
Executor：
xxl.job.executor.appname: 执行器的应用名，用于区分不同的执行器实例。
xxl.job.executor.ip: 执行器的IP地址，用于调度中心定位执行器。
xxl.job.executor.port: 执行器的端口号，调度中心通过该端口与执行器通信。
xxl.job.executor.logpath: 执行器的日志文件存放路径。
xxl.job.executor.logretentiondays: 日志文件保留天数。
xxl.job.executor.accessToken: 与调度中心通信的令牌，需要与调度中心的 xxl.job.accessToken 一致。
xxl.job.executor.registry*: 如果使用注册中心（如Zookeeper），则需要配置注册中心的地址等信息。
xxl.job.executor.dispatch: 任务执行的线程池配置，如 xxl.job.executor.dispatchthread 表示调度线程数。

xxl:
  job:
    admin:
      addresses: http://127.0.0.1:7397/xxl-job-admin
    executor:
      address:
      appname: haper-job
      ip:
      port: 9998
      logpath: D:\software_log\Xxl_Job\data\applogs\xxl-job\jobhandler
      logretentiondays: 50
    accessToken: l***

//简单的任务调度
@Slf4j
@Component
public class SimpleXxlJob {
    private final AtomicInteger counts = new AtomicInteger();

    @XxlJob("demoJobHandler")
    public void demoJobHandler() throws Exception {
        XxlJobHelper.log("XXL-JOB, Hello World.");
        // 打印日志
        log.info("[execute][定时第 ({}) 次执行]", counts.incrementAndGet());
    }
}

访问配置中心地址修改配置信息

在Admin界面配置执行器，指定Appname 并且根据自动寻找到ip

设置调度任务

1. 在任务界面指定任务执行模式 一般情况指定Bean
2. 输入Bean的名称 设置执行时间corn 启动即可

如何实现活动限流、熔断

📕本文基于Sentinel、guava ratelimiter、Hystrix实现
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠源码地址：https://gitee.com/dsxriiiii/l3x

使用Guava下的rateLimit实现限流

@Slf4j
@Aspect
@Component
public class RateLimiterAOP {

    //使用自定义注解动态开关
    @DCCValue("rateLimiterSwitch:close")
    private String rateLimiterSwitch;

    // 个人限频记录1分钟，使用一个一分钟的缓存保存key和rateLimit
    private final Cache<String, RateLimiter> loginRecord = CacheBuilder.newBuilder()
            .expireAfterWrite(1, TimeUnit.MINUTES)
            .build();

    // 个人限频黑名单24h - 小黑屋
    private final Cache<String, Long> blacklist = CacheBuilder.newBuilder()
            .expireAfterWrite(24, TimeUnit.HOURS)
            .build();

    @Pointcut("@annotation(cn.dsxriiiii.Haper.types.annotations.RateLimiterAccessInterceptor)")
    public void aopPoint() {
    }

    @Around("aopPoint() && @annotation(rateLimiterAccessInterceptor)")
    public Object doRouter(ProceedingJoinPoint proceedingJoinPoint, RateLimiterAccessInterceptor rateLimiterAccessInterceptor) throws Throwable {
        //查看动态开关是否打开
        if (StringUtils.isBlank(rateLimiterSwitch) || "close".equals(rateLimiterSwitch)) {
            return proceedingJoinPoint.proceed();
        }
        String key = rateLimiterAccessInterceptor.key();
        if (StringUtils.isBlank(key)) {
            throw new RuntimeException("annotation RateLimiter uId is null！");
        }
        // 获取拦截字段 此处即是获取userId
        String keyAttr = getAttrValue(key, proceedingJoinPoint.getArgs());
        log.info("aop attr {}", keyAttr);

        // 黑名单拦截 如果黑名单中获取到了用户并且该用户id访问频次大于限定的黑名单界限 直接拦截
        if (!"all".equals(keyAttr) && rateLimiterAccessInterceptor.blacklistCount() != 0 && null != blacklist.getIfPresent(keyAttr) && blacklist.getIfPresent(keyAttr) > rateLimiterAccessInterceptor.blacklistCount()) {
            log.info("限流-黑名单拦截(24h)：{}", keyAttr);
            return fallbackMethodResult(proceedingJoinPoint, rateLimiterAccessInterceptor.fallbackMethod());
        }
        // 获取限流 -> Guava 缓存1分钟 该缓存用来做访问记录数
        RateLimiter rateLimiter = loginRecord.getIfPresent(keyAttr);
        //创建每秒可以处理{permitsPerSecond}个请求的RateLimiter
        if (null == rateLimiter) {
            //设置QPS 超过则拦截
            rateLimiter = RateLimiter.create(rateLimiterAccessInterceptor.permitsPerSecond());
            loginRecord.put(keyAttr, rateLimiter);
        }

        // 限流拦截 超过rateLimit则会请求失败
        // rateLimiter.tryAcquire 请求失败时返回false
        if (!rateLimiter.tryAcquire()) {
            if (rateLimiterAccessInterceptor.blacklistCount() != 0) {
                //黑名单限流次数处理
                if (null == blacklist.getIfPresent(keyAttr)) {
                    blacklist.put(keyAttr, 1L);
                } else {
                    blacklist.put(keyAttr, blacklist.getIfPresent(keyAttr) + 1L);
                }
            }
            log.info("限流-超频次拦截：{}", keyAttr);
            return fallbackMethodResult(proceedingJoinPoint, rateLimiterAccessInterceptor.fallbackMethod());
        }

        // 返回结果
        return proceedingJoinPoint.proceed();
    }

    /**
     * 调用用户配置的回调方法，当拦截后，返回回调结果。
     */
    private Object fallbackMethodResult(JoinPoint jp, String fallbackMethod) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        //获取签名
        Signature sig = jp.getSignature();
        MethodSignature methodSignature = (MethodSignature) sig;
        //通过反射获取方法
        Method method = jp.getTarget().getClass().getMethod(fallbackMethod, methodSignature.getParameterTypes());
        //调用方法
        return method.invoke(jp.getThis(), jp.getArgs());
    }

    /**
     * 获取通过某个值做拦截
     */
    public String getAttrValue(String attr, Object[] args) {
        if (args[0] instanceof String) {
            return args[0].toString();
        }
        String filedValue = null;
        for (Object arg : args) {
            try {
                if (StringUtils.isNotBlank(filedValue)) {
                    break;
                }
                // filedValue = BeanUtils.getProperty(arg, attr);
                // fix: 使用lombok时，uId这种字段的get方法与idea生成的get方法不同，会导致获取不到属性值，改成反射获取解决
                filedValue = String.valueOf(this.getValueByName(arg, attr));
            } catch (Exception e) {
                log.error("获取路由属性值失败 attr：{}", attr, e);
            }
        }
        return filedValue;
    }

    /**
     * 获取对象的特定属性值
     *
     * @param item 对象
     * @param name 属性名
     * @return 属性值
     * @author tang
     */
    private Object getValueByName(Object item, String name) {
        try {
            Field field = getFieldByName(item, name);
            if (field == null) {
                return null;
            }
            field.setAccessible(true);
            Object o = field.get(item);
            field.setAccessible(false);
            return o;
        } catch (IllegalAccessException e) {
            return null;
        }
    }

    /**
     * 根据名称获取方法，该方法同时兼顾继承类获取父类的属性
     *
     * @param item 对象
     * @param name 属性名
     * @return 该属性对应方法
     * @author tang
     */
    private Field getFieldByName(Object item, String name) {
        try {
            Field field;
            try {
                field = item.getClass().getDeclaredField(name);
            } catch (NoSuchFieldException e) {
                field = item.getClass().getSuperclass().getDeclaredField(name);
            }
            return field;
        } catch (NoSuchFieldException e) {
            return null;
        }
    }

}

使用Hystrix进行熔断操作

导入Maven坐标

<dependency>
  <groupId>com.netflix.hystrix</groupId>
  <artifactId>hystrix-javanica</artifactId>
  <version>1.5.18</version>
</dependency>

简单介绍

待拓展

项目使用

//添加接口
@HystrixCommand(commandProperties = {
           @HystrixProperty(name = "execution.isolation.thread.timeoutInMilliseconds", value = "150")
}, fallbackMethod = "drawHystrixError"
)
public String getUser() {
        return "user";
}

//添加熔断方法
public Response<ActivityDrawResponseDTO> drawHystrixError(@RequestBody ActivityDrawRequestDTO request) {
    //执行熔断具体操作
    log.info("Hystrix控制熔断 -->活动抽奖熔断 userId:{} activityId:{}", request.getUserId(), request.getActivityId());
    return Response.<ActivityDrawResponseDTO>builder()
            .code(ResponseCode.HYSTRIX.getCode())
            .info(ResponseCode.HYSTRIX.getInfo())
            .build();
}

使用Sentinel实现限流熔断

导入Maven坐标

建议使用：SpringBoot整合，该版本支持SpringBoot2.7.13，JDK8

<dependency>
    <groupId>com.alibaba.cloud</groupId>
    <artifactId>spring-cloud-starter-alibaba-sentinel</artifactId>
    <version>2.1.3.RELEASE</version>
</dependency>

也可以选择导入

<!-- sentinel服务 -->
<dependency>
  <groupId>com.alibaba.csp</groupId>
  <artifactId>sentinel-core</artifactId>
</dependency>

<!-- 支持注解 -->
<dependency>
  <groupId>com.alibaba.csp</groupId>
  <artifactId>sentinel-annotation-aspectj</artifactId>
  <version>1.8.6</version>
</dependency>

注入Bean

使用SentinelResource注解需要注入Bean添加Aop切面

@Configuration
public class SentinelAspectConfiguration {

    @Bean
    public SentinelResourceAspect sentinelResourceAspect() {
        return new SentinelResourceAspect();
    }
}

简单实现限流操作

@RestController
@RequestMapping("/user")
public class UserController {
    private final Logger log = LoggerFactory.getLogger(UserController.class);

    //getUserFallbackHandler用于处理BlockException异常发生时使用的方法
    //需要保证入参和返回类型一致，并且添加BlockException入参
    //@SentinelResource(value = "getUser",fallback = "helloFallback")
    @SentinelResource(value = "getUser",fallback = "helloFallback",blockHandler = "getUserFallbackHandler")
    @GetMapping
    public String getUser() {
        return "user";
    }

    public String getUserFallbackHandler(BlockException e) {
        log.error("您已被限流，调用失败了！",e);
        return "限流";
    }

    //如果不指定blockHandler 则会走fallback处理
    public String helloFallback(Throwable e) {
        log.error("熔断",e);
        return "熔断";
    }

    //限流操作 添加配置规则
    @PostConstruct
    public void init() {
        List<FlowRule> rules = new ArrayList<>();
        FlowRule rule = new FlowRule();
        rule.setResource("getUser");//资源名称
        rule.setGrade(RuleConstant.FLOW_GRADE_QPS);
        rule.setCount(1);//设置QPS
        rules.add(rule);
        FlowRuleManager.loadRules(rules);
    }
}

如何使用AOP切片原理记录接口日志

📕本文重点记录实现代码过程 通过切片可以将ip地址，请求出入参，接口响应时间等
🔧通过切片可以保存记录到数据库中并且通过延迟队列打入数据库防止数据库压力过大
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠项目地址：https://gitee.com/dsxriiiii/l3x

导入maven坐标

如果不导入包则无法引入注解

<dependency>
    <groupId>org.aspectj</groupId>
    <artifactId>aspectjweaver</artifactId>
    <version>1.9.21</version>
</dependency>

Application添加注解

@SpringBootApplication
@EnableAspectJAutoProxy//开启对Spring AOP（面向切面编程）的支持
public class Application {
    public static void main(String[] args) {
        SpringApplication.run(Application.class,args);
    }
}

定义注解

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface L3xLog {
}

在方法体上添加注解

这里只是简单实现了一个接口 在接口中添加自定义的注解

@RestController
@RequestMapping("/user")
public class LogController {
    private final Logger log = LoggerFactory.getLogger(LogController.class);

    @L3xLog
    @GetMapping
    public String getUser() {
        return "user";
    }
}

AOP切片定义

@Aspect
@Component
@Slf4j
public class AopLog {
    @Pointcut("@annotation(cn.dsxriiiii.L3x.annotation.L3xLog)")
    public void log(){}
    @Around("log() && @annotation(cn.dsxriiiii.L3x.annotation.L3xLog)")
    public Object aroundLog(ProceedingJoinPoint point) throws Throwable {
        //RequestContextHolder中获取当前的请求属性
        ServletRequestAttributes attributes = (ServletRequestAttributes) RequestContextHolder.getRequestAttributes();
        HttpServletRequest request = Objects.requireNonNull(attributes).getRequest();

        // 打印请求相关参数
        long startTime = System.currentTimeMillis();
        Object result = point.proceed();

        AppLog l = AppLog.builder()
                .ip(getIp(request))
                .url(request.getRequestURL().toString())
                .httpMethod(request.getMethod())
                .requestParams(getNameAndValue(point))
                .result(result)
                .timeCost(System.currentTimeMillis() - startTime)
                .build();

        log.info("Request Log Info : {}", JSON.toJSONString(l));
        return result;
    }

    /**
     * 将请求的参数与入参对应并且返回
     * @param joinPoint ProceedingJoinPoint
     * @return 结果Map
     */
    private Map<String, Object> getNameAndValue(ProceedingJoinPoint joinPoint) {
        // 获取JoinPoint对象的签名，它包含了方法的元数据信息
        final Signature signature = joinPoint.getSignature();
        // 将签名转换为MethodSignature类型，这是专门用于方法签名的类
        MethodSignature methodSignature = (MethodSignature) signature;
        // 获取方法参数的名称数组
        final String[] names = methodSignature.getParameterNames();
        // 获取方法参数的实际值数组
        final Object[] args = joinPoint.getArgs();

        // 检查参数名和参数值是否为空，如果为空则返回空Map
        if (ArrayUtil.isEmpty(names) || ArrayUtil.isEmpty(args)) {
            return Collections.emptyMap();
        }
        // 检查参数名和参数值的长度是否一致，如果不一致则记录警告并返回空Map
        if (names.length != args.length) {
            log.warn("{}方法参数名和参数值数量不一致", methodSignature.getName());
            return Collections.emptyMap();
        }
        // 创建一个HashMap来存储参数名和参数值的映射
        Map<String, Object> map = new HashMap<>();
        // 遍历参数名和参数值，将它们添加到Map中
        for (int i = 0; i < names.length; i++) {
            map.put(names[i], args[i]);
        }
        // 返回包含参数名和参数值映射的Map
        return map;
    }

    private static final String UNKNOWN = "unknown";

    /**
     * 从Http请求中获取ip信息
     * @param request 请求体
     * @return ip地址
     */
    public static String getIp(HttpServletRequest request) {
        // 尝试从HTTP头"x-forwarded-for"获取IP地址
        String ip = request.getHeader("x-forwarded-for");
        // 如果获取的IP为空或者为"unknown"，则尝试从"Proxy-Client-IP"获取
        if (ip == null || ip.isEmpty() || UNKNOWN.equalsIgnoreCase(ip)) {
            ip = request.getHeader("Proxy-Client-IP");
        }
        // 如果获取的IP为空或者为"unknown"，则尝试从"WL-Proxy-Client-IP"获取
        if (ip == null || ip.isEmpty() || UNKNOWN.equalsIgnoreCase(ip)) {
            ip = request.getHeader("WL-Proxy-Client-IP");
        }
        // 如果前面的尝试都失败了，则使用请求的远程地址作为IP
        if (ip == null || ip.isEmpty() || UNKNOWN.equalsIgnoreCase(ip)) {
            ip = request.getRemoteAddr();
        }
        // 定义逗号字符串
        String comma = ",";
        // 定义本地主机地址
        String localhost = "127.0.0.1";
        // 如果IP地址包含逗号，取逗号前的部分作为真实的IP地址
        if (ip.contains(comma)) {
            ip = ip.split(",")[0];
        }
        // 如果IP地址是本地地址，则尝试获取本机真正的IP地址
        if (localhost.equals(ip)) {
            try {
                ip = InetAddress.getLocalHost().getHostAddress();
            } catch (UnknownHostException e) {
                log.error(e.getMessage(), e);
            }
        }
        // 返回最终获取的IP地址
        return ip;
    }

}

AOP出参处理

待更新

SpringCloud-GateWay网关

😋GateWay网关作者本人目前还在测试，更多功能开发更新中……
❗该文章内容基于作者本人思考总结，如有错误欢迎指正

简单使用

创建service服务和gateway网关两个服务
service服务端口为6541
gateway网关为9000

导入依赖

<dependencies>
  <dependency>
    <groupId>org.springframework.cloud</groupId>
    <artifactId>spring-cloud-starter-gateway</artifactId>
    <version>3.1.6</version>
  </dependency>
</dependencies>

❗web和gateway不能放在一起

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>
</dependencies>

定义一个简单的接口

@RestController
@RequestMapping("/user")
public class Controller {
    @RequestMapping("/name")
    public String getName(){
        return "华硕我求你别蓝屏了";
    }
}

网关配置文件

server:
  port: 9000 # 指定网关服务的端口
spring:
  application:
    name: api-gateway
  cloud:
    gateway:
      routes: # 路由数组[路由 就是指定当请求满足什么条件的时候转到哪个微服务]
        - id: product_route # 当前路由的标识, 要求唯一
          uri: http://127.0.0.1:6541 # 请求要转发到的地址
          order: 1 # 路由的优先级,数字越小级别越高
          predicates: # 断言(就是路由转发要满足的条件)
            - Path=/gateway/user/** # 当请求路径满足Path指定的规则时,才进行路由转发
          filters: # 过滤器,请求在传递过程中可以通过过滤器对其进行一定的修改
            - StripPrefix=1 # 转发之前去掉1层路径
      enabled: true

访问网关

直接访问接口

发现结果是相同的

面试150题-动态规划

📕文章题目选自LeetCode面试150题-动态规划
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/

动态规划

LeetCode150-爬楼梯-LC70

该节点爬楼梯的选择取决于前面的两个节点
public class LC70 {
    public static void main(String[] args) {
        int n = 4;
        System.out.println(climbStairs(n));
    }
    public static int climbStairs(int n) {
        if(n < 3) return n;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i < n;i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}

LeetCode150-零钱兑换-LC322

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/15 9:28
 * @Email: lihh53453@hundsun.com
 * @Description: 零钱兑换
 * dp数组的长度为金额+1 dp[0]时金额为零时初始化为0
 * 初始化每个数组的值为amount+1
 * 遍历每一个硬币 对于每一个金额i
 * dp[i]=Math.min(dp[i],dp[i-coin]+1)
 */
public class LC322 {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        int max = amount + 1;
        Arrays.fill(dp,max);
        for (int i = 1; i <= amount ; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

LeetCode150-最长递增子序列-LC300

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/15 10:00
 * @Email: lihh53453@hundsun.com
 * @Description: 最长递增子序列
 * 1.遍历i的位置 循环访问[j,i)区间 
 * 2.如果dp[i]>dp[j] 说明此时满足严格递增区间
 * 递增序列：dp[i] = Math.max(dp[i],dp[j]+1);
 * maxans用来保存最大的数
 */
public class LC300 {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

LeetCode150-三角形最小路径和-LC120

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/15 10:30
 * @Email: lihh53453@hundsun.com
 * @Description: 三角形最小路径和
 * 自底向上动态规划 对于(i,j)位置来说 取(i+1,j+1)和(i+1,j) 斜对角和同列
 */
public class LC120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n+1][n+1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                dp[i][j] = Math.min(dp[i+1][j+1],dp[i+1][j])+triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

LeetCode150-最小路径和-LC64

/**
 * @PackageName: cn.dsxriiiii.LeetCode.LC150
 * @Author: DSXRIIIII
 * @Email: 1870066109@qq.com
 * @Date: Created in  2024/08/17 9:50
 * @Description: 最小路径和
 * 此题可以考虑自上而下进行遍历 因为每一个节点都可以走到
 * 循环向下动态递增即可
 **/
public class LC64 {
    public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i == 0 && j == 0) {
                    continue;
                } else if(i == 0) {
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                } else if(j == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                }else{
                    grid[i][j] = Math.min(grid[i][j - 1],grid[i - 1][j]) + grid[i][j];
                }
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

LeetCode150-最小路径和II-LC63

/**
 * @PackageName: cn.dsxriiiii.LeetCode.LC150
 * @Author: DSXRIIIII
 * @Email: 1870066109@qq.com
 * @Date: Created in  2024/08/17 10:17
 * @Description: 最小路径和II
 * 空间优化：
 * dp[j] = dp[j] + dp[j - 1];
 * dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
 * 因为一维dp已经保存了上一行处理的节点
 * 当前节点取决于行前一个以及行上一个 将空间优化成一维
 **/
public class LC63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid[0].length;
        int[] dp = new int[m];
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (int[] ints : obstacleGrid) {
            for (int j = 0; j < m; j++) {
                if (ints[j] == 1) {
                    dp[j] = 0;
                } else if (ints[j] == 0 && j - 1 >= 0) {
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }
        return dp[m - 1];
    }
}

LeetCode150-最长回文字串-LC5

/**
 * @PackageName: cn.dsxriiiii.LeetCode.LC150
 * @Author: DSXRIIIII
 * @Email: 1870066109@qq.com
 * @Date: Created in  2024/08/17 10:40
 * @Description: 最长回文字串
 * 判断回文串如果长度为1 那么此时为回文串
 * 长度i与j的位置差 == 1  相等即为回文串.两个字符是否相等
 * 长度位置差大于>1 此时字符相等  取决于上一个位置的两个字符是否相等
 **/
public class LC5 {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
        String res = "";
        int maxLength = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            for(int j = i; j < n;j++){
                if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])){
                    dp[i][j] = true;
                    maxLength = Math.max(j - i,maxLength);
//                    if(maxLength < j - i){
//                        res = s.substring(i,j+1);
//                    } 如果这里不相等就不会有结果
                    if(maxLength <= j - i){
                        res = s.substring(i,j+1);
                    }
                }
            }
        }
        return res;
    }
}

LeetCode150-交错字符串-LC97

/**
 * @PackageName: cn.dsxriiiii.LeetCode.LC150
 * @Author: DSXRIIIII
 * @Email: 1870066109@qq.com
 * @Date: Created in  2024/08/17 11:24
 * @Description: 交错字符串
 * 对于s3的字符串位置x=i + j - 1 取决于和字符串s1的 i - 1位置 或者 s2的j - 1位置是否相等
 * 并且继承前一位 dp[i - 1][0] 或者 dp[0][j - 1] 
 * 情况1.s1 所有在字符与 s3 相等 所以就是一维的dp数组
 * 情况2.s2 所有在字符与 s3 相等 所以就是一维的dp数组
 * 情况3.s1 起始位置不在0位置开始 取决与前一位boolean值 和 s1的下一位或者 s2 的下一位
 **/
public class LC97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
        if(l1  + l2 != l3) {
            return false;
        }
        boolean[][] dp =  new boolean[l1 + 1][l2 + 1];
        //初始化dp数组
        dp[0][0] = true;
        for (int i = 1; i < l1; i++) {
            //比较前一位的位置
            //dp[i][0] = dp[i - 1][0] && s1.charAt(i) == s3.charAt(i);
            dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
        }
        for (int j = 1; j < l2; j++) {
            //dp[0][j] = dp[0][j - 1] && s1.charAt(j) == s3.charAt(j);
            dp[0][j] = dp[0][j - 1] && s1.charAt(j - 1) == s3.charAt(j - 1);
        }
        for (int i = 1; i < l1 ; i++) {
            for (int j = 1; j < l2; j++) {
                boolean resI = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                boolean resJ = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                dp[i][j] = resJ || resI;
            }
        }
        return dp[l1][l2];
    }
}

LeetCode150-买卖股票的最佳时机III-LC123

package cn.dsxriiiii.LeetCode;

/**
 * @PackageName: cn.dsxriiiii.LeetCode
 * @Author: DSXRIIIII
 * @Email: 1870066109@qq.com
 * @Date: Created in  2024/08/19 9:35
 * @Description: 买卖股票的最佳时机III
 * 确定好四个状态
 * 
 **/
public class LC123 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        //第一天买入
        int buy1 = -prices[0];
        //第一天买入且买出
        int sell1 = 0;
        //第一天全部卖出且买入新的
        int buy2 = -prices[0];
        //第一天全部卖出且全部卖出
        int sell2 = 0;
        for (int i = 1; i < n; i++) {
            //只进行过一次买操作
            buy1 = Math.max(buy1,-prices[i]);
            //买操作之后卖出
            sell1 = Math.max(sell1,buy1 + prices[i]);
            //第一次买卖交易后买入
            buy2 = Math.max(buy2,sell1 - prices[i]);
            //第一次买卖交易后卖出
            sell2 = Math.max(sell2,buy2 + prices[i]);
        }
        return sell2;
    }
}

LeetCode10-买卖股票的最佳时机IV-LC188

/**
 * @PackageName: cn.dsxriiiii.LeetCode.LC150
 * @Author: DSXRIIIII
 * @Email: 1870066109@qq.com
 * @Date: Created in  2024/08/19 10:28
 * @Description: 买卖股票的最佳时机IV
 * 分析得出五个状态
 * 没有操作 （其实我们也可以不设置这个状态）
 * 第一次持有股票 dp[i][0 + 1] = Math.max(dp[i - 1][0 + 1],dp[i - 1][0] - prices[i]);   j = 0 = 0 * k -> 0 * k + 1  【0】
 * 第一次不持有股票 dp[i][0 + 2] = Math.max(dp[i - 1][0 + 2],dp[i - 1][0 + 1] + prices[i]); j = 0 = 0 * k  -> 0 * k + 2  【1】
 * 第二次持有股票 dp[i][0 + 3] = Math.max(dp[i - 1][0 + 3],dp[i - 1][0 + 2] - prices[i]);  j = 1 = 1 * k -> 1 * k + 1  【2】
 * 第二次不持有股票 dp[i][0 + 4] = Math.max(dp[i - 1][0 + 4],dp[i - 1][0 + 3] - prices[i]);  j = 1 = 1 * k -> 1 * k + 2  【3】
 * ....类推得到递推公式
 **/
public class LC188 {
    public int maxProfit(int k, int[] prices) {
        int l = prices.length;
        int[][] dp = new int[l][2*k+2];
        for (int i = 1; i < 2 * k; i+=2) {
            dp[0][i] = -prices[0];
        }
        for (int i = 1; i < l; i++) {
            for (int j = 0; j < 2 * k - 1 ; j+=2) {
//                //dp[i][j] = dp[i - 1][j];  对应1
//                dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[j]);   //对应 情况1 情况3
//                dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[j]);  //对应  情况2  情况4

                //dp[i][j] = dp[i - 1][j];  对应1
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]);   //对应 情况1 情况3
                dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]);  //对应  情况2  情况4
            }
        }
//        return dp[l - 1][2 * k + 1];
        return dp[l - 1][2 * k];
    }
}

LeetCode10-最大正方形-LC221

/**
 * @PackageName: cn.dsxriiiii.LeetCode.LC150
 * @Author: DSXRIIIII
 * @Email: 1870066109@qq.com
 * @Date: Created in  2024/08/19 11:27
 * @Description: 最大正方形
 * 简单递推 
 * 1.边界为0时如果为1就初始化为1
 * 2.不为0时找到左上 左 上 三个位置 找到最小值+1
 * 3.比较的到最大的边长
 **/
public class LC221_2 {
    public int maximalSquare(char[][] matrix) {
        int res = 0;
        int max_len = 0;
        if(matrix.length == 0 || matrix[0].length == 0){
            return res;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(matrix[i][j] == 1){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1])+1;
                    }
                    max_len = Math.max(max_len,dp[i][j]);
                }
            }
        }
        return max_len*max_len;
    }
}

面试150题-二分查找、位运算、数学

📕文章题目选自LeetCode面试150题-二分查找+位运算+数学部分
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/

二分查找

LeetCode150-搜索插入位置-LC35

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 15:09
 * @Email: lihh53453@hundsun.com
 * @Description: 搜索插入位置
 */
public class LC35 {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(target == nums[mid]){
                return mid;
            }
            if(target < nums[mid]) right = mid - 1;
            if(target > nums[mid]) left = mid + 1;
        }
        return left;
    }
}

LeetCode150-搜索二维矩阵-LC74

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 15:32
 * @Email: lihh53453@hundsun.com
 * @Description: 搜索二维矩阵
 * 二分查找
 * 将二位数组转化为一维
 * 坐标位置就是matrix[mid/matrix[0].length][mid%matrix[0].length]
 * 注意区分行列
 */
public class LC74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0;
        //int right = matrix.length * matrix[0].length;
        int right = matrix.length * matrix[0].length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            //int value = matrix[mid/matrix.length][mid%matrix.length];
            int value = matrix[mid/matrix[0].length][mid%matrix[0].length];
            if(target < value){
                right = mid - 1;
            }else if(target > value){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;
    }
}

LeetCode150-寻找峰值-LC162

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 16:15
 * @Email: lihh53453@hundsun.com
 * @Description: 寻找峰值
 * 1.直接找最大值 最大值就是峰值
 * 2.时间复杂度为log(n) 使用二分查找
 * 判断如果mid此时位于下坡路 那么此时可能找不到峰值
 * 如果mid走上坡路 那么一定有峰值 
 */
public class LC162 {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid + 1] < nums[mid]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

LeetCode150-搜索旋转排序数组-LC33

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 17:04
 * @Email: lihh53453@hundsun.com
 * @Description: 搜索旋转排序数组
 * 二分查找
 * 左节点从0开始 右节点到n-1结束
 * 找到严格递增区间 nums[0] <= nums[mid]
 * 1.true:说明左区间为严格递增区间 3 4 5 6 7 1 2
 *      1.1.target在[0,mid]之间 right = mid - 1 缩小到左递增区间
 *      1.2 target在该区间内 left = mid + 1;
 * 2.false:说明右区间为严格递增区间 6 7 1 2 3 4 5
 *      2.1.target在[mid,n - 1]之间 left = mid + 1 缩小到右递增区间
 *      2.2 target在不该区间内 right = mid - 1;
 */
public class LC33 {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            //选择一个有序数组进行处理
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.length - 1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

LeetCode150-在排序数组中查找元素的第一个和最后一个位置-LC34

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 17:47
 * @Email: lihh53453@hundsun.com
 * @Description: 在排序数组中查找元素的第一个和最后一个位置
 * 最后一个位置：满足条件nums[mid] <= target left = mid + 1 此时走到target后一位 所以rightIndex要-1
 * 元素的第一个位置：满足条件nums[mid] >= target right = mid - 1 此时会向左走 直到走到边界
 */
public class LC34 {
    public int[] searchRange(int[] nums, int target) {
        int leftIndex = bin_search(nums,target,true);
        int rightIndex = bin_search(nums,target,false) - 1;
        if(leftIndex < rightIndex && rightIndex < nums.length && nums[leftIndex] == target && nums[target] == target){
            return new int[]{leftIndex,rightIndex};
        }
        return new int[]{-1,-1};
    }

    private int bin_search(int[] nums, int target, boolean flag) {
        int left = 0;
        int right = nums.length - 1;
        int ans = -1;
        while(left <= right){
            int mid = left + (left - right) / 2;
            if(nums[mid] > target || (flag&&(nums[mid] >= target))){
                right = mid - 1;
                ans = mid;
            }else {
                //nums[mid] <= target 走到target满足条件 此时步数+1 走到target后一位
                left = mid + 1;
            }
        }
        return ans;
    }
}

LeetCode150-寻找旋转排序数组中的最小值-LC153

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 9:43
 * @Email: lihh53453@hundsun.com
 * @Description: 寻找旋转排序数组中的最小值
 * 将中间值与最后一个元素比较
 * 1.nums[mid] < nums[nums.length - 1] 说明中间值在第二段数组 并且最小值在mid的左边
 * 2，nums[mid] >= nums[nums.length - 1] 说明中间值在第一段数组 最小值在第二段数组 更新left = mid + 1;
 * 3.right初始化为 nums.length - 2 因为不断要和nums[n-1]比较 假如nums[n-1]为最小值 left=mid+1 也会走到target
 */
public class LC153 {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 2;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[nums.length - 1]){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

（待解决）LeetCode150-寻找两个正序数组的中位数-LC4

二分查找总结

1. 搜索插入位置：常规二分
2. 搜索二维矩阵：坐标位置转换 nums[i/col][i%col]+常规二分
3. 寻找峰值：判断当前是否是下坡路 nums[mid + 1] < nums[mid] 下坡路没有峰值 更新left和right
4. 搜索旋转排序数组：找到严格递增数列 并且更新left和right的坐标位置 二分
5. 在排序数组中查找元素的第一个和最后一个位置：找到第一个target的位置 和 最后一个target的后一个位置 条件即为nums[mid] >= target 或者 nums[mid] > target
6. 寻找旋转排序数组中的最小值：二分条件nums[mid] < nums[nums.length - 1] 区间从[0,n-2] 因为要不断与n-1进行比较 mid的位置也会不断改变 当相等时left也会递增到最后一位

位运算

LeetCode150-二进制求和-LC190

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 15:22
 * @Email: lihh53453@hundsun.com
 * @Description: 二进制求和
 * 逢2进一 保存进位值
 */
public class LC67 {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int temp = 0;
        for(int i = a.length() - 1,j = b.length() - 1;i >=0 || j >=0;i--,j--){
            int sum = temp;
            sum+= i >= 0 ? a.charAt(i) - '0' : 0;
            sum+= j >= 0 ? b.charAt(j) - '0' : 0;
            sb.append(sum%2);
            temp = sum / 2;
        }
        sb.append(temp == 1 ? "1":"");
        return sb.reverse().toString();
    }
}

LeetCode150-颠倒二进制位-LC190

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 13:25
 * @Email: lihh53453@hundsun.com
 * @Description:
 * (x >> k) & 1 获取第k位数字
 * (x << 1) | 1/0 将数字1/0添加到数字末尾
 */
public class LC190 {
    public int reverseBits(int n) {
        int temp = 0;
        for (int i = 0; i < 32; i++) {
            //1.(n & 1)取n的最后一位
            //2.x<<(n) 将x左移n位
            //3.temp = (n & 1) << (31 - i) | temp 将最后一位左移的结果添加到temp的末尾 或运算
            temp |= (n & 1) << (31 - i);
            //逻辑右移 去除最后一位
            n>>>=1;
        }
        return temp;
    }
}

LeetCode150-位1的个数-LC191

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 14:09
 * @Email: lihh53453@hundsun.com
 * @Description: 位1的个数
 * (1<<i) i左移i位
 * (n & (1<<i)) n的第(1<<i)位 1/0
 * n & (n−1) 将最低为1 变为 0
 * 当n不为0时 不断将1变成0
 * 
 */
public class LC191 {
    public int hammingWeight(int n) {
        int res = 0;
        for (int i = 0; i < 31; i++) {
            if((n & (1<<i)) != 0) res++;
        }
        return res;
    }
    public int hammingWeight_1(int n) {
        int res = 0;
        while(n != 0){
            n &= (n - 1);
            res++;
        }
        return res;
    }
}

LeetCode150-只出现过一次的数字-LC136

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 14:23
 * @Email: lihh53453@hundsun.com
 * @Description: 只出现过一次的数字
 * 异或 a⊕0=a 异或0为0 异或自己为0
 * 异或的运算规则为 a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b⊕0 = b
 */
public class LC136 {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int num:nums){
            res ^= num;
        }
        return res;
    }
}

LeetCode150-只出现过一次的数字II-LC137

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 14:40
 * @Email: lihh53453@hundsun.com
 * @Description: 只出现一次的数字 II
 * 和只出现一次的数字一样 但是有一个数学的推导
 * 异或的本质是做了比特位上做了模2的加法
 * 所以此题采用比特位上做模3的加法
 * 每一位数字mod三之后拼接即为只出现一次的数字
 */
public class LC137 {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i = 0;i < 32;i++){
            int temp = 0;
            for(int num:nums){
                temp += (num>>i) & 1;
                //(num>>i) & 1 取出第i位数字 temp保存
            }
            ans |= temp % 3 << i;
            //temp % 3 取模 并且左移
            //左移结果 通过|=相加保存
            //001 | 110 -> 111
        }
        return ans;
    }
}

LeetCode150-数字范围按位取-LC201

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 15:07
 * @Email: lihh53453@hundsun.com
 * @Description: 
 * 1.从区间left到right的闭区间 每一个元素进行与运算
 * 对于每一位 例如 数字范围按位与
 * 9   1 0 0 1
 * 10  1 0 1 0
 * 11  1 0 1 1
 * 12  1 1 0 0
 * 这四个数进行&运算 一旦遇到0就一定是0
 * 所以要找到这个区间的公共前缀 公共前缀对应的树即为要找的数
 * 当 left >= right时 此时右区间的数已经比left小了 此时就代表找到了最小的公共前缀
 * 利用 n&(n-1) 不断取出最后位的1
 */
public class LC201 {
    public int rangeBitwiseAnd(int left, int right) {
        while(left < right){
            right &= right - 1;
        }
        return right;
    }
}

位运算总结

(n - 1) & 1 取最后一位
n << i   n左移i位补0
n >> i   n右移i位左边补0
n >>> 1  逻辑右移 不会添加0或1
(n - 1) & n 不断删除最后一位的1

二进制求和：遍历取得最后一位的字符 遇2进1 余数添加 进位保存
颠倒二进制位：temp |= (c) << (31 - i); n>>>=1; (n & 1)取n的最后一位 并且左移取最后一位 右移 去除最后一位 最后或运算合并数字
位1的个数：(n -1)&n 可以不断去除最后一位的1
只出现过一次的个数I：异或运算(^) a^0 = a -> a^a = 0
只出现过一次的个数II：异或的逻辑就是模2 将每一位取出来temp += (num>>i) & 1 最后将(temp%3)<<(位数) | res 合并 即ans |= temp % 3 << i;
数字范围按位取：找前缀 [n,m] 当n <= m时(n -1)&n 可以不断去除最后一位的1 找到前缀和

数学

LeetCode150-回文数-LC9

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 16:28
 * @Email: lihh53453@hundsun.com
 * @Description: 回文数
 * 1.字符串反转比较即可
 * 2.while(x > reverseNum)将数从最后一位不断的添加 如12321 最后比较即为 12 与 123 比较 此时是奇数情况
 *                                            如1221 最后比较即为 12 与 12 比较 此时是偶数情况
 * 3.最后比较两个值是否相等
 * 4.注意是否是10的倍数 同样地，如果数字的最后一位是 0，为了使该数字为回文，则其第一位数字也应该是 0 只有0满足这个条件
 */
public class LC9 {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        int reverseNum = 0;
        while(x > reverseNum){
            reverseNum = reverseNum * 10 + x % 10;
            x/=10;
        }
        return x == reverseNum || x == reverseNum / 10;
    }
}

LeetCode150-加一-LC66

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 16:47
 * @Email: lihh53453@hundsun.com
 * @Description: 加一
 * 如果没有满足进位的条件 digit[i]++ 后直接返回即可
 * 如果有进位 989 在第二次循环时 会以 990的情况返回
 * 如果 999 全部都进位了 创建新数组 第一位为1 其余位未被初始化都是0 直接返回即可
 */
public class LC66 {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0 ; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if(digits[i] != 0) return digits;
        }
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}

LeetCode150-阶乘后的零-LC172

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/13 17:00
 * @Email: lihh53453@hundsun.com
 * @Description: 阶乘后的零
 * 即找五的个数 10就是2 * 5 但是在阶乘中5的数量少于2 多少个0就取决于多少个5
 * 1 * 2 * 3 * 4 * 5 * 7 * 8 * 9 * 10
 * 5的倍数个数为2 -> 10/5=2
 * 对于阶乘 100 
 * 5的倍数个数为  -> 100/5=20
 * 5 * 5 的倍数个数为 100/5*5=44 25 50 75 100 四个 以此类推
 */
public class LC172 {
    public int trailingZeroes(int n) {
        int ans = 0;
        while(n != 0){
            n /= 5;
            ans += n;
        }
        return ans;
    }
}

LeetCode150-x 的平方根-LC69

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/14 9:26
 * @Email: lihh53453@hundsun.com
 * @Description: x 的平方根
 * 二分法
 */
public class LC69 {
    public int mySqrt(int x) {
        if(x == 1) return 1;
        if(x == 0) return 0;
        int left = 1;
        int right = x / 2;
        while(left <= right){
            int mid = left + (right - left + 1)/2;
            if(mid > x / mid){
                right = mid - 1;
            }else if(mid == x / mid){
                return mid;
            }else{
                left = left + 1;
            }
        }
        return left + 1;
    }
}

LeetCode150-Pow(x, n)-LC50

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/14 9:47
 * @Email: lihh53453@hundsun.com
 * @Description: Pow(x, n)
 * 递归求平方
 * 1. 正数quickPow(x,N) 负数 1/quickPow(x,-N)
 * 2. 递归 如X**2 = X*X  X**3 = X**X**X 
 */
public class LC50 {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickPow(x,N) : 1 / quickPow(x,-N);
    }
    public double quickPow(double x,Long N){
        if(N == 0) return 1.0;
        double y = quickPow(x,N / 2);
        return N % 2 == 0 ?  y * y : y * y * x;
    }
}

面试150题-分治(归并排序)、Kadane

📕文章题目选自LeetCode面试150题-分治+Kadane
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/

分治(归并排序)

LeetCode150-将有序数组转换为二叉搜索树-LC108

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/11 17:55
 * @Email: lihh53453@hundsun.com
 * @Description: 将有序数组转换为二叉搜索树
 * 分治算法->归并排序
 */
public class LC108 {
    public TreeNode sortedArrayToBST(int[] nums) {
//        return dfs(nums,0,nums.length);
        return dfs(nums,0,nums.length - 1);//注意边界位置
    }

    private TreeNode dfs(int[] nums, int left, int right) {
        if(left > right){
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums,left,mid - 1);
        root.right = dfs(nums,mid + 1,right);
        return root;
    }
}

LeetCode150-排序链表-LC148

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/11 18:05
 * @Email: lihh53453@hundsun.com
 * @Description: 排序链表
 * 分治算法(归并排序) 时间复杂度(nlog(n))
 * 1.拆解链表 使用快慢指针拆解链表 左链表头节点head 右链表头节点fast
 * 2.将链表排序 使用虚拟头节点指向min节点然后遍历 更新左右节点和当前节点
 */
public class LC148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head; //确保头节点不为null
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //fast走到尾节点 slow走到中间节点
        fast = slow.next; //fast指向right链表的头节点
        slow.next = null; //断开左右链表
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        ListNode left = sortList(head);
        ListNode right = sortList(fast);
        while(left != null && right != null){
            if(left.val <= right.val){
                cur.next = left;
                left = left.next;
            }else{
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;//cur的位置也需要改变
        }
        cur.next = left != null ? left : right;
        return dummy.next;
    }
}

LeetCode150-构建四叉树-LC427

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 9:14
 * @Email: lihh53453@hundsun.com
 * @Description: 构建四叉树
 * 思路：分治(归并) + dfs
 * 记录(r0,c0) 到 (r1,c1)的判断是否为四叉树 两层循环遍历 boolean值记录
 * 如果为四叉树的叶子节点直接返回Node(true,true)
 * 否则则会继续dfs遍历 将四个叶子节点进行判断封装
 * dfs的起点(r0,c0)和(r1,c1) 即为左上角和右上角的坐标位置
 */
public class LC427 {
    public FourTreeNode construct(int[][] grid) {
        return dfs(grid,0,0,grid.length,grid.length);
    }

    private FourTreeNode dfs(int[][] grid, int r0, int c0, int r1, int c1) {
        boolean same = true;
        for (int i = r0; i < r1; i++) {
            for (int j = c0; j < c1; j++) {
                if (grid[i][j] != grid[r0][c0]) {
                    same = false;
                    break;
                }
            }
            if(!same) break;
        }
        if(same) return new FourTreeNode(grid[r0][c0] == 1, true);
        return new FourTreeNode(
                true,
                false,
                dfs(grid,r0,c0,(r0 + r1)/2,(c0 + c1)/2),
                dfs(grid,r0,(c0 + c1)/2,(r0 + r1)/2,c1),
                dfs(grid,(r0 + r1)/2,c0,r1,(c0 + c1)/2),
                dfs(grid,(r0 + r1)/2,(c0 + c1)/2,r1,c1)
        );
    }
}

LeetCode150-合并k个升序链表-LC23

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 9:43
 * @Email: lihh53453@hundsun.com
 * @Description: 合并k个升序链表
 * 分治 + 合并两个链表
 * 注意分治区间为[left,mid] 和 [mid+1,right] 否则会死循环
 * 分治逻辑 拆分两个链表 
 * 1.坐标相同返回nodes[left]
 * 2.坐标left>right越界 返回null
 * 3.拿到两个链表 进行排序
 */
public class LC23 {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if(left == right){
            return lists[left];
        }
        if(left > right) return null;
        int mid = (left + right) / 2;
        System.out.println("区间为：["+left+","+right+"]");
        //[1,2] (1+2)/2 = 1 下次一次区间还是[1,2] 死循环 栈溢出
        return mergeList(merge(lists,left,mid),merge(lists,mid+1,right));
        //return mergeList(merge(lists,left,mid-1),merge(lists,mid,right));
    }

    private ListNode mergeList(ListNode left, ListNode right) {
        if(left == null || right == null){
            return left == null ? right : left;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy,temp_left = left,temp_right = right;
        while(temp_left != null && temp_right != null){
            if(temp_left.val <= temp_right.val){
                cur.next = temp_left;
                temp_left = temp_left.next;
            }else{
                cur.next = temp_right;
                temp_right = temp_right.next;
            }
            cur = cur.next;
        }
        cur.next = temp_left == null ? temp_right:temp_left;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode[] nodes = new ListNode[]{
                new ListNode(1, new ListNode(4, new ListNode(5))),
                new ListNode(1, new ListNode(3, new ListNode(4))),
                new ListNode(2, new ListNode(6))
        };
        LC23 lc23 = new LC23();
        lc23.mergeKLists(nodes);
    }
}

分治算法总结

1. 将有序数组转化为二叉搜索树：找到mid节点 左树为dfs(left,mid-1),右树为dfs(mid+1,right)

2. 排序链表：拆分链表 拿到left=sortList(head) right=sortList(fast) 在合并两个链表

3. 四叉树：从(0,0)到(r1,r1) 分治成四个区间
   dfs(grid,r0,c0,(r0 + r1)/2,(c0 + c1)/2),

           dfs(grid,r0,(c0 + c1)/2,(r0 + r1)/2,c1),
           dfs(grid,(r0 + r1)/2,c0,r1,(c0 + c1)/2),
           dfs(grid,(r0 + r1)/2,(c0 + c1)/2,r1,c1)

4. 合并k个升序链表：for循环遍历链表 -> 分治 拆分成mergeList(merge(lists,left,mid),merge(lists,mid+1,right));

Kadane 算法

LeetCode150-最大子数组和-LC53

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 13:17
 * @Email: lihh53453@hundsun.com
 * @Description: 最大子数组和
 */
public class LC53 {
    public int maxSubArray(int[] nums) {
        int max_value = nums[0];
        int current_sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            current_sum = Math.max(current_sum,current_sum + nums[i - 1]);
            max_value = Math.max(current_sum,max_value);
        }
        return max_value;
    }
}

LeetCode150-环形子数组的最大和-LC918

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/12 14:27
 * @Email: lihh53453@hundsun.com
 * @Description: 环形子数组的最大和
 * 考虑到数组是环形的 从最开头的几个节点和尾节点也可能创造最大的res
 * 1.先记录从前往后遍历的最大和res 即最大的子序列和
 * 2.记录左遍历的对于每一个节点的最大的前缀和
 * 3.从右向左遍历 记录右边开始的后缀和 res=Math.max(res,后缀和right_sum+最大前缀和)
 */
public class LC918 {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        leftMax[0] = nums[0];
        int pre = nums[0];
        int res = nums[0];
        int left_sum = nums[0];
        for (int i = 1; i < n ; i++) {
            pre = Math.max(pre+nums[i],nums[i]);
            res = Math.max(pre,res);//记录前缀和 保存最大的子序列的和
            left_sum+=nums[i];
            leftMax[i] = Math.max(leftMax[i - 1],left_sum);//记录前缀最大值
        }
        int right_sum = 0;
        for (int i = n - 1; i > 0; i--) {
            right_sum += nums[i];
            //从后往前遍历 前缀最大值+右边和与最大的子序列的和比较的到最大和
            res = Math.max(leftMax[i - 1] + right_sum,res);
        }
        return res;
    }
}