KMP算法
KMP算法KMP解决的问题字符串str1和字符串str2,str1是否包含str2,如果包含返回str2在str1中的位置。如何做到时间复杂度O(n)完成?
12str1 111111112str2 1112
这样如果使用暴力查找,复杂度较高,O(n*m) str1是n,str2是m
最长前缀和求字符串中字符k前面的前缀和后缀的最大匹配个数。
例如字符串 abbabbk前后缀如下
1
2
3
4
5
前缀
a
ab
abb
abba
abbab
后缀
b
bb
abb
babb
bbabb
x
x
√
x
x
对于k来说就前缀和后缀的最大匹配个数为3。
对于 aaaaak前后缀如下:
1
2
3
4
前缀
a
aa
aaa
aaaa
后缀
a
aa
aaa
aaaa
√
√
√
√
对于k来说就前缀和后缀的最大匹配个数为4。
KMP算法KMP算法第一步就是求解字符串str每一位字符前面字符的前缀和后缀的最大匹配个数,叫nextarr,利用数组对查找进行加速。
对于字符串 aabaabsaa每一位的前缀和后缀的最大匹配个数如下(n ...
有序表并查集
来源 左神 有序表并查集
并查集岛问题【题目】leetcode 200一个矩阵中只有0和1两种值,每个位置都可以和自己的上、下、左、右四个位置相连,如果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?
123456【举例】001010111010100100000000这个矩阵中有三个岛
遍历二维数组每一位, 如果这一位为1,就调用感染函数进行感染(周围的岛屿都变为2),记录了调用几次感染函数,就有几个岛屿。
1234567891011121314151617181920212223242526272829303132333435363738394041424344public class CountIslands { /* 定义 遍历二维数组每一位, 如果这一位为1,就调用感染函数进行感染,最后记录了调用几次感染函数 */ public int numIslands(char[][] m) { if (m == null || m[0] == null) { return 0 ...
哈希函数和哈希表
哈希函数out = f(in)
in -> 无穷,out -> string 有限
md5: 0 - 2^64^-1
sha1: 0 - 2^128^-1
same in -> same out 不随机
different in -> same out (哈希碰撞)
离散性和均匀性 (输入有规律,输出无规律)
in 通过hash函数得到 out 再取模 %m 就可以的带 0 - (m-1) 范围的数
题1一个大文件 无符号整数 (2^32^-1 就是 0- 42亿范围)有40亿个数,1g内存求出现次数最多的数是哪一个?
如果使用hash表来做 key - value ,key是(4B),value是int(4B), 一个数就要8B,如果40亿个数都不一样,就需要 320亿B(32G)。
对数据a 先使用 hash函数得到数 b,然后 % 100得到 0-99范围的数,相同的数据进同一个文件,不同的数种类上进不同文件。对每一个小文件使用hash表,然后求出这100个数的最大值。不怕同一种数太多,怕不同种的数太多,内存不够。
哈希表表 + ...
结果处理器
ResultSetHandler:结果集处理器
ResultContext:结果提出
ResultHandler:结果处理器
ResultSetHandler1234567public interface ResultSetHandler { //包装结果集 <E> List<E> handleResultSets(Statement stmt) throws SQLException; //处理存储过程输出参数的 void handleOutputParameters(CallableStatement cs) throws SQLException;}
DefaultResultSetHandler,在默认的情况下都是通过这个类进行处理的。这个实现有些复杂,它涉及使用JAVASSIST 或者CGLIB作为延迟加载,然后通过typeHandler和ObjectFactory进行组装结果再返回。
ResultContext控制结果的获取
1234567891011public interface ResultContext< ...
SqlSeesion缓存
SqlSession原理中介绍了在SQL查询时一级缓存和二级缓存的调用过程。这里介绍一下缓存的场景和失效。
一、一级缓存一级缓存与SqlSession相关,是一个会话级别的缓存,会话关闭清空缓存。在会话中一级缓存与运行时参数和操作配置相关
命中场景123456789101112131415161718192021public class FirstCacheTest { private Configuration configuration; private SqlSession sqlSession; @Before public void init() throws IOException, SQLException { SqlSessionFactoryBuilder factoryBuilder = new SqlSessionFactoryBuilder(); InputStream inputStream = Resources.getResourceAsStream("mybat ...
SqlSeesion原理
一、sqlSession运行过程SqlSession采用了门面模式,提供了API(增删改查),辅助API(提交关闭)。
核心执行组件Executor,执行操作。提供了(改和查的操作),维护缓存,辅助API(提交、关闭执行器、批处理刷新)
映射器的动态代理Mapper映射是通过动态代理来实现的
1234567891011121314151617181920212223242526public class MapperProxyFactory<T> { private final Class<T> mapperInterface; private Map<Method, MapperMethod> methodCache = new ConcurrentHashMap(); public MapperProxyFactory(Class<T> mapperInterface) { this.mapperInterface = mapperInterface; } pub ...
markdown语法
Markdown是一种纯文本格式的标记语言。通过简单的标记语法,它可以使普通文本内容具有一定的格式。
一、标题在想要设置为标题的文字前面加#来表示一个#是一级标题,二个#是二级标题,以此类推。支持六级标题。
注:标准语法一般在#后跟个空格再写文字,貌似简书不加空格也行。
示例:
123456# 这是一级标题## 这是二级标题### 这是三级标题#### 这是四级标题##### 这是五级标题###### 这是六级标题
二、字体
加粗:要加粗的文字左右分别用两个*号包起来
斜体:要倾斜的文字左右分别用一个*号包起来
斜体加粗:要倾斜和加粗的文字左右分别用三个*号包起来
删除线:要加删除线的文字左右分别用两个~~号包起来
示例:
1234**这是加粗的文字***这是倾斜的文字*`***这是斜体加粗的文字***~~这是加删除线的文字~~
效果如下:
这是加粗的文字这是倾斜的文字`这是斜体加粗的文字这是加删除线的文字
三、引用在引用的文字前加>即可。引用也可以嵌套,如加两个>>三个>>>,n个…貌似可以一直加下去,但没神马卵用
示例:
123&g ...
Mybatis原理
MyBatis的解析和运行原理
MyBatis 的运行分为两大部分,第一部分是读取配置文件缓存到Configuration对象,用以创建SqISessionFactory,第二部分是SqISession的执行过程。
构建SqlSessionFactory过程
通过org.apache.ibatis.builder.xm1.XMLConfigBuilder解析配置的XML文件,读出配置参数,并将读取的数据存入这个org.apache.ibatis.session.Configuration类中。注意,MyBatis 几乎所有的配置都是存在这里的。
使用Confinguration对象去创建SqISessionFactory。MyBatis中的SqISessionFactory是一个接口,而不是实现类,为此 MyBatis 提供了一个默认的SqISessionFactory’实现类,我们一般都会使用它org.apache.ibatis.session.defaults.DefaultSqlSessionFactory。
这种创建的方式就是一种 Builder模式。对于复杂的对象而言,直接 ...
Mybatis简介
一、简介JDBCJDBC是java提供的连接数据库的规范。
JDBC连接数据库的步骤:
注册驱动和数据库信息
操作Connection,打开Statement对象
通过Statement执行SQL,返回结果到ResultSet中
使用ResultSet读取数据,通过代码转换为具体的POJO对象
关闭数据库。
ORM模型操作数据库的过程复杂,ORM模型基于JDBC进行封装。ORM模型就是数据库的表和简单Java对象(Plain Ordinary Java Object,简称POJO)的映射关系模型,它主要解决数据库数据和POJO对象的相互映射。
MybatisMyBatis是一个半自动映射的框架。之所以称它为半自动,是因为它需要手工匹配提供POJO、SQL和映射关系。
二、Mybatis的构成核心组件
SqlSessionFactoryBuilder(构造器):它会根据配置信息或者代码来生成SqlSessionFactory (工厂接口)。
SqlSessionFactory:依靠工厂来生成SqlSession(会话)。
SqlSession:是一个既可以发送SQL去执行并返回结果, ...