牛客剑指offer(1~20题总结)
T1
思路：
已知前序遍历： 根-左-右 中序遍历：左-根-右 还原二叉树
首先前序遍历的第一个点一定是当前树的根节点，那么可以根据其值在中序遍历中确定位置 i。这样就将原来树的中序遍历划分为了左子树和右子树的中序遍历。同样可以根据左右子树的长度再去前序遍历中进行左右子树的划分。
扩展：
这题如果是已知中序遍历和后序遍历也可以按照类似方法做。
T2
思路
这题实际上是要我们确定树B 是否是 树A的子树，而不是子节点。
根据树B的 root 值到树A中去查询找到值相等的点；然后遍历以该点为根节点树的所有值是否和树B中对应点的值相等；
如果 步骤1 返回 false，那么继续判断树B 是否是 树A的左子树的子树；
如果 步骤2 返回 false，那么继续判断树B 是否是 树A的右子树的子树；
T3
思路：
题目要求查找栈中的最小元素，而且要求时间复杂度为 O(1)
由于时间复杂度为 O(1)，必须是随机查找。这里可以使用双栈法。
双栈法：生成两个栈，栈2作为辅助栈，每次栈1 插入一个元素 栈2 也进行比较后插入；
https://blo ...
JVM、(二)JVM的内存结构
一、程序计数器(PC)定义： Program counter Register作用：记住下一条JVM指令的执行地址。(通过寄存器来实现的)
二进制字节码通过解释器被解释为机器码，然后机器码才能够交给CPU去执行。当第1条JVM指令被解释翻译执行后 程序计数器会去记录下一条JVM指令的执行地址然后接着执行。
特点：* **线程私有的**。程序运行时会开启多个线程，CPU会对这些线程进行调度，每个线程有着自己的时间片。当时间到但是线程1还未执行完，线程1的程序计数器便会记录此时执行到的指令的位置；然后切换到线程2去执行，同理线程2也有自己的程序计数器。
* 不会存在内存溢出。
二、虚拟机栈(Virtual Stack)定义：
栈 - 线程运行需要的内存空间；由多个栈帧(Frame)组成。
栈帧 - 每个方法调用时需要的内存；
栈与栈帧的关系 - 每个线程只能有一个活动栈帧，对应着正在执行的那个方法(位于栈顶部的那个栈帧)；
一个栈中可能存在多个栈帧。比如说某个方法执行时会需要一些参数、局部变脸、返回地址。这些都被记录在栈帧这个内存空间中。也可能在执行该方法时还调用了其余的 ...
JVM、(一)JVM开篇
一、JVM是什么？
定义：Java Virtual Machine - java程序的运行环境 （Java 二进制字节码的运行环境）比如 Helloworld.java 程序通过javac编译成了 class字节码然后被加载到java虚拟机中运行。
好处：
跨平台实现的基石。 Java程序一次编译，到处运行，JVM屏蔽了字节码和底层操作系统之间的差异，使得编译后的二进制字节码文件能够运行在不同的操作系统平台上。
自动内存管理，垃圾回收功能。
数组下标越界越界检查。
多态。
比较(jre、jdk、jvm)：jre：java runtime environment(Java运行时环境) jvm结合一些基础类库构成了jre；jdk：java development kit(Java 开发工具包) jvm+基础类库+编译工具构成 jdk；
二、常见的JVM
三、学习路线重点：
JVM主要涉及三大块： 类加载器ClassLoader、JVM内存结构(方法区、堆、虚拟机栈、本地方法栈、程序计数器)、执行引擎(解释器、即时编译器、垃圾回收)
一个java程序通过编译为二 ...
Redis(7).集群
一、集群是什么？集群：集群就是使用网络将若干台计算机联通起来，并提供统一的管理方式，使其对外呈现单机的服务效果。
集群的作用：
分散单台服务器的访问压力，实现负载均衡；
分散单台服务器的存储压力，实现可扩展性；
降低单台服务器宕机带来的业务灾难。
二、集群的存储结构设计对于输入的一个key，不是直接将其存储到某台服务器中，而是通过算法设计计算出应该存放的位置，之后再存储。
如果此时集群中加入了新的服务器，那么各个服务器需要需要给出各自的部分空间组成新的存储空间(给出的空间称为槽)。各个机器持有一定的槽，当加机器时分出自己的部分槽给新的机器，减机器时再将这些槽返回给其余机器。不管多少台服务器，槽(slot)的总数不变都是16387，但是随着空间的增大每个槽的内存变大了。从而实现了扩容。
各个数据库相互通信，每个数据库都持有所有槽的编号数据。当一个key经过两次算法计算得到具体的位置数值，如果此时访问A会去A中查找，如果命中了直接返回。如果一次未命中，则告知具体的位置直接去查找。
槽用来区分数据的存储空间；
key 用来加密后确定数据的存储位置；
一次命中或者两次命中就能够找到 ...
Redis(8).企业级解决方案
一、缓存预热
概念： 缓存预热就是在系统启动前，提前将相关的缓存数据加载到缓存系统。避免在用户请求的时候，先查询数据库，然后再将数据缓存的问题！用户直接查询实现被预热的缓存数据！
解决方案：
二、缓存雪崩
概念：缓存雪崩可以理解为原有缓存失效，新缓存还未到期间(例如：我们设置的缓存过期时间相同，统一时间大面积的缓存过期)，所有原本应该访问缓存的请求都去查询数据库了，而对数据库和CPU和内存产生巨大压力，严重的造成宕机影响。从而造成一连锁的反应，致使整个系统崩溃。
正常缓存的获取图：缓存失效瞬间：
解决方案：
加锁方法详解：
(1)一般并发量不是特别高的时候可以通过 加锁排队 的方式来解决高访问量问题：
1234567891011121314151617181920212223//伪代码int cacheTime = 30; //缓存过期时间String cacheKey = "product"; //缓存keyString lockKey = cahceKey;public Object getP ...
Redis(6).哨兵模式
一、哨兵模式简介哨兵(Sentinel) 是一个分布式系统，用于对主从结构中的每台服务器进行监控，当出现故障时通过投票机制来选举出新的master并将所有的slave连接到新的master。哨兵也是一台redis服务器，只不过不提供数据服务。哨兵通常配置为单数。
二、哨兵的搭建
sentinel.conf 配置文件解读
123456789101112131415161718192021222324252627282930313233343536# Example sentinel.conf# port <sentinel-port>port 8001# 守护进程模式daemonize yes# 指明日志文件名logfile "./sentinel1.log"# 工作路径，sentinel一般指定/tmp比较简单dir ./# 哨兵监控这个master，在至少quorum个哨兵实例都认为master down后把master标记为odown# （objective down客观down；相对应的存在sdown，subjective down，主观d ...
Redis(5).主从复制
一、主从复制的概念为什么需要主从复制，因为单机Redis会存在以下问题： ①机器故障，那么原本机器中的业务数据会损害造成不可挽回的损失；②容量瓶颈，单继Redis的内存有限，硬件条件拉跨无法存储巨额数据；为了避免这些问题保证数据的安全性和服务器的高可用性出现了主从复制。主从复制是指，主机数据更新后根据配置和策略，自动同步到备机的master/slaver 机制，Master以写为主，Slave 以读为主。
二、主从复制基础用法简介：
2.1 工作流程（1）建立连接
首先由 slave(从服务器)向 master(主服务器) 发送 slaveof ip port 指令申明称为 master的从机。紧接着slave 会保存master的地址(masterhost)和端口(masterport)以保存master的信息，然后根据保存的信息建立起与主机间的socket连接。为了保证连接的不中断同时slave会不断发送ping命令来测试连接是否联通。如果主机设置了密码，此时还需要从机进行身份验证auth password来向主机核验自己的身份，如果验证授权通过从机才可以发送指 ...
Redis(4).事务
一、Redis事务是什么？概念：
可以一次执行多个命令，本质是一组命令的集合。一个事务中所有命令都会序列化，按顺序地串行化执行而不会被其它命令插入，不允许阻塞。
如何使用？
事务相关命令：(1) DISCARD 取消事务，放弃执行事务块内地所有命令；(2) EXEC 执行所有事务块内的命令；(3) MULTI 标记一个事务块的开始；(4) UNWATCH 取消WATC命令对所有key的监视；(5) WATCH key [key ....] 监视一个或者多个key，如果在事务执行之前这个key被其它命令所改动，那么事务会被打断；
事务的正常执行：
放弃事务：
全体连坐：类似于Java中的异常处理，书写代码时就会报错，但是它不会处理 1/0=xx 这种错误，这种错误需要在编译时才能被发现。
冤头债主：说明了Redis对事务是部分支持
watch监控
表锁：将整张表锁住，其它行的任何操作都不行；
行锁：仅仅锁住这一行。
悲观锁：类似于表锁。数据的正确性是最高的。
乐观锁：类似于行锁。每条记录包括一个Version版本信息，每次有用户修改后Ver ...
Redis(3).持久化操作
一、Redis配置文件解析
INCLUDES 包含
作用：类似于Struct2 配置文件，可以通过 INCLUDES来包含其它配置文件，redis.conf 可以作为总闸。
GENERAL 通用
Daemonize：是否作为守护线程运行，如果开启则开机自启
Pidfile： 进程管道pid文件
Port：redis运行的端口
Tcp-backlog：backlog其实是一个连接队列，用来避免慢客户端连接问题。
Timeout：在多长的空闲时间后会关闭连接，默认值为0，表示不关闭
Bind： 绑定的ip地址
Tcp-Keepalive：用于定时检测连接是否正常，单位为秒，如果设置为0，则不会进行Keepalive检测，建议设置为60
Loglevel：日志级别，redis默认有4种日志级别 debug、verbose、notice、warning，日志级别由低到高主键上升。
logfile：日志保存的路径；默认为标准输出，如果Redis设置为守护进程方式运行，而这里又配置为标准输出，则日志会发送给 /dev/null
sys-log-enabled： 是否允 ...
Redis(2).jedis线程池
一、什么是jedis
jedis是 Java语言 连接 redis服务的一个工具，常用的包括 Jedis、SpringData Redis、Lettuce
java-jedis 操作redis 和 redis自身的命令完全一致。
二、使用步骤1.Jedis 读写redis数据(案例)
2. 编码2.1 设定业务方法：
2.2 设定线程类，模拟用户调用：
2.3 设计redis控制方案：
2.4 设计启动主程序:
3. Jedis 工具类配置如果每次使用redis 都通过创建一个连接然后关闭的方式来进行会导致效率非常低。因此往往采用 jedis连接池的方式进行操作。
3.1 配置文件12345678910111213141516171819202122# 最大可用连接数redis.maxTotal=1000# 最大空闲连接数redis.maxIdle=100# 最小空闲连接数redis.minIdle=50# 当池内没有返回对象时，最大等待时间redis.maxWaitMillis=10000# 当调用borrow Object方法时，是否进行有效性检查redis.testOnBo ...