Kid1999' Blog

最小生成树 我们定义无向连通图的 最小生成树 （Minimum Spanning Tree，MST）为边权和最小的生成树。 以下实现皆是基于LeetCode 5513题：连接所有点的最小费用的实现 1234567连接所有点的最小费用 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。 Kruskal 算法 Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354public class Kr ...

并查集 DisJoint 检查图上是否存在环 通过一个数组表示每个点的父节点地址 通过查询每个节点的父节点是否相同判断是否是同一个集合 核心两个方法：1.找到根节点2.合并两个集合123456789101112131415161718192021222324252627282930313233343536373839404142434445public class Disjoint { public static void main(String[] args) { int[][] edges = { {0,1},{1,2},{1,3}, {3,2},{2,4} }; int len = (int) 1e5; int[] parents = new int[len]; Arrays.fill(parents,-1); // 初始化 // xxxx 其他操作 for (int[] edge:edges) { ...

ElasticSearch Elasticsearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎，基于RESTful web接口。 本文基于 Elasticsearch7.8.0。 目录 ElasticSearch的安装使用 相关配套设施的安装使用 基本概念简介 SpringBoot整合Elasticsearch的两种方案1. 自定义封装RestHighLevelClient 基于JPA规范开发 1. ElasticSearch的安装使用 基于window 解压运行 基于docker（参见 常用docker环境运维） 2. 相关配套设施的安装使用 elasticsearch-head ： 类似Navicat的elasticseach的数据可视化查询工具（Chrome商店安装） Kibana：ElasticSearch官方配套可视化组件，可组成ELK日志处理可视化体系 安装：下载解压 修改配置文件 config/kibana.yml ： 123456# 端口server.port: 5601# elasticsearch 地址elas ...

Spring-Security 统一提供拦截器，接口实现用户权限验证，放行等安全工作。可整合OAuth2、JWT等验证模式。 此处为SpringBoot整合SpirngCouldOauth2实现JWT验证的实例 目录 Maven依赖 web安全配置WebSecurityConfig User对象实现UserDetails配置验证 UserService实现UserDetailsService实现验证流程* AuthorizationServerConfig 授权服务器 配置 JwtTokenStoreConfig JWT存储配置 JwtTokenEnhancer JWT内容扩展(可选) ResourceServerConfig 资源服务器 配置 测试 1.Maven依赖1234567891011121314151617181920212223242526272829303132333435363738<properties> <java.version>1.8</java.version> <spring ...

最短路径的两个算法 Dijkstra — 单源最短路 基于dfs Floyd算法 — 多源最短路 基于矩阵 SPFA算法 — 单源最短路 本文主要介绍 Dijkstra 在Java中的使用(Dijkstra)迪杰斯特拉算法解决的问题是： 在一个有向图中，求图中一个节点到其他所有节点的最短距离 算法思路：每次选取一个离出发点最近且未标记的节点，调整出发点到以这个节点为中心的周边节点的最短距离。这个过程持续 n - 1 次，直到所有节点都遍历完毕。 假设有一个这样的图（图片出处：Dijkstra算法Java实现）： 1.求节点 1 到其他节点的最短距离思路： 记录 start 点到各点的最短路径长度 找出一个未标记的离出发点最近的节点(最短边) 标记该节点为已经访问过 基于该点更新其他点到start点的距离 循环往复到遍历完所有节点12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849public class Test { public ...

蓝桥杯2020省赛总结A: 门牌制作 123456789101112public class A { public static void main(String[] args) { int res = 0; for (int i = 1; i <=2020 ; i++) { String s = String.valueOf(i); for(char c:s.toCharArray()){ if(c == '2') res++; } } System.out.println(res); }} B: 寻找 2020 12345678910111213141516171819202122232425262728293031323334353637383940414243444546import java.io.File;import java.io.FileInputStream;import java.io.FileNotFoundException;im ...

双指针技巧可以分为两类 「快慢指针」 解决主要解决链表中的问题，比如典型的判定链表中是否包含环 「左右指针」 后者主要解决数组（或者字符串）中的问题，比如二分查找、滑动窗口 一、快慢指针的常见算法快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。 1、判定链表中是否含有环这应该属于链表最基本的操作了，如果读者已经知道这个技巧，可以跳过。 单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。 如果链表中不包含环，那么这个指针最终会遇到空指针 null 表示链表到头了，这还好说，可以判断该链表不含环。 12345boolean hasCycle(ListNode head) { while (head != null) head = head.next; return false;} 但是如果链表中含有环，那么这个指针就会陷入死循环，因为环形数组中没有 null 指针作为尾部节点。 经典解法就是用两个指针，一个每次前进两步，一个每次前 ...

以下操作基于Centos7 1.目录 docker安装 mysql安装 redis安装 minio安装 rabbitMQ安装 ElasticSearch安装 hadoop-spark安装 zookeepker、kafka安装 1.docker安装centos 7 安装: 在新主机上首次安装Docker CE之前，需要设置Docker存储库。之后，您可以从存储库安装和更新Docker。 12345678910111213141516171819202122231. 安装所需的包sudo yum install -y yum-utils \ device-mapper-persistent-data \ lvm2sudo yum install -y yum-utils \ device-mapper-persistent-data \ lvm22. 设置稳定存储库sudo yum-config-manager \ --add-repo \ https://download.docker.com/linux/centos/docker-ce.repo3. 安装 ...

适用范围： 我已经有了一个类，但是这个类还不够让我满意，我就拿装饰器给他装饰一下。 代码演示： 假如我去喝咖啡，但是咖啡是苦的，我需要加糖装饰一下 苦咖啡 与 加糖咖啡 都是基于 咖啡接口 即将刚开始的苦咖啡经过加糖咖啡的装饰返回了一杯新的咖啡 咖啡接口 123456public interface Coffee { /** * 打印当前咖啡的原材料，即咖啡里有什么 */ void printMaterial();} 苦咖啡实现类 123456public class BitterCoffee implements Coffee { @Override public void printMaterial() { System.out.println("咖啡"); }} 默认点餐逻辑 123456public class Main { public static void main(String[] args) &# ...

简单工厂模式定义：由一个工厂对象决定创建出哪一种类型实例。客户端只需传入工厂类的参数，无心关心创建过程。 优点：具体产品从客户端代码中抽离出来，解耦。 缺点：工厂类职责过重，增加新的类型时，得修改工程类得代码，违背开闭原则。 举例：新建Fruit水果抽象类，包含eat抽象方法： 123public abstract class Fruit { public abstract void eat();} 其实现类Apple： 123456public class Apple extends Fruit{ @Override public void eat() { System.out.println("吃🍎"); }} 新建创建Fruit的工厂类： 123456789public class FruitFactory { public Fruit produce(String name) { if ("apple" ...