- 博客(44)
- 收藏
- 关注
RSS订阅原创 docker-compose服务编排(mysql、redis、mongo、nacos、rabbitmq、kafka、fastdfs、minio、es、seata、yapi、jenkins)
docker-compose服务编排(mysql、redis、mongo、nacos、rabbitmq、kafka、fastdfs、minio、es、seata、yapi、jenkins)
2023-01-13 22:54:10
1036
原创 最短路径(加权有向图)
最短路径1. 最短路径定义以及性质定义：在一副加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。性质：路径具有方向性。权重不一定等于距离。权重可以是距离、时间、花费等内容，权重最小指的是成本最低。只考虑连通图。一副图中并不是所有的顶点都是可达的，如果s和t不可达，那么它们之间也就不存在最短路径，所以只考虑连通图。最短路径不一定是唯一的。从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条，所以只需要找出一条即可。最短路径树：给定一副加权
2021-08-28 17:00:29
4331
原创 加权有向图
加权有向图加权无向图中，边是没有方向的，并且同一条边会同时出现在该边的两个顶点的邻接表中，为了能够处理含有方向性的图的问题，我们需要实现以下加权有向图。1. 加权有向图边的表示API设计：类名DirectedEdge构造方法DirectedEdge(int v,int w,double weight)：通过顶点v和w，以及权重weight值构造一个边对象成员方法1.public double weight():获取边的权重值2.public int from():获取有
2021-08-28 10:30:46
726
原创 Prim算法实现、最小生成树(加权无向图)
最小生成树加权图，我们发现它的边关联了一个权重，那么我们就可以根据这个权重解决最小成本问题，但如何才能找到最小成本对应的顶点和边呢？最小生成树相关算法可以解决。1. 最小生成树定义以及相关约定定义：图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树约定：只考虑连通图。最小生成树的定义说明它只能存在于连通图中，如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为最小生成森林。所有边的权重都各不相同。
2021-08-27 23:24:14
2347
原创 加权无向图
加权无向图加权无向图是一种为每条边关联一个权重值或是成本的图模型。这种图能够自然地表示许多应用。在一副航空图中，边表示航线，权值则可以表示距离或是费用。在一副电路图中，边表示导线，权值则可能表示导线的长度即成本，或是信号通过这条先所需的时间。此时我们很容易就能想到，最小成本的问题，例如，从西安飞纽约，怎样飞才能使时间成本最低或者是金钱成本最低？在下图中，从顶点0到顶点4有三条路径，分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过那条路径到达4顶点最好呢？此时就要考虑，那条路径的成本最低
2021-08-27 23:19:44
2537
1
原创 拓扑排序
拓扑排序在现实生活中，我们经常会同一时间接到很多任务去完成，但是这些任务的完成是有先后次序的。此时如果某个同学要完成这些任务，就需要指定出一个任务方案，我们只需要对图中的顶点进行排序，让它转换为一个线性序列，就可以解决问题，这时就需要用到一种叫拓扑排序的算法。拓扑排序：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。下列是一副拓扑排序后的示意图：1. 检测有向图中的环如果学习x课程前必须先学习y课程，学习y课程前
2021-08-26 07:45:43
239
原创 有向图、及其反向图
二、有向图2.1 有向图的定义及相关术语定义：有向图是一副具有方向性的图，是由一组顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。出度：由某个顶点指出的边的个数称为该顶点的出度。入度：指向某个顶点的边的个数称为该顶点的入度。有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。有向环：一条至少含有一条边，且起点和终点相同的有向路径。一副有向图中两个顶点v和w可能存在一下四种关系：没有边相连。存在从v->w的边。存在从
2021-08-24 00:18:24
3071
原创 无向图、深度优先搜索(无向图)、广度优先搜索(无向图)、无向图路径查找(基于深度优先搜索)
一、无向图1.1 图的相关术语相邻顶点：当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。度：某个顶点的度就是依附于该顶点的边的个数。子图：是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。路径：是由边顺序连接的一系列的顶点组成。环：是一条至少含有一条边且终点和起点相同的路径。连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图。连通子图：一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连
2021-08-24 00:15:21
2900
原创 二分查找（折半查找）
二分查找（折半查找）1. 原理2. 代码实现/** * 二分查找 */public class binarySearch { /* 对数组内的元素进行查找 */ public int search(Comparable[] arr, Comparable target) { int left = 0; int right = arr.length - 1; int mid = (left + right) / 2;
2021-08-21 23:00:59
109
原创 设计模式(单例、多例、工厂)
设计模式(单例、多例、工厂)一、单例设计模式1.1 单例设计模式的作用单例模式，是一种常用的软件设计模式。通过单例模式可以保证系统中，应用该模式的这个类只有一个实例。即一个类只有一个对象实例。1.2 单例设计模式实现步骤将构造方法私有化，使其不能在类的外部通过new关键字实例化该类对象。在该类内部产生一个唯一的实例化对象，并且将其封装为private static类型的成员变量。定义一个静态方法返回这个唯一对象。1.3 单例设计模式的类型根据实例化对象的时机单例设计模式又分为以下两种:
2021-08-18 16:57:17
246
原创 B树(B-、B+)
B树(B-、B+)一、B-树B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。B树，这种数据结构中，一个结点允许多于两个key的存在。1.1 B树的特征B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：每个结点最多有M-1个key，并且以升序排列；每个结点最多能有M个子结点；根结
2021-08-16 17:44:47
786
原创 平衡树(查找树、红黑树)
15-平衡树(查找树、红黑树)一、2-3查找树为了保证查找树的平衡性，我们需要一些灵活性，因此在这里我们允许树中的一个结点保存多个键。确切的说，我们将一棵标准的二叉查找树中的结点称为2-结点(含有一个键和两条链)，而现在我们引入3-结点，它含有两个键和三条链。2-结点和3-结点中的每条链都对应着其中保存的键所分割产生的一个区间。1.1 2-3查找树的定义一棵2-3查找树要么为空，要么满足满足下面两个要求：2-结点：含有一个键(及其对应的值)和两条链，左链指向的2-3树中的键，都小于该结点的键
2021-08-16 16:26:16
220
原创 xml+dom4j+反射--实现接口解耦(框架注解原理)
xml+dom4j+反射–实现接口解耦(模拟框架创建实例原理)public class BeanFactory { public static Object newInstance(String id) throws Exception { // 创建xml解析器 SAXReader sax = new SAXReader(); // 读取注册文件 Document document = sax.read("exercise\\sr
2021-08-16 16:21:09
98
原创 反射、注解、动态代理
反射、注解、动态代理一、反射1.1 类的加载器1.1.1 类的加载当我们的程序在运行后，第一次使用某个类的时候，会将此类的class文件读取到内存，并将此类的所有信息存储到一个Class对象中上图：Class对象是指：java.lang.Class类的对象，此类由Java类库提供，专门用于存储类的信息。我们程序中可以通过：“类名.class”，或者"对象.getClass()"方法获取这个Class对象1.1.2 类的加载时机创建类的实例。类的静态变量，或者为静态
2021-08-16 16:18:37
140
原创 NIO、AIO
NIO、AIOBuffer类Channel通道Selector选择器AIO一、NIO(同步、阻塞)NIO概述在我们学习Java的NIO流之前，我们都要了解几个关键词（NIO面向块的I/O系统）同步与异步（synchronous/asynchronous）：同步是一种可靠的有序运行机制，当我们进行同步操作时，后续的任务是等待当前调用返回，才会进行下一步；而异步则相反，其他任务不需要等待当前调用返回，通常依靠事件、回调等机制来实现任务间次序关系阻塞与非阻塞：在进行阻塞操作时，当前线
2021-08-11 21:45:46
256
原创 优先队列--最大、最小优先队列(基于堆思想)
优先队列–最大优先队列(基于堆思想)最大优先队列：可以获取并删除队列中最大的值最大优先队列API设计类名MaxPriorityQueue构造方法MaxPriorityQueue(int capacity)：创建容量为capacity的MaxPriorityQueue对象成员方法1.private boolean less(int i,int j)：判断堆中索引i处的元素是否小于索引j处的元素2.private void exch(int i,int j):交换堆中i索引和
2021-08-10 23:05:25
356
原创 Socket网络编程
Socket网络编程一、网络变成入门1.1 软件结构C/S结构 ：全称为Client/Server结构，是指客户端和服务器结构。常见程序有ＱＱ、迅雷等软件。B/S结构 ：全称为Browser/Server结构，是指浏览器和服务器结构。常见浏览器有谷歌、火狐等。两种架构各有优势，但是无论哪种架构，都离不开网络的支持。网络编程，就是在一定的协议下，实现两台计算机的通信的程序。1.2 网络通信协议**网络通信协议：**通信协议是计算机必须遵守的规则，只有遵守这些规则，计算机之间才
2021-08-08 22:15:11
2849
1
原创 File类、IO概述、字节流、字符流、属性集、缓冲流、转换流、序列化流
File类、IO概述、字节流、字符流、属性集、缓冲流、转换流、序列化流一、File类1.1 概述java.io.File 类是文件和目录路径名的抽象表示，主要用于文件和目录的创建、查找和删除等操作。1.2 构造方法public File(String pathname) ：通过将给定的路径名字符串转换为抽象路径名来创建新的File实例。public File(String parent, String child) ：从父路径名字符串和子路径名字符串创建新的 File实例。public Fi
2021-08-07 19:14:16
118
原创 多线程（死锁、等待与唤醒）
多线程（死锁、等待与唤醒）一、死锁（面试）代码实现：// 实现死锁机制public class MyRunnable implements Runnable { public static String lockA = "A锁"; public static String lockB = "B锁"; @Override public void run() { while (true) { synchronized (loc
2021-08-05 22:42:08
104
原创 Lambda表达式、函数式思想、Stream流
Lambda表达式一、Lambda表达式1.1 函数式编程思想概述 在数学中，函数就是有输入量、输出量的一套计算方案，也就是“拿什么东西做什么事情”。相对而言，面向对象过分强调“必须通过对象的形式来做事情”，而函数式思想则尽量忽略面向对象的复杂语法——强调做什么，而不是以什么形式做。做什么，而不是怎么做我们真的希望创建一个匿名内部类对象吗？不。我们只是为了做这件事情而不得不创建一个对象。我们真正希望做的事情是：将 run 方法体内的代码传递给 Thread 类知晓。传递一段代码——这才是
2021-08-03 22:45:01
143
原创 多线程、高并发及线程安全、volatile关键字、原子性、并发包、线程池、线程状态、定时器
多线程、高并发及线程安全、volatile关键字、原子性、并发包、线程池、线程状态、定时器一、多线程1.1 并发与并行并发：指两个或者多个事件，在同一时间段内发生（交替执行）。并行：指两个或者多个事件，在同一时刻发生（同时执行） 在操作系统中，安装了多个程序并发是指的是在一段时间内宏观上有多个程序同时运行，这在单CPU系统中，每一时刻只能有一道程序执行，即微观上这些程序是分时的交替运行，只不过给人的感觉是同时运行，那是因为分时的交替运行的时间是非常短的。而在多个 CPU 系统中，则
2021-08-03 22:36:03
220
原创 堆排序
堆排序给定一个数组： String[] arr = {“S”,“O”,“R”,“T”,“E”,“X”,“A”,“M”,“P”,“L”,“E”}请对数组中的字符按从小到大排序。AP设计：类名HeapSort<T extends Comparable>成员方法1.public static void sort(Comparable[] source)：对source数组中的数据从小到大排序2.private static void createHeap(Compa
2021-08-03 07:12:04
78
原创 堆--完全二叉树的数组实现
堆–完全二叉树的数组实现堆的定义堆是计算机科学中一类特殊的数据结构的统称，堆通常可以看作是一棵完全二叉树的数组对象。堆的特性1.它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。2.它通常用数组来实现。 具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推。A,E,G,H,I,N,O,P,R,S,T 如果一个结点的
2021-08-02 23:04:18
481
原创 Collection、泛型、List、Collections、Set、Map
Collection、泛型、List、Collections、Set、Map一、Collection集合1.1 集合概述 集合：集合是java中提供的一种容器，可以用来存储多个数据。 集合和数组的区别：数组的长度是固定的。集合的长度是可变的。数组中存储的是同一类型的元素，可以存储任意类型数据。集合存储的都是引用数据类型。如果想存储基本类型数据需要存储对应的包装类型1.2 集合常用类的继承关系 Collection：单列集合类的根接口，用于存储一系列符合某种规则的元素，它有两个
2021-07-30 19:41:01
186
原创 快速排序（冒泡排序的升级）
快速排序快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排过程可以递归进行，以此达到整个数据变成有序序列。需求：排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}排序原理：1.首先设定一个分界值，通过该分界值将数组分成左右两部分；2.将大于或等于分界值的数据放到到数组右边，小
2021-07-27 06:45:20
264
原创 归并排序
归并排序 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。需求：排序前：{8,4,5,7,1,3,6,2}排序后：{1,2,3,4,5,6,7,8}排序原理：1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。2.将相邻的两个子组进行合并成一个有序的大组；3.不断
2021-07-26 23:59:17
50
原创 希尔排序（插入排序的升级）
希尔排序（插入排序的升级）希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。前面学习插入排序的时候，我们会发现一个很不友好的事儿，如果已排序的分组元素为{2,5,7,9,10}，未排序的分组元素为{1,8}，那么下一个待插入元素为1，我们需要拿着1从后往前，依次和10,9,7,5,2进行交换位置，才能完成真正的插入，每次交换只能和相邻的元素交换位置。那如果我们要提高效率，直观的想法就是一次交换，能把1放到更前面的位置，比如一次交换就能把1插到2和5之间，这样一次交换1
2021-07-26 18:03:16
90
原创 插入排序
插入排序插入排序（Insertion sort）是一种简单直观且稳定的排序算法。插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，如下图所示：需求：排序前：{4,3,2,10,12,1,5,6}排序后：{1,2,3,4,5,6,10,12}排序原理：1.把所有的元素分为两组，已经排序的和未排序的；2.找到未排序的组中的第
2021-07-26 16:25:57
45
原创 选择排序
选择排序选择排序是一种更加简单直观的排序方法。需求：排序前：{4,6,8,7,9,2,10,1}排序后：{1,2,4,5,7,8,9,10}排序原理：1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引2.交换第一个索引处和最小值所在的索引处的值选择排序API设计：类名Selection构造方法Selection()：创建Sel
2021-07-26 16:04:28
46
原创 冒泡排序
冒泡排序 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。需求：排序前：{4,5,6,3,2,1}排序后：{1,2,3,4,5,6}排序原理：比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。冒泡排序API设计：类名Bubble构造方法Bubble()：创建Bubble对象成员方法1.public
2021-07-26 10:27:22
54
原创 二叉树（链表实现）--应用案例（最大深度、折纸问题）
二叉树–最大深度、折纸问题二叉树的最大深度问题需求： 给定一棵树，请计算树的最大深度（树的根节点到最远叶子结点的最长路径上的结点数）; 上面这棵树的最大深度为4。实现：public int maxDepth()：计算整个树的最大深度private int maxDepth(Node x):计算指定树x的最大深度实现步骤：1.如果根结点为空，则最大深度为0；2.计算左子树的最大深度；3.计算右子树的最大深度；4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+
2021-07-26 00:02:07
376
原创 二叉树（链表实现）--前序、中序、后序、层序遍历
二叉树（链表实现）–前序、中序、后序、层序遍历 我们把树简单的画作上图中的样子，由一个根节点、一个左子树、一个右子树组成，那么按照根节点什么时候被访问，我们可以把二叉树的遍历分为以下三种方式：1.前序遍历； 先访问根结点，然后再访问左子树，最后访问右子树2.中序遍历； 先访问左子树，中间访问根节点，最后访问右子树3.后序遍历； 先访问左子树，再访问右子树，最后访问根节点如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：前序遍历public Queu
2021-07-25 22:48:01
3818
原创 二叉树（链表实现）--增、删、改、查
二叉树（链表实现）1.1 树的基本定义 树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构、等等。 树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树具有以下特点：每个结点有零个或多个子结点；没有父结点的结点为根结点；每一个非根结点只有一个父结点；每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树；
2021-07-25 07:03:01
656
1
原创 符号表（以及有序符号表）
符号表 符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的键值对数据，我们可以根据键来查找对应的值。 符号表是利用单链表实现的，原先的链表的结点只有item和next数据，而实现符号表的链表的结点为key、value、next数据 符号表中，键具有唯一性。 符号表在实际生活中的使用场景是非常广泛的，见下表：应用查找目的键值字典找出单词的释义单词释义图书索引找出某个术语相关的页码术语一串页码
2021-07-22 17:12:56
950
原创 队列
队列 队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。队列的API设计方法名方法功能public boolean isEmpty()判断队列是否为空，是返回true，否返回falsepublic int size()获取队列中元素的个数public T dequeue()从队列中拿出一个元素public void enqueu
2021-07-22 15:28:44
61
原创 栈
栈 栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。/** * 栈--单链表实现（头结点位置是栈顶） */public class Stack<T> implements Iterable<T> { // 记录首结点
2021-07-22 15:26:24
54
原创 栈--逆波兰表达式求值
栈–逆波兰表达式求值中缀表达式： 中缀表达式就是我们平常生活中使用的表达式，例如：1+3*2,2-(1+3)等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。 中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作逆波兰表达式(后缀表达式) 逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于
2021-07-22 10:55:07
244
原创 循环链表–约瑟夫问题
循环链表–约瑟夫问题问题描述： 传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏 。问题转换：41个人坐
2021-07-20 23:48:23
57
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人