gca的博客

数组&排序88、合并两个有序数组 12345+ 双指针 + 倒排 + while循环（条件：下面退出） + 上指针未结束，且大于下指针 + 上指针结束（提前走完）或者小于下面指针+ 其他方法 75、颜色分类 1234567891011121314+ 对数组排序（只包含0、1、2），原地排序（常数空间），一趟扫描+ sort ×+ 排序算法 ×+ 双、三指针（扫描一趟常用解法） + 左边两个指针（放0、遍历扫描），右边一个指针（放2），判断左边元素 + 遍历（条件：扫描退出） + 扫描到1跳过 + 扫描移动 + 扫描到0与左指针交换 + 左指针移动 + 扫描移动（交换来的值已经被扫描过，无需判断） + 扫描到2与右指针交换 + 右指针移动 + 扫描再次判断（交换来的值未被判断过） 16、部分排序 1234567891011121314+ 找到中间未排序的区间（两边已排序） ...

跳表思考有序链表搜索、添加、删除 时间复杂度较高 二分搜索无法应用 需要搜索、添加、删除快速的数据结构！！ 跳表相比较于红黑树 实现、维护更加简单 跳表：增加多层快速路线 一个node有多层 每层每层都有一个指针 最下层指向下一个节点 实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916 ...

并查集需求分析设计一个数据结构，能够快速执行2个操作 1、查询 2、连接 数组、链表、平衡二叉树、集合（Set）？ 查询、连接的时间复杂度都是：O(n) 并查集并查集也叫作不相交集合（Disjoint Set） 并查集有2个核心操作 查找（Find）：查找元素所在的集合（这里的集合并不是特指Set这种数据结构，是指广义的数据集合） 合并（Union）：将两个元素所在的集合合并为一个集合 有2种常见的实现思路： Quick Find 查找（Find）的时间复杂度：O(1) 合并（Union）的时间复杂度：O(n) Quick Union 查找（Find）的时间复杂度：O(logn)，可以优化至 O （𝛼 （𝑛）） ，α(𝑛) < 5 合并（Union）的时间复杂度：O(logn)，可以优化至 O （𝛼 （n）） ，α(𝑛) < 5 如何存储数据： 可以用数组实现的树形结构 Quick find 连接节点 树的高度最多是2 查找节点 实现： 12345678910111213141516+ 准备 + 父节点数组 ...

ReentrantReadWriteLock原理t1 w.lock t2 r.lock 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859+ 读写锁原理 + 使用的同一个sycn同步器 + t1 w.lock 写锁 + 与可重入锁基本相同 + state低16位写锁，高16位读锁 + tryacquire + 这段看书没懂，现在终于懂了 + 判断有无：读锁、写锁（非本线程） + t2 r.lock + 读源码最好的办法是写个小栗子然后通过idea调试阅读，直接读太慢，还容易理解错了 + 判断有无写锁、当前线程的写锁 + 阻塞，和独占锁差不多 + 只是节点类型不同：node类型为shared + 判断是否为老二 ...

自定义线程池结构 阻塞队列12345678910// 1. 任务队列private Deque<T> queue = new ArrayDeque<>();// 2. 锁private ReentrantLock lock = new ReentrantLock();// 3. 生产者条件变量private Condition fullWaitSet = lock.newCondition();// 4. 消费者条件变量private Condition emptyWaitSet = lock.newCondition();// 5. 容量private int capcity; 123456789101112131415161718192021+ blocking queue + 任务队列-双向链表 + 可重入锁 + 生产者条件变量 + 队列容量限制 + 消费者条件变量 + 队列空限制 + 容量上限 + 阻塞获取 + 上锁 + ...

共享模型之无锁123456789+ 问题提出 + 保护共享资源 + 加锁实现 + synchronize、reentrantlock + 无锁实现 + AtomicInteger：原子整数 + int封装 + compareAndSet(prev,next) + 修改成功为true CAS与volatilecas 123456789101112131415161718192021+ cas与volatile + 工作方式 + cas原子 + CAS就是JAVA里唯一的乐观锁了... + 保证了CAS原子性 + 慢动作分析 + volatile + 保证了变量的可见性 + 保证获取新值比较 + 效率分析 + 无锁始终运行，有锁会上下文切换 + runnable——>blocked ...

共享模型之内存Java内存模型-JMMJMM 即 Java Memory Model，它定义了主存、工作内存抽象概念，底层对应着 CPU 寄存器、缓存、硬件内存、CPU 指令优化等。 JMM 体现在以下几个方面 原子性 - 保证指令不会受到线程上下文切换的影响 可见性 - 保证指令不会受 cpu 缓存的影响 有序性 - 保证指令不会受 cpu 指令并行优化的影响 可见性 可见性 一个线程对主存数据修改，对于另外一个线程不可见 问题 初始状态，t线程从主存读取run到工作内存 因为t要频繁从主内存读取run JIT编译器将run的值存储在工作内存中，减少对主存run的访问 CPU高速缓存 主线程修改run的值，同步到主存 t一直从高速缓存中读 解决 加上volatile修饰：易变 只能修饰成员、静态成员变量 必须从主存获取值 加上synchronize解决 在Java内存模型中，synchronized规定，线程在加锁时， 先清空工作内存→在主内存中拷贝最新变量的副本到工作内存 →执行完代码→将更改后的共享变量的值刷新到主内存中→释放互斥锁。 ...

共享模型之管程共享带来的问题上下文切换问题 123456789101112131415161718192021222324252627282930313233343536373839404142434445+ 共享带来的问题+ 上下文切换分析 + 单线程 + 多线程情况 + 线程的 cpu 时间片用完 -> 线程挂起，运行到就绪 -> 线程上下文切换 -> 字节码指令交错运行 -> 共享变量counter读写冲突 + 根源：指令交错+ 临界区与竞态条件 + 临界区 + 存在对共享资源的多线程读写区域 + 竞态条件 + 结果无法预测+ 避免竞态条件 + 非阻塞式 + 原子变量 + 阻塞式 + synchronize、lock+ synchronize + 对象锁 + 临界区代码变成串行 + 对象，多个线程共享 + 理解 + 比喻 + synchronize中即使时间片用完，下次 ...

进程与线程进程与线程123456789101112131415+ 进程 + 加载指令、管理内存、管理io + 程序的一个实例 + java中资源分配的最小单位+ 线程 + 一个指令流 + 一个进程内多个线程 + java中最小调度单位+ 对比 + 进程基本相互独立，线程存在于进程中 + 进程通信复杂 + 不同计算机进程通信，http协议等 + 线程通信简单 + 共享进程内的内存，数据 + 线程上下文切换成本低 并行并发的概念并发 并行 123456789101112131415并发： 同一时间段，多个任务都在执行 (单位时间内不一定同时执行)并行： 单位时间内，多个任务同时执行+ 并发 + 同一时间线程轮流使用cpu + concurrent + 单核cpu下 + 实际串行执行 + cpu时间片轮流执行 + 宏观上并行+ 并行 + 多核cpu下 + 每个核同时调度运行线程+ 并发和并行都有 + 并发： ...

Docker 容器化相比虚拟化 同一标准 应用无论什么语言同一构建成镜像 镜像分享仓库 容器化时代 虚拟化技术 容器化技术 资源隔离 资源隔离 访问设备隔离 网络隔离 用户隔离 docker架构 操作 镜像操作 docker hub仓库 容器操作 外部操作 内部操作 看镜像仓库官网 打包镜像变化 docker commit 镜像保存 docker save 保存为压缩包文件 镜像加载 docker load 读取压缩包为镜像 镜像推送 login：登录仓库 tag：改名，带上自己的仓库名 push：推送镜像 挂载 保证外部有配置文件 提前cp出来文件 其他命令 docker logs 容器 容器日志 docker cp 容器复制到本地 本地复制到容器 构建应用 以前 springboot打包 jar包上传服务器（环境） 运行jar包 现在 打包镜像，启动即用 编写docker file（如何打包） from：基础镜像 运行环境 label：作者 ...