- 博客(255)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 手写算法-LFU
这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法，最低访问数的条目首先被移除。这个方法并不经常使用，因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。
2022-08-21 11:49:35
207
1
原创 手写算法-FIFO
FIFO是英文First In First Out 的缩写，是一种先进先出的数据缓存器，他与普通存储器的区别是没有外部读写地址线，这样使用起来非常简单，但缺点就是只能顺序写入数据，顺序的读出数据，其数据地址由内部读写指针自动加1完成，不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。
2022-08-21 11:47:41
210
原创 手写数据结构-队列
队列的基本功能满足可扩容使用Optional返回数据栈的基本功能满足可扩容使用Optional返回数据enqueue入队时检查tail是否到达尾部，到达尾部则检查head的位置，如果head！=0则进行搬移数据。
2022-07-17 18:10:57
399
原创 Mybatis 不带$符号的分页代码实现
因为limit 后无法使用运算符，所以要借助mybatis 的bind 先进行计算<select id="selectForPage1" resultType="com.lagou.entity.Position"> <bind name="offsetSize" value="(num2-1)*num1"/> select * from position limit #{offsetSize},#{num1} </select>
2021-11-15 23:27:29
483
原创 java 特性总结
java 7switch中添加对String类型的支持数字字面量的改进 / 数值可加下划异常处理（捕获多个异常） try-with-resources增强泛型推断JSR203 NIO2.0（AIO）新IO的支持JSR292与InvokeDynamic指令Path接口、DirectoryStream、Files、WatchService（重要接口更新）fork/join framework推荐阅读更多内容Java 7的新特性java 8推荐阅读更多内容Java 8的新特性java
2021-11-13 22:07:00
157
原创 Optional的常用方法
static Optional ofNullable(T value)如果为非空，返回 Optional 描述的指定值，否则返回空的 Optional。Optional map(Function<? super T,? extends U> mapper)如果有值，则对其执行调用映射函数得到返回值。如果返回值不为 null，则创建包含映射返回值的Optional作为map方法返回值，否则返回空Optional。T orElse(T other)如果存在该值，返回值， 否则返回 ot.
2021-11-13 17:27:33
201
原创 三元表达式自动拆箱
问题描述boolean flag = false;Integer a = null;Integer n = flag ? 1 : a;在计算三元表达式结果时，a变量自动拆箱了，因为a=null，所以造成了NPE问题。问题解决在三元表达式计算中，当第二、第三位操作数中有基本类型和对象时，对象就会拆箱为基本类型进行操作。所以如果使用了基本类型或者隐式的使用了基本类型，需要考虑NPE问题。...
2021-11-13 17:21:13
377
原创 Seat 学习
一、Seata 简介Seata（Simple Extensible Autonomous Transaction Architecture）是一套一站式分布式事务解决方案，是阿里集团和蚂蚁金服联合打造的分布式事务框架。发展史二、 特色功能微服务框架支持⽬前已支持 Dubbo、Spring Cloud、Sofa-RPC、Motan 和 grpc 等RPC框架，其他框架持续集成中AT 模式提供无侵入自动补偿的事务模式，目前已支持 MySQL、 Oracle 、PostgreSQL和 TiDB的
2021-11-13 16:12:21
2272
原创 分布式事务学习
一、分布式事务理论CAP（强一致性）CAP 定理，又被叫作布鲁尔定理。对于共享数据系统，最多只能同时拥有CAP其中的两个，任意两个都有其适应的场景。BASE（最终一致性）BASE 是指基本可用（Basically Available）、软状态（ Soft State）、最终一致性（ Eventual Consistency）。它的核心思想是即使无法做到强一致性（CAP 就是强一致性），但应用可以采用适合的方式达到最终一致性。BA指的是基本业务可用性，支持分区失败，允许损失部分可用性，延迟或者降
2021-11-08 18:19:59
131
原创 DDD 落地学习
领域设计领域驱动设计通常适用于增删改的业务操作，但不适用于分析统计。在一个系统中，增删改的业务可以采用领域驱动的设计，但在非增删改的分析汇总场景中，则不必采用领域驱动的设计，直接 SQL 查询就好了，也就不必再遵循聚合的约束了。为了让微服务设计做到高内聚，最佳的实践则是 DDD：先从 DDD 开始需求分析、领域建模，逐渐建立起多个问题子域；再将问题子域落实到限界上下文，它们之间的关联形成上下文地图；最后，各子域落实到微服务中贫血模型或充血模型的设计，从而在微服务之间依据上下文地图形成接口。软
2021-11-05 21:50:40
334
原创 DDD 学习
一、DDD 简介领域驱动设计（Domain Driven Design，简称 DDD）。DDD 核心思想是通过领域驱动设计方法定义领域模型，从而确定业务和应用边界，保证业务模型与代码模型的一致性。DDD 是一种处理高度复杂领域的设计思想，它试图分离技术实现的复杂性，并围绕业务概念构建领域模型来控制业务的复杂性，以解决软件难以理解，难以演进的问题。DDD 不是架构，而是一种架构设计方法论，它通过边界划分将复杂业务领域简单化，帮我们设计出清晰的领域和应用边界，可以很容易地实现架构演进。二、DDD 设计D
2021-11-05 13:10:40
182
原创 B树与B+树
一、B树1.1 简介一个n叉树数据结构，每个节点通常有多个孩子。1.2 特点m阶的B树具有如下特征根结点要么没有子女要么至少有两个子女每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m每一个叶子节点都包含k-1个元素，其中m/2 <= k <= m所有的叶子结点都位于同一层节点中的元素从小到大排列，节点中k-1个元素正好是k个孩子包含的元素的值域分划二、B+树2.1 简介B树的一个升级版，充分利用节点空间，查询速度接近于二分查找。
2021-09-15 00:28:44
85
原创 红黑树学习
一、红黑树简介1972年Rudolf Bayer发明，称为平衡二叉B树（symmetric binary B-trees），在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为“红黑树”，一种特化的AVL树，在插入和删除时通过特定操作保持二叉查找树的相对平衡，从而获得较高的查找性能。红黑树不是严格的AVL树，只是黑色平衡，如上图所示，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的。二、红黑树特点符合二叉搜索树基本特性，同时具备以下特性：
2021-09-14 14:36:40
323
1
原创 滑动窗口 Sliding window
一、滑动窗口简介像窗口一样滑动，窗口内大部分元素不变。滑动窗口的应用： 网络限流，令牌桶算法。二、滑动窗口特点用以解决数组/字符串的子元素问题，查找满足一定条件的连续区间的问题，例如“请找到满足xx的最x的区间（子串、子数组）的xx。可以将嵌套的循环问题转换为单循环问题，当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，从而减少重复计算，降低了时间复杂度。三、示例题目3.1 固定长度窗口给定一个整数数组，计算长度为 k 的连续子数组的最大总和。暴力解法：从头开始计算相邻k个总和
2021-09-14 11:38:48
343
原创 树映射 TreeMap常用方法总结
lowerKey(key1)： 小于key1的最大的键值对所对应的KEYhigherKey(key1)：大于key1的最小的键值对所对应的KEYfloorKey (key1)： 小于等于key1的最大的键值对所对应的KEYceilingKey(key1)：大于等于key1的最小的键值对所对应的KEYlowerEntry()、higherEntry()ceilingEntry()、floorEntry()...
2021-09-14 11:22:17
248
原创 单调栈学习
一、单调栈简介一类具备单调性（顺序）的特殊栈普通栈，对入栈的数据没有顺序要求，单调栈要求栈中的数据是有序的。、二、递增栈与递减栈单调递增栈：栈中数据出栈的序列为单调递增序列单调递减栈：栈中数据出栈的序列为单调递减序列三、代码实现Stack<Integer> stack=new Stack<>();for (int value:array) { if (stack.isEmpty() ||stack.peek()>=value){ //栈为空或 栈顶元
2021-09-14 11:20:42
80
原创 位图BitMap
一、位图简介用二进制的每一位来压缩存放很多数据的状态，通常用于判断某个数据是否存在。如果某个数字存在就在对应位置置为1，比如标识0、8、22三个数字存在。位图的大小取决于要存放的数据范围，数据到下标的对应关系需自行设计，超过32位可分段存储。二、位图常见操作2.1 采用位运算快速将某个位置置为1采用按位或int bitMap;public void setBit(int pos) { int bit = 1 << pos; bitMap |= bit;}采用按位异或调
2021-09-14 11:03:56
277
原创 动态规划：监控二叉树
一、题目描述给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。二、理解题意在本题中，每个节点可以监视父节点、自身以及子节点要求在所有节点都被监视到时候所需最小的摄像头的数目摄像头放到非叶子节点上监视的范围最大(父节点+左右子节点)任意一个节点是否放置摄像头取决于其父节点+左子节点+右子节点的状态三、解法一：暴力搜索从上往下，依次搜索所有可能性，取最小interval=2， 则当
2021-09-14 10:09:37
110
原创 动态规划学习
一、动态规划学习动态规划来源于运筹学，是求解决策过程最优化的一种数学方法。在20世纪50年代初美国数学家R. E.Bellman等提出的最优化原理，动态规划的核心思想是利用各阶段之间的关系，逐个求解，最终得到全局最优解。设计一个动态规划算法的关键点是确认原问题与子问题、动态规划的状态、边界状态值和状态转移方程等。二、动态规划解题步骤想清楚原问题与子问题设计状态设计状态转移方程确定边界状态值三、动态规划示例-爬楼梯3.1 题目描述在爬楼梯的时候，每次可以往上爬1阶台阶或2阶台阶，问n
2021-09-13 22:34:23
353
原创 位运算学习
一、位运算符二、常见的位运算问题2.1 异或特点n^n=0 n^0=n数组中每个数字都出现了两次，只有一个出现了一次，找到出现一次的数字（leetcode 136）根据异或特点n^n=0 n^0=n，异或到最后只剩下0^npublic static int singleNumber(int[] nums) { int num = 0; for (int i = 0; i < nums.length; i++) { num = num ^ nums[i]; } re
2021-09-13 21:31:24
79
原创 回溯的理解
递归是一种算法结构，而回溯是一种算法思想，可以用递归实现。回溯就是一种试探，类似于穷举，但回溯有“剪枝”功能。如在求和问题。给定7个数字，1 2 3 4 5 6 7求和等于7的组合。从小到大搜索，选择1+2+3+4 =10>7，则5 6 7就没必要再继续了，这就是剪枝。从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到“尽头”的时候, 再倒回出发点, 从另一个可能出发, 继续搜索。这就是回溯。...
2021-09-13 17:32:17
1731
原创 最小生成树+并查集： 找到最小生成树的关键边和伪关键边
一、题目描述找到最小生成树里的关键边和伪关键边。给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪
2021-09-13 15:00:09
167
原创 生成树和最小生成树
一、生成树和最小生成树简介生成树（Spanning Tree）：在无向连通图中，生成树是将图中所有顶点以 最少的边 连通的子图。• 图必须是无向连通图，非连通图和有向图都没有生成树的概念• 生成树是一个连通子图，是给定图的一个子集，它连接了所有节点且没有环• 生成树不止一种，生成树含有图中全部n个顶点，以及包含图中n-1条边最小生成树（Minimum Spanning Tree，MST ）：生成树中，边的权值和最小，是“最小权重生成树”的简称。二、关键边和伪关键边关键边：如果从图中删去某条边，
2021-09-13 14:24:01
2536
原创 并查集学习
一、并查集简介并查集，处理一些不相交集合（Disjoint Sets）的合并及查询问题。常用于判断无向图中连通分量的个数和任意两个顶点是否连通。二、并查集操作初始化：把每个元素所在集合初始化为其自身合并（Union）：把两个不相交的集合合并成一个集合，通常，合并之前会检查两个元素是否属于同一个集合。查询（Find）：查询元素所在的集合（代表节点/代表元），也可以用于判断两个元素是否属于同一个集合。路径压缩(find)：查找时，使节点x到root之间的所有节点都指向root。
2021-09-13 12:56:03
92
原创 并查集+深度优先：岛屿数量
一、题目描述岛屿数量。给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。二、理解题意三、数据结构及算法思维选择四、解法一：广度优先搜索public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) return 0; int gridLe
2021-09-13 12:28:13
147
原创 拓扑排序学习
一、拓扑排序思想在计算机科学领域，有向图的拓扑排序是对其顶点的一种线性排序，使得对于图中的每个有向边 uv，u 在排序中都在v之前。拓扑排序是对一个有向图的顶点进行排序。它关心的是图中各个顶点的连接关系，这种连接关系也叫拓扑关系，因为它不关心各个顶点的位置与距离。例如，图的顶点可以表示要执行的任务，边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。对于下面的有向图，我们可以进行拓扑排序得到
2021-09-13 11:37:00
301
原创 矩阵中的最长递增路径
一、题目描述给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。二、理解题意问题建模将矩阵中每个元素当成一个节点，连接上下左右相邻的元素，我们可以得到一个图由于题目要求寻找最长递增路径，我们可以只保留从小元素指向大元素的有向边那么该问题也就变成了寻找有向图中的最长路径由于该图中的邻接关系是固定的，我们并不用显式构建邻接表或邻接矩阵，直接使用该矩阵即可三、解法一：深度优先遍历法p
2021-09-13 10:49:09
669
原创 图中最短路径：网络延迟时间
一、题目描述有 N 个网络节点，标记为 1 到 N。给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。二、理解题意• 我们需要找到从给定节点k发出的信号多久后可以到达所有节点。• 每条边都被赋予了长度（边权），即信号在该边传输所用的时间。• 观察：从
2021-09-12 23:57:47
286
原创 迪杰斯特拉算法
一、迪杰斯特拉算法简介• 迪杰斯特拉算法，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。• 迪杰斯特拉算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。二、迪杰斯特拉算法主要思想定义一个节点集合D表示从源点k出发已经确定最短路径的前n近的节点比
2021-09-12 23:41:57
587
原创 图：节点间通路
一、题目描述节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。二、理解题意给定一些节点，某些节点间存在单向通路需要查找是否存在从节点a到节点b的通路例如图中存在0→1, 0→3, 0→2, 1→3的通路不存在3→1, 3→2, 3→0的通路额外信息• 节点数量n在[0, 100000]，节点编号大于0小于n• 可能存在自环和平行边三、解法一：广度优先遍历public boolean findWhetherExistsPath(int n, int[][
2021-09-12 23:13:26
553
原创 数据结构—图
一、图的简介• 在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。• 顶点有时也被称为节点或者交点，边有时也称为链接。• 边可以是单向的，也可以是双向的。二、图的分类无向图：无向图是由顶点和边构成。有向图：有向图是由顶点和有向边构成。完全图：如果任意两个顶点之间都存在边叫完全图，有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。三、图的表示3.1 邻接矩阵• 使用一个n×n的布尔值矩阵
2021-09-12 22:55:30
58
原创 树状数组学习
一、什么是树状数组？二、树状数组的两个基本操作三、代码实现/** * * <p>树状数组或二叉索引树（英语：Binary Indexed Tree），以其发明者命名为Fenwick树。 * 其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题， * 现多用于高效计算数列的前缀和， 区间和。</p> * * <p>虽然BIT的名字是“二叉索引树”，实际上我们并没有使用一个“树”的结构去存储BIT对象， * 而是将其放
2021-09-12 22:40:36
71
原创 线段树学习
一、简介线段树是一种平衡二叉搜索树(完全二叉树)，它将一个线段区间划分成一些单元区间。对于线段树中的每一个非叶子节点，表示区间[a, b]的和，它的左孩子表示的区间为[a,(a+b)/2]，右孩子表示的区间为[(a+b)/2+1,b]，最后的叶子节点数目为N，与数组下标对应。线段树一般包括建立、查询、插入、更新等操作，建立规模为N的时间复杂度是 O(NlogN)，其他操作时间复杂度为O(logN) 。二、结构由于线段树是完全二叉树，线段树可以使用数组保存，对二叉树进行层次遍历。假设某个节点下标为i，
2021-09-12 16:34:51
131
原创 PriorityQueue学习
一、简介PriorityQueue是一个基于优先级的无界队列，Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。Java中PriorityQueue默认是最小堆，可以通过传入Comparator实现最大堆。二、使用//小顶堆，默认容量为11PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();//大顶堆，容量11PriorityQueue<Integer>
2021-09-12 16:03:06
83
原创 字典树学习
一、字典树介绍又叫做trie树或前缀树。是一种有序的、用于统计、排序和存储字符串的数据结构。关键字不直接保存在结点中，而是由结点在树中的位置决定，每个结点代表一个字符。根结点代表空字符串，第一层孩子结点到某个标记的结点代表了存储的字符串。一个结点及其所有子孙结点都有相同的前缀，也就是这个结点对应的字符串。只有叶子结点和某些被标记的内部结点，才存储了字符串。字典树最大优点是利用字符串的公共前缀来减少存储空间和查询时间，从而最大限度的减少无谓的字符串比较，是非常高效的字符串查找结构，插入和查找的时
2021-09-12 15:01:25
71
原创 二叉搜索子树的最大键值和
一、题目描述给出一棵root为根的二叉树，请你返回任意二叉搜索子树的最大键值和二、理解题意如何判断一棵子树是否是二叉搜索树？如何记录一棵子树的键值和？如何得到最大键值和？三、Choose 数据结构及算法思维选择四、后序遍历解法理解本题关键点在于判断一棵子树是否是BST• BST = 左子树是BST + 右子树是BST + 左子树最大值 < 根结点值 + 右子树最小值 >= 根结点值解法递归三要素确定函数等价关系式（参数，返回值）• 参数是根节点+目标值，返回值
2021-09-12 12:00:11
192
原创 二叉搜索树学习
一、简介如果左子树不为空，则左子树所有结点值都小于根结点的值。如果右子树不为空，则右子树所有结点值都大于或等于根结点的值。任意一棵子树也是一棵二叉搜索树。二、特点当你需要完成的功能是插入、删除、检索时，二叉搜索树具有极佳的性能二叉搜索树在排序、检索、数据库管理系统及人工智能等方面广泛应用二叉搜索树的中序遍历序列是一个递增的序列三、二叉搜索树的建立给定一个序列，对序列的每一个元素插入到二叉搜索树：如果二叉搜索树为空，则该元素即为根结点如二叉搜索树为非空，如该元素值小于根结点值，插
2021-09-12 11:29:59
92
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人