多线程
概念 -> 使用 -> 同步 -> 锁 -> 线程池 -> 并发
多线程的本质是：多个任务“快速”的轮流进行。
进程：一个任务的基本单位，线程是CPU调度的基本单位。
特性区别：
进程
- 资源独立
- 开销大
- 稳定性高
- 通信慢
线程
- 资源共享，局部变量不共享。
- 开销小
- 稳定性差
使用线程的方法
- 创建线程
- 继承 Thread 类
- new 匿名内部类
- 传入 Runnable 接口
- start 方法开启线程
通过 join 方法还可以加入其他线程，其他线程需要等待该线程才能结束。
通过 interrupt 方法可以中断线程，但是这里仅是改变一个状态量，实际结束线程需通过 Thread 提供的方法 isInterrupted() 方法检测线程状态。
如果线程处于等待状态，interrupt 会抛异常，导致状态更改失败。
等待状态：
- 当前线程正在 sleep
- 当前线程正在等待其他 join 的线程
线程的状态分为 new -> running, waiting -> interrupted。
守护线程
“守护”其他所有线程的线程。
==只有所有线程结束，它才会停止（包括 Main JVM主线程）==
setDeamon(true) 即可将线程设置为守护线程。
同步问题
由于多线程是异步操作，如果同时对变量进行操作，会有状态竞争问题。
因此需要同步这些操作：一个一个操作。
通过 synchronized 关键字、原子操作、Atomic 类都可以做到同步操作。
协调问题
有时候一个线程可能和另一个线程相关，但又被限制为了同步操作，导致这个方法不能结束另一个方法又不能执行，这被称为死锁。
这时可以通过 wait() 方法使当前线程暂时休眠，等另一个线程执行完对应任务后通过 notifyAll() 来唤醒它，最后达成同步。
锁除了 synchronized 外，还有一个专门的包专门提供锁。
- ReentrantLock 可重入锁
- ReadWriteLock 读写锁
- StampedLock 读写锁的优化版
- Semaphore 信号量
除此之外，还有一些个专门的线程安全集合类
- CopyOnWriteArrayList
- ArrayBlockingQueue
- 等等
线程池
因为线程的创建需要资源和时间，频繁的创建和销毁会浪费大量的性能。
因此就可以创建线程池，存储创建过的线程，复用线程。
创建方式：
大多都是通过 Executors 的方法创建
- newFixedThreadPool
- newScheduledThreadPool
Schedule 表示定时操作
又分为
- schedule 定时
- scheduleAtFixedRate 以固定频率定时
- scheduleWithFixedDelay 以固定间隔定时
并发操作
普通的 Thread 创建子线程只能执行操作，而不能获取返回值。
因此 Future 就出场了，可以获得返回值。
但是其 get() 操作确实阻塞的。
这时候 CompletableFuture 又出现了，提供异步回调的方式。
同时还有多种方法实现“并行”和“串行”的并发操作，非常好用。
算法
轮转数组
通过分析轮转后数组中各元素的位置变化。
首先发现尾部的数组会变到数组的头部（首位翻转数组）
同时还保持着原有的顺序（切割数组，将数组各部分翻转回来）
最终实现了原地转了过去。
除自身以外数组的乘积
题目要求不能用除法
不然就是一个求积，然后除以当前元素得到结果了。【O(n), O(1)空间爽歪歪！】
常规思路就是除去当前位置，左右求积然后再积，O(n^2^)
略微思考可以发现左右求积的过程都是【无后效性】的，即一个状态是另一个状态的基础。
没错！！动态规划，提前求出每个状态的前后累乘积。
那么在遍历求结果时，只需要 O(1) 的时间就可以得到结果了，最终 O(n)。
缺失的第一个正数
给定一个数组，要求找出数组确实的第一个正整数
常规思路：建立哈希表（优化查找效率），然后从 1 开始遍历，第一个不存在的即为答案。
深度思考：
结果要么属于 [1, N]，要么就是 N+1。
因为数组只有两种情况，要么[1, N]刚好塞满，要么中间差了谁，被区间外的数占了。
不要专注于什么没有，而是要看什么已经有了。
同时，题目要求：必须使用 O(1) 的空间。
那建立哈希表不是泡汤了？
错！！既然结果属于 [1, N] 就让数组本身成为哈希表。
核心：通过遍历数组标记索引为 [0, N-1] 的位置，第一个没有被标记的位置 + 1 即为结果。
怎么标记不影响原数组呢？
设为负数
本身就是负数呢？
设为N+1，不干扰到索引范围内的数。
矩阵置零
要求使用额外常数空间 O(1)
只要某个位置存在 0，就将整行和整列变为 0。
摆脱固定思维：真的一行一列遍历赋值为0。。。O(n^3^)
O(M+N) ：分别建立行和列的数组，标记出现 0 的行或列，遍历整个矩阵，只要当前行或列存在 0，当前元素就赋值为 0，时间：O(n^2^)。
O(2)：从矩阵本身挑出第一行和第一列作为标记数组，并且设置 flagRow，flagCol 两个标记变量标记原第一行或列是否存在 0。
和上一题很像，以自身为空间
O(1)：省去 flagRow，用第一列的第一个元素代替标记。
在用第一行或列作为标记数组，并将存在 0 的行或列对应位置赋值为 0，并不影响原位置元素。
因为如果这一行或列存在 0 的话，它本身就应该变为 0。
旋转图像
n * n 矩阵顺时针旋转。
顺时针旋转 = （上下）左右翻转 + （负）正时针对角线交换
对角线交换公式（正方形）
X(i, j) => X(n-1-j, n-1-i) n为边长。
位置交换，并转化为长度的“找补”。
代码如下：
1 | for(int i = 0; i < n; i++) { |