-
AQS
概述AQS(AbstractQueuedSynchronizer)字面意思:抽象队列同步器AQS 是用来实现锁或者其他同步器组件的公共基础部分的抽象实现。是重量级基础框架及整个 JUC 体系的基石,主要用于解决锁分配给 “谁” 的问题加锁会导致阻塞,有阻塞就需要排队,实现排队必然需要队列。AQS 由一个抽象 FIFO 队列 + int 类变量组成 CLH 双端队列:完成资源获取线程的排队工作。头部出队,尾部入队。 int 类变量:表示持有锁的状态:0 表示资源空闲,1 表示资源被占用。...…
-
JMM Java 内存模型
背景JMM 用于屏蔽掉各种硬件和操作系统的内存访问差异,以实现让 Java 程序在各种平台下都能达到一致的并发效果,JMM 规范了 Java 虚拟机与计算机内存是如何协同工作的:规定了一个线程如何和何时可以看到由其他线程修改过后的共享变量的值,以及在必须时如何同步的访问共享变量。JMM(Java Memory Model)本身是一种抽象的概念,并不是真实存在它仅仅描述的是一组约定和规范。通过这组规范定义了程序中(尤其是多线程)各个变量的读写访问方式并决定一个线程对共享变量的写入何时以及如何...…
-
Java 堆
概述 一个 JVM 实例中只存在一个堆内存,是 Java 内存管理的核心区域。在 JVM 启动时创建堆。 《Java 虚拟机规范》规定,堆可以处于物理上不连续的内存空间中,但是在逻辑上它应该被视为连续的。 所有的线程共享 Java 堆,在这里还可以划分线程私有的缓冲区(Thread Local Allocation Buffer,TLAB) 几乎所有的对象实例以及数组都应当在运行时分配在堆上,所以在栈帧上只保存对象实例和数组的引用。 在方法结束后,堆中的对象不会马上被移除,仅仅在...…
-
GC
GC 分类与性能指标GC 分类按**线程数(垃圾回收的线程)**分 串行垃圾回收器:在同一段时间内只允许一个 CPU 用于执行垃圾回收操作,此时工作线程被暂停,直至垃圾收集工作结束 使用场景:单 CPU 处理器或者较小的应用内存等硬件平台不是特别优越的场合,串行回收器的性能表现可以超过并行回收器和并发回收器。串行回收默认被应用在客户端的 Client 模式下的 JVM 中 在并发能力较强的 CPU 上,并行回收器产生的停顿时间要短于串行回收器。 ...…
-
GC 算法
垃圾回收主要在:堆区和方法区标记阶段:引用计数算法在堆里存放着几乎所有的 Java 对象实例,在 GC 执行垃圾回收之前,首先需要区分出内存中哪些是存活对象,哪些是已经死亡的对象。只有被标记为已经死亡的对象, GC 才会所占在执行垃圾回收时,释放掉其所占用的内存空间,因此这个过程我们可以称为垃圾标记阶段。当一个对象已经不再被任何的存活对象继续引用时,就可以宣判为已经死亡。判断对象存活一般有两种方式:**引用计数算法** 和**可达性分析算法**引用计数算法(Reference Counti...…
-
MVCC
概述MVCC是什么?MVCC 是为了解决事务操作中多线程并发安全问题的无锁并发控制技术。它的全称为:多版本并发控制。为什么需要MVCC?我们可以根据数据库三种并发场景来分析: 读读并发,不会产生并发问题,也不需要并发控制。 读写并发,会造成事务隔离问题,造成脏读、幻读、不可重复读的问题。 写写并发,可能出现数据更新丢失的问题。MVCC 为每个修改保存一个版本,版本与事务时间戳关联,读操作只读事务开始前的数据库的快照。它是通过 Undo 日志和ReadView 来实现的。MVCC 为数...…
-
Raft 算法
[TOC]Raft 选举的用途Raft 算法是分布式系统开发首选的共识算法。主要在分布式集群架构下进行领导者(主节点)选举。比如现在流行的组件:Etcd、Consul、Nacos、RocketMQ、Redis Sentinel 底层都是采用 Raft 算法来选举集群中的主节点,再通过主节点向其他节点下达指令。如果掌握了这个算法,就可以比较容易地处理绝大部分场景的容错和一致性需求。比如分布式配置系统、分布式 NoSQL 存储等等,轻松突破系统的单机限制。Raft 算法是通过一切以领导者为准的...…
-
调整搜索二叉树中两个错误的节点
一棵二叉树原本是搜索二叉树,但是其中有两个节点调换了位置,使得这棵二叉树不再是搜索二叉树,请找到这两个错误节点并返回。 已知二叉树中所有节点的值都不一样,给定二叉树的头节点 head,返回一个长度为 2 的二叉树节点类型数组 errs,errs[0] 表示一个错误节点,errs[1] 表示另一个错误节点。解法一:递归如下图对搜索二叉树进行中序遍历,可以得到一个升序数组。如果搜索二叉树中有两个节点调换为了位置,那么得到的数组,升序一定被破坏了。如下图:如果节点 2 与节点 4 调换了位...…
-
LFU 缓存
一个缓存结构需要实现如下功能: void set(int key,int value):加入或者修改 key 对应的 value int get(int key):查询 key 对应的 value 值 但是缓存最多放 K 条记录,如果新的 K + 1 条记录需要加入,就需要根据策略删掉一条记录,然后才能把新记录加入。 这个策略为:在缓存结构的 K 条记录中,哪一个 key 从进入缓存结构的时刻开始,被调用 set 或者 get 次数最少,就删掉这个key 的记录;如果调用次数最...…
-
矩形重叠个数
平面内有 n 个矩形,第 i 个矩形的左下角坐标为(x1[i],y1[i]),右上角坐标为:(x2[i],y2[i])。如果两个或多个矩形有公共区域,则认为他们是相互重叠的(不考虑边界和角落)。请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠?分析:**二维的图像题一般可以转化为一维的图像题****任何一个重合区域的底,一定是某一个矩形的底。**对矩形底边排序,先出处理下方的矩形,依次向上处理。在处理线段重叠问题时使用了有序表,此时我们假设有一个容器。将的底...…
-
线段重叠个数
一条直线上有 n 个线段,第 i 个线段的坐标为(x1[i],x2[i])。请你计算出直线上重叠线段数量最多的地方,有多少个线段相互重叠?分析:首先需要根据线段的起始点排序,便于后续处理。线段重叠问题需要根据当前线段的 start 和 end 排除哪些没有重合的线段。我们可以将线段的 end ,放入一个有序表里,将有序表中小于 start 的数据都删除(那些已加入有序表线段的 end 小于当前线段的 start,肯定与当前线段不重叠)。有序表中所有end 个数就是线段相互重叠数...…
-
环形加油站
N 个加油站组成一个环形,给定两个长度都是 N 的非负数组 oil 和 dis(N > 1),oil[i] 表示第 i 个加油站存的油可以跑多少千米,dis[i] 代表第 i 个加油站到环中下一个加油站相隔多少千米。 假设你有一辆邮箱足够大的车,初始时车里没有油。如果车从第 i 个加油站出发,最终可以回到这个加油站,那么第 i 个加油站就算良好出发点,否则就不算。请返回长度为 N 的 boolean 数组 res,res[i] 代表第 i 个加油站是不是良好出发点。解法一:暴力...…
-
正数分裂
给定一个正数 1,裂开的方法有一种:(1) 给定一个正数 2,裂开的方法有一种:(1,1),(2) 给定一个正数 3,裂开的方法有一种:(1,1,1),(1,2),(3) 给定一个正数 4,裂开的方法有一种:(1,1,1,1),(1,1,2),(1,3),(2,2),(4) 给定一个正数 n,求裂开的方法数。亮点:斜率优化方案一:暴力递归f ( pre, rest ) pre 只之前裂开的数 rest 是本次要裂开的数。rest 要大于 pre。 返回结果:裂开的方法数最...…
-
包含所有字符的最小子串长度
给定字符串 str1 和 str2 ,求 str1 的子串中含有 str2 所有字符的最小子串长度。 【举例】 str1 = “abcde” ,str2 = “ac“ 因为 ”abc“ 包含 str2 所有的字符,并且在满足这一条件的 str1 的所有子串中,”abc“ 是最短的,返回 3. str1 = “12345” ,str2 = “344“,最小包含子串不存在,返回 0。分析:使用 left 和 right 维护一个滑动窗口。 right 移动的时机:窗口没有...…
-
需要排序的最短子数组长度
给定一个无序数组 arr,求出需要排序的最短子数组长度。 【例如】arr=【1,5,3,4,2,6,7】返回 4,因为只有【5,3,4,2】需要排序。分析:子数组一定是连续的,所以整个数组可以分为三部分,只有中间一部分是乱序的。我们需要找到乱序部分的起始位置和终止位置。首先我们分析一下这三部分的特征:因为有序1 和有序3 不需要排序,那么有序1排序后一定在最前边一段(数据最小的一段),同理有序3排在最后一段(数据最大的一段):有序1 < 乱序2 < 有序3那么: 有序1...…
-
旋变字符串
一个字符串可以分解成多种二叉树结构。如果 str 长度为 1 ,认为不可分解。如果 str 长度为 N(N > 1),左部分长度可 以为 1 ~ N - 1,剩下的为右部分的长度。左部分和右部分都可以按照同样的逻辑,继续分解。形成的所有结构都是 str 的二叉树结构。 比如,字符串“abcd”,可以分解成一下五种结构: 任何一个str的二叉树结构中,如果两个节点有共同的父节点,那么这两个节点可以交换位 置,这两个节点叫作一个交换组。一个结构会有很多交换组,每个交换组都可...…
-
汉诺塔
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。汉诺塔问题分三步: 将 0 ~ n -1 号圆盘从 from 柱子移动到 other 柱子。 将 n 号圆盘从 from 柱子移动到 to 柱子。 将 0 ~ n - 1 号圆盘从 othe...…
-
子数组最大异或和
数组异或和的定义:把数组中所有数异或起来得到的值。 给定一个整型数组:arr,其中可能有正、有负、有零,求其子数组的最大异或和 【举例】 arr = 【3】 数组中只有 1 个数,所以只有一个子数组,就是这个数组本身,最大异或和为 3 arr = 【3,-28,-29,2】 子数组有很多,但是【-28,-29】这个子数组的异或和为 7,是所有子数组中最大的。分析:异或和没有单调性。两个小的数的异或和可能比两个大数的异或和大。解法一:暴力算法对每一个以 i 为开始和以 j 为...…
-
打爆气球
给定一个数组 arr,代表一排有分数的气球。每打爆一个气球都能获得分数,假设打爆气球的分数为 X,获得分数的规则如下: 如果被打爆气球的左边有没打爆的气球,找到离被打爆气球最近的气球,假设分数为 L;如果被打爆气球的右边有没有打爆的气球,找到离被打爆气球最近的气球,假设分数为 R。获得分数为 L * X * R 如果被打爆气球的左边有没打爆的气球,找到离被打爆气球最近的气球,假设分数为 L;如果被打爆气球的右边所有气球都已经被打爆。获得分数为:L*X 如果被打爆气...…
-
最大宽度坡
给定一个整数数组 A,坡是元组 (i, j),其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。 找出 A 中的坡的最大宽度,如果不存在,返回 0 。示例 1:输入:[6,0,8,2,1,5]输出:4解释:最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.示例 2:输入:[9,8,1,0,1,9,4,0,4,1]输出:7解释:最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9...…