naive的博客

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< ...

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 ...

一、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是一种纯文本格式的标记语言。通过简单的标记语法，它可以使普通文本内容具有一定的格式。 一、标题在想要设置为标题的文字前面加#来表示一个#是一级标题，二个#是二级标题，以此类推。支持六级标题。 注：标准语法一般在#后跟个空格再写文字，貌似简书不加空格也行。 示例： 123456# 这是一级标题## 这是二级标题### 这是三级标题#### 这是四级标题##### 这是五级标题###### 这是六级标题 二、字体 加粗：要加粗的文字左右分别用两个*号包起来 斜体：要倾斜的文字左右分别用一个*号包起来 斜体加粗：要倾斜和加粗的文字左右分别用三个*号包起来 删除线：要加删除线的文字左右分别用两个~~号包起来 示例： 1234**这是加粗的文字***这是倾斜的文字*`***这是斜体加粗的文字***~~这是加删除线的文字~~ 效果如下： 这是加粗的文字这是倾斜的文字`这是斜体加粗的文字这是加删除线的文字 三、引用在引用的文字前加>即可。引用也可以嵌套，如加两个>>三个>>>，n个…貌似可以一直加下去，但没神马卵用 示例： 123&g ...

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模式。对于复杂的对象而言，直接 ...

一、简介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去执行并返回结果, ...