• 知识梳理
  • Jvm性能调优
    • 类的加载
    • 主要组成部分
    • 垃圾回收机制
    • 类的对象
    • 常量池
  • Tomcat深度剖析
    • Tomcat的Endpoint组件与操作系统建立Socket连接
  • MySQL深度剖析
    • 索引结构
    • 引擎分类
    • 索引的优化原则
    • 锁机制
    • 索引类型
    • 语言分类
    • 分布式
    • 多版本的并发控制MVCC
  • 并发编程专题
    • 并发基础
    • 并发缓存一致性MESI
    • happens-before原则
    • Synchronized(同步)
    • ReentrantLock(独占互斥)
    • 线程间的通信
    • Atomic原子类(乐观锁)
    • ThreadPool线程池
  • 源码框架专题
    • Spring常用注解
    • 认识Spring Boot
    • Spring Boot作用
    • Spring两大特性
    • Bean的生命周期
    • BeanFactory和ApplicationContext的区别
    • SpringBoot自动配置的原理
    • Spring IOC加载过程
    • 三级缓存应对循环依赖
    • Spring AOP
    • Spring MVC的运作流程
  • 核心知识专题
    • 网络协议
    • HTTP状态码
    • TCP传输
    • Servlet生命周期
    • 跨域资源共享CORS
    • 跨域请求伪造CSRF
    • 输入域名访问过程
    • 网络IO模型
    • 同步与互斥
    • 进程调度算法
    • DDOS网络攻击
  • 中间件专题
    • Redis
    • Zookeeper
    • RabbitMQ
    • Kafka
  • 算法与数据结构
    • 数据结构
    • 算法

知识梳理

Jvm性能调优

类的加载

• 类的加载过程

  • 加载

  • 验证

  • 准备

  • 解析

  • 初始化

• 类的双亲委托机制

  • 加载器分类

    • 引导类加载器

    • 扩展类加载器

    • 应用程序类加载器

    • 自定义类加载器

  • 机制的好处

    • 沙箱保护机制

    • 防止类的重复加载

主要组成部分

• 类加载器

• 字节码执行引擎

• JVM内存结构(运行时数据区)

  • 方法区

  • 堆内存

  • 线程栈

  • 程序计数器

  • 本地方法栈

垃圾回收机制

• 垃圾回收算法

  • 复制算法

  • 标记-清除算法

  • 标记-整理算法

  • 分代回收机制

类的对象

• 创建过程

  • 类加载

  • 分配内存

  • 初始化内存

  • 设置对象头

  • 执行<init>

• 对象分配

  • 分配方式

    • 指针碰撞

    • 空闲列表

  • 并发环境

    • CAS

    • TLAB

  • 分配在栈上

    • 逃逸分析

    • 标量替换

  • 分配在堆上

    • 设置最大分代年龄

    • 大对象直接放在老年代

    • 动态分代年龄判断机制

    • 老年代空间担保机制

• 垃圾收集算法

  • 复制算法

  • 标记清除算法

  • 标记整理算法

• 垃圾收集器

  • 新生代

    • Serial

    • ParNew

    • Parallel

  • 老年代

    • SerialOld

    • ParallelOld

    • CMS

      • 增量更新+写屏障避免漏标

  • G1

    • Region内存区域分块

    • Humongous大对象存储块

    • PauseTime设置垃圾回收停顿时间

    • MixedGC新垃圾回收分类

    • Snapshot At The Beginning原始快照

      • 写屏障+原始快照避免漏标

• 对象的跨代引用

  • 记忆集 + 卡表

常量池

• class常量池

  • 方法区

• 运行时常量池

  • 方法区

• 字符串常量池

  • 堆内存

• 基础类型常量池

  • 堆内存

Tomcat深度剖析

Tomcat的Endpoint组件与操作系统建立Socket连接

MySQL深度剖析

索引结构

• B+树

• Hash

引擎分类

• Mylsam

• Innodb

索引的优化原则

• 码先行

• 联合索引覆盖查询条件

• 不在小基数上建立索引

• 字符串建立前缀索引

• 优先优化where语句

• 根据慢查询优化SQL

• Limit分页优化

• Join小表驱动大表

• 联合索引最左前缀原则

• Like模糊查询不出现左模糊

锁机制

• 性质分类

  • 乐观锁(不依赖于MySQL锁机制)

  • 悲观锁

    • 读锁

    • 写锁

• 粒度分类

  • 行锁

  • 表锁

索引类型

• 主键索引

• 唯一索引

• 普通索引

• 全文索引

语言分类

• DDL数据定义语言，例如CREATE、DROP等

• DQL数据查询语言，例如SELECT

• DML数据操作语言，例如UPDATE、DELETE、INSERT

• DCL数据权限语言，例如GRANT等

分布式

• binlog快照提供主从复制功能，搭建主从架构实现读写分离，保证安全性、高可用

  • statement

  • row

  • mixed

• 分布式架构解决方案

  • MMM

  • MHA

  • MGR

多版本的并发控制MVCC

• undo log事务操作历史记录链

• read-view一致性视图

  • 未提交的事务ID数组

  • 已提交事务的最大ID

并发编程专题

并发基础

• 计算机五大组成部分

• CPU核结构：寄存器+三级缓存

• 并发编程的三要素

• CPU高速缓存

• 进程与线程

并发缓存一致性MESI

• 地位是替代了性能较差的总线锁

• M修改

• E独占

• S共享

• I舍弃

happens-before原则

• volatile(内存屏障)

• 锁机制

• 语义顺序

• 传递性

• 对象回收

• 线程

  • start()

  • interrupted()

  • join()

Synchronized(同步)

• 临界资源

• 锁膨胀

• 逃逸分析

  • 锁粗化

  • 锁消除

ReentrantLock(独占互斥)

• AQS特性

  • 公平/非公平

  • 共享/独占

  • 阻塞等待队列

  • 可重入

  • 允许中断

线程间的通信

• Blocking Queue阻塞队列

  • 类型

    • ArrayBlockingQueue

    • LinkedBlockingQueue

    • DelayQueue

    • ConcurrentLinkedQueue

  • 场景

    • 生产者与消费者

  • 关键API

    • put()

    • take()

• Semaphore信号量

  • 作用

    • 限制访问特定资源的线程数目

  • 场景

    • 限流

  • 关键API

    • acquire()

    • release()

• CountDownLatch计数器

  • 场景

    • 确保前置组件完成初始化

  • 关键API

    • await()

    • countDown()

  • 一次性，不可重用

• CyclicBarrier栅栏屏障

  • 作用

    • 阻塞的线程相当于加上一道屏障点，当加最后一道屏障后唤醒所有的线程（又称为同步点）

  • 场景

    • 模拟高并发

  • 关键API

    • await()

  • 可重用

• ForkJoin

• Discruptor

Atomic原子类(乐观锁)

• 内部实现

  • Atomic是基于魔术类Unsafe提供的CAS-API实现的，通过offset偏移量确定需要修改的值在主内存中的位置，从而比较并修改成新的值，这种方式保证了操作的原子性，整个过程是无锁操作的，又称为乐观锁

• Unsafe魔术类

  • 越过JVM内存管理

  • 访问直接内存

  • 自主管理内存的创建与回收

ThreadPool线程池

• 线程与协程的关系

• 三个主要的拒绝策略

• 抛出异常的线程

• 线程池的五种状态

• ScheduledThreadPool定时线程池

  • Timer

  • 三种定时方式

    • 定时执行

    • 周期定时执行

    • 周期延时执行

源码框架专题

Spring常用注解

• 认识@注解Annotation

  • @Target

    • 表示当前注解可标记在哪里

  • @Retention

    • 表示编译以什么方式保留，搭配RetentionPolicy.RUNTIME会被JVM加载

  • @Document

    • java doc会生成注解信息

  • @Inherited

    • 表示可以被继承

• 启动类

  • @SpringBootApplication

    • 搭配SpringApplication启动Web应用

• 控制层

  • @RestController

    • 相当于@ResponseBody ＋ @Controller合在一起，作用于接收请求并返回结果

  • @RequestMapping

    • 请求的映射

• 测试类

  • @SpringBootTest

    • SpringBoot的测试类，常搭配junit的@Test注解使用

  • @TestPropertySource

    • 指定当前测试类启动使用的应用配置

• 声明Bean

  • @Configuration

    • Spring底层会给配置方法创建Cglib代理，防止重复创建Bean对象（默认单例）

    • @Component

      • 泛指Bean组件(例如pojo)

    • @Conditional

      • @Conditional系列注解决定当前配置类是否生效

  • @Component

  • @ComponentScan

  • @Import

    • 不声明配置类时，可以通过Import进行自定义配置类的导入，例子可见SpringBoot启动自动配置

  • @ImportResource

  • @Service

• Bean使用

  • @Value

    • 使用方法SPEL：@Value("${server.port}")，绑定配置文件中属性的值

  • @ConfigurationProperties

    • 提供Bean属性与配置文件的绑定，例如(prefix="user")自动填充user的属性，支持relaxed binding松散绑定

      • .properties

      • .yml

  • @Validated

    • 支持JSR-303数据校验

• 代理类

  • @ProxyTargetClass

    • 设置为true强制使用CGLIB动态代理

认识Spring Boot

• Spring Boot是基于Spring框架开发，目的是简化应用的搭建与使用

  • 容器

    • IOC

    • AOP

  • 注解配置

  • maven仓库自动管理Jar版本，避免冲突

  • 内置Tomcat快速启动Web应用

Spring Boot作用

• SpringBoot是一种轻量级的Java开发框架，基于Spring框架实现，目的是简化企业级应用开发的复杂度，使得应用的搭建与使用更加便捷

Spring两大特性

• DI

• AOP

Bean的生命周期

• 实例化Bean

• 填充属性

• 装载Bean

• 初始化

• 销毁Bean

BeanFactory和ApplicationContext的区别

• BeanFactory是一个Bean工厂，以简单工厂模式的方式工作，职责是生产和获取Bean

• ApplicationContext是BeanFactory的派生类

  • 管理Bean生命周期

  • 自动注册处理器

  • 国际化

  • 事件的监听与发布

SpringBoot自动配置的原理

• 特性

  • DefferedImport延时导入

  • Group分组导入

• 自动配置流程

  • 入口@SpringBootApplication注解内置启用自动配置

  • SpringFactoriesLoader获取SpringFactories列表，即所有的自动配置类

  • pom依赖过滤当前场景使用到的配置

  • 判断配置类是否满足@Conditional条件注解

Spring IOC加载过程

• 实例化 ApplicationContext

• 实例化 BeanFactory

• init()

  • 实例化 BeanDefinitionReader

    • 将包括解析配置类的相关处理器和解析注解的相关Bean注册到Bean定义中

  • 实例化 BeanDefinitionScanner

    • 将包括扫描Package作用范围的相关处理器和Bean注册到Bean定义中

• register()

  • 将配置类注册到Bean定义当中

• refresh()

  • 执行所有已注册的处理器，包括扫描并注册Package作用范围的配置类到Bean定义中

  • BeanFactory根据Bean定义生成Bean对象

    • 单例Bean且不是懒初始化会被初始化进一级缓存

三级缓存应对循环依赖

• 先检查缓存中是否命中当前Bean，没有则创建

• 在实例化之前的入口处添加标记

• 在实例化之后添加获取未初始化的对象或者是动态代理对象的钩子函数到三级缓存中

• 出现循环依赖时会调用到三级缓存中的函数获取到相应对象，并将其赋给二级缓存，跳出循环

• 对象完成初始化后会将初始化好的对象放在一级缓存当中，并移除其在二级、三级缓存的对象

Spring AOP

• AOP的全称是Aspect Oriented Programming 面向切面编程，运用设计模式中的代理模式，也就是在不修改原有代码的情况下对方法做增强处理

  • 实现方式

    • XML

    • 注解

    • 接口

  • 作用过程

    • 遍历IOC容器中的BeanName

    • 解析带有@Aspect注解的切面类

    • 提取通知对应生成Advisor对象添加到缓存中

    • 在执行方法时检查是否命中切面切点

    • 若命中则创建代理进行增强

Spring MVC的运作流程

• 前端控制器接收到客户端请求

• 查询处理器映射返回对应的处理器适配器

• 由适配器执行相应的控制器方法

• 控制器方法的返回值交给视图解析器

• 最后由视图解析器渲染视图相应给前端进行展示

核心知识专题

网络协议

• 网络协议是用于指定网络传输的数据规则

• 网络分层

  • OSI七层参考模型

    • 应用层

      • 不同的应用协议服务于不同的应用程序

    • 表示层

      • 负责将应用数据格式与网络数据格式进行转换

    • 会话层

      • 负责建立、管理、中断进程之间的通信连接

    • 传输层

      • 建立点对点之间的数据传输

    • 网络层

      • 确定目标地址以及路由协议

    • 数据链路层

      • 确定链路层协议，负责将比特流和数据帧进行转换

    • 物理层

      • 物理设备、传输介质，负责将比特流和电信号进行转换

  • TCP/IP四层模型

    • 应用层

      • TELNET、SSH、HTTP、HTTPS、SMTP、FTP等

    • 传输层

      • TCP协议

        • TCP协议是一种有连接的可靠协议，建立和中断一次TCP传输至少需要经过七次的发包收包，传输的代价较大，换来的是安全性，适用于HTTP、SMTP等应用场景

      • UDP协议

        • UDP协议是一种无连接的不可靠协议，发送端不关心接收端是否收到准确的数据，这是一种不安全的协议，但是传输速度较快，适用于视频、语音通信等应用场景

    • 网络层

      • IP协议

        • IP协议是一种无连接、不可靠的传输协议，负责数据报的传输，简洁且速度快

      • ICMP协议

        • ICMP协议在网络传输出现异常时负责异常通知

      • ARP协议

        • ARP协议负责将IP地址解析成MAC物理地址

    • 接口层

HTTP状态码

• 1XX

  • 表示请求正在进行处理

• 2XX

  • 表示请求已完成

  • 常用的状态码

    • 200 OK

      • 请求已正常处理

    • 204 No Content

      • 请求处理成功，但没有任何资源可以返回

    • 206 Partial Content

      • 完成对资源的范围请求

• 3XX

  • 表示需要进一步的操作

  • 常用的状态码

    • 301 Moved Permanently

      • 永久性重定向

    • 302 Found

      • 临时性重定向

    • 304 Not Modified

      • 资源已找到，但未符合条件请求

• 4XX

  • 表示客户端错误

  • 常用的状态码

    • 400 Bad Request

      • 无法理解客户端发送的请求

    • 401 Unauthorized

      • 表示发送的请求有未通过的认证信息

    • 403 Forbidden

      • 资源的不允许访问

    • 404 Not Found

      • 没有请求的资源

• 5XX

  • 表示服务端错误

  • 常用的状态码

    • 500 Internal Server Error

      • 服务器内部资源出故障

    • 503 Service Unavailable

      • 表明服务器暂时处于超负载或正在停机维护

TCP传输

• 探测信号

  • 当客户端在TCP连接过程中断开，服务端会连续发送十次探测信号，若客户端无响应则断开连接

• TCP的2MSL问题

  • MSL全称是Maximum Segment Lifetime，表示数据包传输的最大生存时间

  • 四次挥手后客户端等待2MSL才关闭连接是因为数据包的一去一回的最长时间正好是2MSL，等待时间是为了确认服务端收到了连接关闭的信号

• 窗口控制

  • 窗口的引入是为了优化TCP传输发送和回应对网络性能的消耗，它的大小表示服务端无需等待回应而可以继续发送数据包的最大值

  • 窗口控制

    • 窗口控制表示即使丢失了部分客户端的答应信号也没有关系，会以最新的序号进行窗口的滑动

  • 重发控制

    • 当服务端连续三次收到来自客户端的同一个响应，那么服务端就认为数据报在发送的过程中丢失了，因而触发重发机制，重发丢失的数据报

• 拥塞控制

  • 拥塞控制的出现是为了避免应用程序刚启动时TCP传输大量的数据包导致网络拥堵，甚至网络瘫痪的现象

  • 拥塞控制的算法及其作用原理

    • 慢开始

      • 慢开始是指拥塞窗口从1开始的每次数据包往返按1/2/4的指数函数增长，直到拥塞窗口到达拥塞阈值时，将算法切换成拥塞避免

    • 拥塞避免

      • 拥塞避免是指拥塞窗口从阈值开始的每次数据包往返加1的线性增长，直到发生超时或是重发的现象时，将算法切换成快重传和快恢复算法

    • 快重传和快恢复

      • 快重传和快恢复算法一般是搭配使用的，分两个情况分析

        • 超时

          • 将此时的拥塞窗口值设置为1，阈值设置为当前拥塞窗口大小的一半，将算法切换为慢开始

        • 重发

          • 将此时的拥塞窗口和阈值都设置为当前拥塞窗口大小的一半，将算法切换为拥塞避免

Servlet生命周期

• init初始化

• service执行服务

• destory销魂

跨域资源共享CORS

• 跨域资源共享（Cross-origin resource sharing）是为了解决当前脚本请求资源的域与目标资源的域不一致时，会出现跨域请求错误

• 发生跨域请求的三个条件

  • 协议不同(HTTP/HTTPS)

  • 域名(<www.a.com/www.b.com>)

  • 端口(80/8080)

• 解决跨域请求的方式

  • Access-Control系列响应头

  • Nginx反向代理映射同域访问到不同域的资源

  • jsonp的callback回调函数

跨域请求伪造CSRF

• 跨域请求伪造（Cross-site request forgery）指的是攻击者伪造正常用户对服务器进行请求

• 解决跨域请求伪造的方式

  • 验证码

  • Refer请求头验证

  • _CSRF随机生成认证Token

输入域名访问过程

• DHCP动态主机配置协议给本机分配IP地址，同时获取DNS服务器的IP地址、网关的IP地址

• ARP协议解析网关的IP地址得到物理MAC地址

• 走出网关访问DNS服务器，解析目标域名的IP地址

• 与目标IP地址建立TCP传输连接

网络IO模型

• BIO

• NIO

• AIO

同步与互斥

• 同步指的是多个同步代码块顺序执行

• 互斥指的是多个线程访问同一个临界值时只有一个线程能够进入

进程调度算法

• 先来先服务

• 短作业优先（非抢占）

• 最短剩余时间优先（抢占）

• 最高响应比优先

DDOS网络攻击

• DDOS全称是分布式拒绝服务攻击，攻击者伪造正常用户对服务器发送建立连接的请求，接受到同步请求后不向服务端返回响应从而达到占用服务端连接资源的目的

• 应对DDOS网络攻击的方式

  • IP拦截

  • 路由拦截

  • 透明代理CDN

  • 部署数据清洗服务

中间件专题

Redis

• 认识Redis

  • 五大基础类型

    • 字符串

      • 订单ID自增

      • string:set、get、del…

    • 哈希表

      • 购物车

      • hash:hset key field value…

    • 列表

      • 推文

      • list:lpush、lrange…

    • 无序集合

      • 抽奖

      • set:sadd、spop、srandmember…

    • 有序集合

      • 热搜

      • sorted-set:zadd key score member…

  • 持久化

    • RDB

    • AOP

    • Redis4.0混合持久化

  • 集群

  • 数据存储在内存

  • IO多路复用

• 主从复制架构

  • 主从复制，从节点向主节点发送sync数据同步信号，主节点自动调用bgsave异步RDB持久化 + 写时复制，持久化结束后将数据包传给从节点

  • 数据传输过程若出现网络中断，会根据主节点存储的offset偏移量实现断点续传

  • 尽量避免一个主节点下挂载大量的从节点，因为有可能出现从节点的同步请求过多导致主机风暴；解决方案是将部分从节点挂载到其他从节点

  • 从节点晋升为主节点需要基于哨兵结构下，哨兵节点监听主从节点，当主节点无响应时会在从节点中选出新的主节点

• Redis原子操作

  • 借助Lua脚本实现一系列操作在单次IO执行完毕，从而保证这些操作的原子性

• 集群架构

  • 搭建集群后默认会开启gossip服务，此时会占用port+10000的端口

  • 主节点的选举需要集群下的从节点获得整个集群中超过半数的其他集群主节点的响应

• Redis实战项目解决方案

  • 缓存穿透

    • 缓存穿透是不存在的缓存数据被频繁访问，穿透访问DB的情况

    • 缓存空对象

    • 布隆过滤器

  • 缓存击穿(失效)

    • 缓存失效出现在大批量缓存在某时刻同时失效，可能导致大量请求同时穿透直达DB

    • 避免缓存同时失效，额外添加随机的过期时间

  • 缓存雪崩

    • 缓存雪崩指的是Redis无法抗住大量请求崩溃，请求穿透同时把DB也击溃，导致应用崩溃

    • 请求异步 + 消息队列限流

    • Redis搭建集群 + 哨兵架构

  • 热点Key

    • 热点Key问题是指某个未建立缓存的值被某一时刻的高并发量访问

    • setnx(set if not exist)分布式锁 + 轮询获取

  • 双写不一致

    • 业务容忍短时间不一致（商品名称、商品分类菜单等）：设置缓存过期时间

    • 必须强一致（商品价格、订单信息）：读写锁

Zookeeper

• 类似文件系统，由文件节点组成，常用于分布式架构的配置文件信息的同步

• 文件节点事件监听-w

  • 监听文件节点

    • 修改节点

  • 监听文件夹节点

    • 增加/删除节点

• ACL权限控制

  • c增加节点

  • d删除节点

  • r读取节点

  • w修改节点

  • a控制权限

RabbitMQ

• 消息中间件好处

  • 解耦，便于维护、扩展

  • 异步，提高应用程序响应效率

  • 削峰，限流，提高系统稳定性

• 交换机的作用/模式

  • 广播（工作、关注订阅）

  • 路由直连

    • 全文匹配

  • Topic

    • 通配符匹配

• 消息队列的工作模式

  • 工作队列Queue

  • 发布订阅P/S

  • 路由模式Route

    • 指定路由

  • 主题模式Topic

    • 通配符匹配路由

Kafka

• 六大术语

  • Broker服务节点

    • 通过ZK同步配置信息，且集群中的服务节点ID不能相同

  • Producer生产者

    • 指定Topic发送消息

  • Topic主题

  • Partition(主题)分区

    • 算法根据主题、序列化键值进行哈希

  • Consumer消费者

  • ConsumerGroup消费组

    • 以消费组为单位接收监听主题的消息

算法与数据结构

数据结构

• 物理结构

  • 数组

    • 适用于查询

  • 链表

    • 适用于插入、删除

• 逻辑结构

  • 队列Queue

  • 栈Stack

  • 哈希表Map

  • 树Tree

  • 堆Heap

  • 图Graph

算法

• 排序算法

  • 简单排序

    • 选择排序

      • O(n²)，原地算法，不稳定

    • 插入排序

      • O(n²)，原地算法，稳定

    • 冒泡排序

      • O(n²)，原地算法，稳定

  • 复杂排序

    • 希尔排序

      • O(n²)&gt;O(x)&gt;O(nlogn)，原地分组排序算法额外空间复杂度O(1)，不稳定

    • 快速排序

      • O(nlogn)，递归栈辅助空间O(logn)，不稳定

    • 堆排序

      • O(nlogn)，原地操作堆，稳定

    • 归并排序

      • O(nlogn)，数组辅助空间O(n)，稳定

    • 基数排序

      • 数组长度n，数字十进制位数d，辅助基数r

      • O(d(n+r))，基数辅助空间O(r)，稳定

• 查找算法

  • 二分查找

  • 跳表

    • 每隔一个元素建立更高一级的索引

  • 暴力查找

  • 哈希查找

  • KMP

    • 动态规划构建next数组，时间复杂度O(n)

• 竞赛算法

  • 搜索算法(自顶向下)

    • 广度优先

    • 深度优先

    • A*算法

  • 动态规划(自底向上)

    • 确定初始状态，列出状态转换方程

  • 最短路径算法

    • 单源最短路径：迪杰斯特拉算法

    • 多源最短路径：弗洛伊德算法

  • 数学

    • 螺旋数组遍历

    • 质数/素数

    • 字典序算法

      • 全排列的数量

        • 无重复字符

          • A(n,n) = n (n-1) (n-2) … 1

        • 有重复字符：重复字符组g，重复个数g1-&gt;m1，字符总数n

          • A(n,n)/A(m1,m1) A(m2m2) … A(mg,mg)
      • 下一个全排序

      • 12354 -&gt; 12435

        • 从右到左查找第一个降序的值，记为r

        • 123(r)54

        • r右侧的字符倒序

        • 123(r)45

        • index从r向右搜索第一个大于r的值

        • 123(r)4(index)5

        • r和index交换位置得到结果
        • 124(index)3(r)5
      • 上一个全排序

      • 12534 -&gt; 12453

        • 从右到左查找第一个升序的值，记为r

        • 125(r)34

        • r右侧的字符倒序

        • 125(r)43

        • index从r向右搜索第一个小于r的值

        • 125(r)4(index)3

        • r和index交换位置得到结果
        • 124(index)5(r)3

    • 贪心

    • 卡特兰数论

      • f(n)=C(2n,n) 1/(n+1)=f(n-1) f(0) + f(n - 2) f(1) + f(n - 3) f(2) + … + f(0) * f(n - 1)

    • 组合数C(n,m) = n! / m! * (n - m)!

      • 费马小定律(求阶乘 + 逆元)

        • 如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）

        • 通常
        • p是1e9+7，质数

        • a是小于1e9+7的值

          • 那么
          • a^（p-1）≡1（mod p）
          • 可得
          • a^（p-2）* a ≡1（mod p）
          • 即a的逆元等于a^（p-2）

    • 快速幂模

      • n^m = n^2^m/2 * ((m&1) == 1 ? n : 1)

        • m是奇数

          • (n n) ^ m/2 n

        • m是偶数

          • (n * n) ^ m/2

    • MOD

      • 通常取模mod = 1000000007

        • Integer.MAX_VALUE= 2147483647

        • 2的31次方-1，Integer.MAX_VALUE / mod ≈ 2

        • Long.MAX_VALUE=9223372036854775807
        • 2的63次方-1，19位数

      • 一般需要取模的题目最好用long

  • 单调栈

    • 二维问题，一维排序，另一维划分多个单调区间

  • 前缀和

    • 一维前缀和

      • dp[n] = dp[n-1] + arr[n]

      • 涉及连续数组数量或最大长度时，通常配合哈希表使用

    • 二维前缀和

      • dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[n]

  • 缓存淘汰算法

    • LRU

      • 双向链表

        • LinkedHashMap重写removeEldestEntry

    • LFU

      • 带权值的双向链表

  • 最小生成树

    • Kruskal

      • 排序 + 判环

    • Prim

      • 循环每轮确定一个最短路径(类似单源最短路径)

  • 位运算

    • 运算符

      • 与 &

      • 或

      • 非 ~

      • 异或 ^

    • 负数进制 转 负数的绝对值

      • 反码 再 + 1

    • 负数的绝对值 转 负数进制

      • -1 再 反码