Segment Tree 线段树

线段树解决的是「区间和」的问题，且该「区间」会被修改

一个区间的例子是对于 nums = [1, 2, 3, 4, 5] 多次求某些区间的和，是不是首先想到了利用「前缀和」。

但是如果 nums 会被修改呢？比如：

• 把第 i 个元素修改成 x
• 把第 i 个元素增加 x
• 把区间 [i, j] 内的元素都增加 x

此时，如果我们再使用「前缀和」，就没那么高效了。因为每一次更新，前缀和数组必须也随之更新，时间复杂度为 O(n)。

Redis Type Implementation 数据类型实现

String类型

Redis使用C自行实现了一个简单动态字符串（SDS）作为String类型的底层实现。其源码可以见这。

线程安全如何实现

线程安全问题的产生本质上是因为多个线程在并发条件下对同一个共享资源的争抢，因此有两种方向来保证线程安全：

1. 限制线程对资源的并发访问：这个方向的主要方式是加锁（阻塞），volatile（非阻塞）。
2. 将该资源设置为线程独占的：这个方向主要实现方式是TreadLocal。

Java 多线程入门

• 进程，是对运行时程序的封装，是系统进行资源调度和分配的基本单位，实现了操作系统的并发。
• 线程，是进程的子任务，是 CPU 调度和分派的基本单位，实现了进程内部的并发。

Java锁简介

实战：多线程打印ABC

主要方向有两种：一是自旋，二是阻塞（加锁或信号量）

1. 使用volatile关键字进行自旋

三个方法各自死循环，直到计数器对 3 取余是相应的数字。为了避免浪费资源，在自旋失败时让出 CPU 时间

public class PrintABC {
    private volatile int counter = 0;

    public void printA() {
        while (true) {
            while (counter % 3 != 0) {
                Thread.yield();
            }
            System.out.print("A");
            counter++;
        }
    }

    public void printB() {
        while (true) {
            while (counter % 3 != 1) {
                Thread.yield();
            }
            System.out.print("B");
            counter++;
        }
    }

    public void printC() {
        while (true) {
            while (counter % 3 != 2) {
                Thread.yield();
            }
            System.out.print("C");
            counter++;
        }
    }

    public static void main(String[] args) {
        PrintABC printABC = new PrintABC();
        new Thread(()-> printABC.printA()).start();
        new Thread(()-> printABC.printB()).start();
        new Thread(()-> printABC.printC()).start();
    }
}

股市买卖问题

故事买卖类的问题主要使用动态规划进行解决，只是复杂程度不同罢了。

递归方程的建立考虑以下问题：

• 目的：能够获得的最大利润

• 联系：一共有n天需要记录，每天有两种状态，当天有股票或没股票

  • 今天没有股票：昨天也没买今日未操作，或者卖掉股票获得钱
  • 今天有股票：昨天就已经买入股票今日未操作，或者今日买入股票

• 优化：是否需要记录每一天，还是只与上一天的结果有关。

Binary Search 二分搜索

二分搜索的关键在于：

1. 搜索 [0, len-1] 这个闭区间，还是 [0, len) 这个开区间.
2. 如果是闭区间，则循环条件使用 while(left <= right)；如果是开区间，则使用while(left < right)。很好理解，考虑列表只有一个因素的情况，闭区间是[1,1]需要等于搜索。
3. 思考返回的问题：
   • 如果元素是不重复的，可以直接if(nums[mid] == target) return mid;判断返回。
   • 如果元素是重复的，需要考虑返回第一个重复元素还是最后一个重复元素的问题。
     • 返回第一个：if (nums[mid] == target) right = mid - 1; 锁定左侧边界，返回值为：return nums[left] == target ? left : -1;
     • 返回最后一个：if (nums[mid] == target) left = mid + 1; 锁定右侧边界，返回值为：nums[right] == target ? right : -1;

Nacos Introduction 简介

主要功能

服务发现：帮助各个微服务发现所需的调用方服务。

配置管理：将配置文件发送到各个微服务用于服务启动和动态调整

如果我们要启动一个springboot应用，我们需要在application.properties(或.yml)进行相关的配置，但如果这个应用要启动成百上千个，对于其的配置就会要重复非常多次，而一旦要变更配置也会更加麻烦，这就是为什么需要一个配置管理的中间件来帮助进行其他中间件和业务组件的配置。

详情

Nacos 进行配置管理

Nacos支持多种配置管理模式，当已经启动一个nacos实例后，访问http://localhost:8848/nacos就能访问nacos的Dashboard，可以看到有以下支持。

比如，我的一个Springboot项目中就用到了下面这种配置方式，主要用到的就是properties和YAML两种