Dimple在左耳听风ARTS打卡（十）

题图：2019法网的纳达尔。小编是纳达尔多年的球迷了，从他第一个法网冠军开始就是小迷弟，尤其是在红土的统治力，以及他体现出来的意志力等等，是我学习的榜样。10个火枪手杯在手，期待今年再次捧杯，让组委会头疼一个特殊的仪式去吧，哈哈。

所谓ARTS： 每周至少做一个LeetCode的算法题；阅读并点评至少一篇英文技术文章；学习至少一个技术技巧；分享一篇有观点和思考的技术文章。（也就是Algorithm、Review、Tip、Share 简称ARTS）这是第十期打卡。

截止到今天为止，把《Spring Cloud微服务》这本书已经从入门到实践，并且看完一遍。前面搭建环境的部分很用心地在实践，后面因为还得根据实际项目情况，实际分析，所以就粗略看了下各种知识点，准备在项目实际进展中开干!

Algorithm LeetCode算法

实现strStr() (https://leetcode-cn.com/problems/implement-strstr/)

题目描述：实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1：

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明：

当needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

题目已经描述的很清楚了，其实就是让你自己去实现一个编程语言自带的函数，在Java中叫indexOf()，C语言中叫strStr()，其他语言自己相应的对号入座噢。

其实也从侧面反应，最好的学习办法就是从学习源码开始。哈哈，这题解完，你可以去和源码对比下，有能力的同学，还可以把源码修改下拿去运行，看看到底是你执行的效率高，还是源码执行的销量高呢？

看了下题解，说是为了考察用户的KMP算法，此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。其实还有一个暴力法，也挺好用的，我都给呈现出来。

暴力法 

public static int strStr1(String S, String T) {
    int n1 = S.length();
    int n2 = T.length();
    if (n1 < n2) return -1;
    else if ( n2 == 0) return 0;
    for (int i = 0; i < n1 - n2 + 1; i++ ){
        if (S.substring(i, i+n2).equals(T)) return i;
    }
    return -1;
}

KMP算法，具体思路，可以搜索下噢，在这里不再赘述了。

public static int strStr2(String haystack, String needle) {
    //如果都为空或者needle为空，则返回0
    if((haystack.length() < 1 && needle.length() < 1) || haystack.length() >= 1 && needle.length() < 1)){
        return 0;
    }
    if(haystack == null || needle == null || haystack.length() < 1 || needle.length() < 1){
        return -1;
    }        

    //主字符串haystack的下标
    int index1 = 0;
    //模式串needle的下标
    int index2 = 0;
    char[] char1 = haystack.toCharArray();
    char[] char2 = needle.toCharArray();
    //获得nexts数组
    int[] nexts = getNexts(char2);
    while(index1 < char1.length && index2 < char2.length){
        if(char1[index1] == char2[index2]){
            index1++;
            index2++;
        }else if(nexts[index2] == -1){//如果为第一位都不匹配则直接下一个字符
            index1++;
        }else{
            index2 = nexts[index2];
        }
    }
    return index2 == char2.length ? index1 - index2 : -1;
}
//获得next数组
public static int[] getNexts(char[] str2){
    if(str2.length == 1){
        return new int[]{-1};
    }
    int[] nexts = new int[str2.length];
    nexts[0] = -1;
    nexts[1] = 0;
    //指向当前元素最长前缀的指
    int cn = 0;
    //遍历字符串时的下标
    int index = 2;
    while(index < str2.length){
        if(str2[index - 1] == str2[cn]){
            nexts[index++] = ++cn;
        }else if(cn > 0){
            cn = nexts[cn];
        }else{
            nexts[index++] = 0;
        }
    }
    return nexts;
}

Review 阅读并点评至少一篇英文文章

How to think like a programmer—lessons in problem solving (https://medium.com/free-code-camp/how-to-think-like-a-programmer-lessons-in-problem-solving-d1d8bf1de7d2)

因为之前查找英文文档都是Medium这个地址，这周选择了一篇他根据我阅读文章的历史推荐给我的，虽然时间是2018年的文章，但看到标题就吸引了我，不知道是否吸引了你呢？

文章开篇用了乔布斯的一句话：“这个国家的每个人都应该学习编程计算机，因为它会教你思考”。足以说明，现在是互联网最好的时代，我们选择了编程，其实就是选择了最好的时代，选择了未来。

现在是冬天，很多初级程序员一开始找工作会碰壁，是因为雇主想要一个能力强的，能快速解决问题的能人，而初级程序员暂时不具备这个能力。好吧，原来老外对这个要求也是很苛刻的，并不只是我们周边存在这种情况哦。

我看到新程序员犯的最大错误就是专注于学习语法而不是学习如何解决问题。这是 V. Anton Spraul，一位优秀程序员说的。在此，文中给了我们解决问题的几个步骤：

1. 理解明白

当你遇到一个问题的时候，首先你得理解明白这个问题。如果你拿到一个问题，但是你不能用一个简单的术语解释清楚，其实，你对这个问题还是不明白。

1. 计划

如果你没有计划（我理解的是想法），你就先别动手去解决他。不知道平时的你是不是会有这种感觉，遇到一个bug，先不着急动手去改，而是刨根问底，找到问题的根本原因。最好是画一个图来描绘下。

1. 分解

请注意了，这是最重要的一部分。不要试图一次性能解决一个大问题，我们应该做的是，把问题一个个划分出来，通过一个个子问题，单独击破，最终这个大问题就会迎刃而解。

1. 卡住？

哈哈，其实当你分解问题之后，还是会遇到很多你解决不了的问题。别担心，这个其实每个人都会遇到的，但是“不同之处在于最好的程序员/问题解决者对错误/错误更感兴趣而不是恼火”。

这个时候，你就需要通过调试，问题再分解，甚至你还得重新评估之前的判断，善用搜索引擎来查看别人是否也有类似的问题。

练习、练习、练习，如果你想成为一名优秀的解决问题的能手，那就得多练习。是吧，我们一直强调，写程序就是要实践，不停地实践，看书，刷网页，都不足以帮助你解决问题，最关键的还得是自己亲身经历过。

小编上周，通过看书+实践，才勉强完成微服务的入门，就是这个道理。期间遇到了新版本的很多问题，都是靠一点一点实践，把大问题分解，转换成一个个力所能及的小问题，才得以入门。写程序的世界，真的是无国度啊。

看完这篇，小编发现，在编程的世界里，每个国度都是类似的。尤其是解决问题的方式，以及写程序的方式。作者最后希望我们能遇到更多的问题。一段经典话语送给大家：

就在你认为自己已成功驾驭一个障碍时，另一个障碍就出现了。

但这就是让生活变得有趣的东西，生命是一个突破这些障碍的过程-我们必须突破一系列强化路线。

每一次，你都会学到一些东西。

每一次，你都会发展力量，智慧和观点。

每一次，竞争的一点点都会消失。 直到剩下的就是你：最好的版本。

所以，ARTS打卡，真的很棒。我们在不停地刷题，不停地看文档，了解“同一个世界，同一个编程”，哈哈。感谢ARTS打卡。

Tip 一个技术技巧

继续分享《Java核心技术36讲》做的学习笔记，今天分享的有点长。谈谈MySQL支持的事务隔离级别，以及悲观锁和乐观锁的原理和应用场景

典型回答 所谓隔离级别（Isolation Level），就是在数据库事务中，为保证并发数据读写的正确性而提出的定义，它并不是MySQL专有的概念，而是源于ANSI/ISO制定的SQL-92标准

以最常见的MySQL InnoDB引擎为例，它是基于MVCC（Multi Versioning Concurrency Control）和锁的复合实现，按照隔离程度从低到高，MySQL事务隔离级别分为四个不同层次：

• 读未提交（Read uncommitted），就是一个事务能够看到其他事务尚未提交的修改，这是最低的隔离水平，允许脏读出现
• 读已提交（Read committed），事务能够看到的数据都是其他事务已经提交的修改，也就是保证不会看到任何中间性状态，当然脏读也不会出现。读已提交仍然是比较低级别的隔离，并不保证再次读取时能够获取同样的数据，也就是允许其他事务并发修改数据，允许不可重复读和幻象读（Phantom Read）出现
• 可重复读（Repeatable reads），保证同一个事务中多次读取的数据是一致的，这是MySQL InnoBD引擎的默认隔离级别，但是和一些其他数据库实现不同的是，可以简单认为MySQL在可重复读级别不会出现幻象读
• 串行化（Serializable），并发事务之间是串行化的，通常意味着读取需要获取共享锁，更新需要获取排它锁，如果SQL使用WHERE语句，还会获取区间锁（MySQL以GAP锁形式实现，可重复读级别中默认也会使用），这是最高的隔离级别

知识扩展 对数据库相关领域学习的看法，从最广泛的应用开发者角度，至少需要掌握：

• 数据库设计基础，包括数据库设计中的几个基本范式，各种数据库的基础概念，例如表、视图、索引、外键、序列号生成器等，清楚如何将实现中业务实体和其他依赖关系映射到数据库结构中，掌握典型实体数据应该使用什么样的数据库数据类型等。
• 每种数据库的设计和实现多少会存在差异，所以至少要精通你使用过的数据库的设计要点。比如MySQL事务隔离级别，就区别于其他数据库，进一步了解MVCC、Locking等机制对于处理进阶问题非常有帮助；还需要了解，不同索引类型的使用，甚至是底层数据结构和算法等。
• 常见的SQL语句，掌握基础的SQL调优技巧，至少要了解基本思路是怎样的，例如SQL怎样写才能更好利用索引、知道如何分析SQL执行计划等。
• 更进一步，至少需要了解针对高并发等特定场景中的解决方案，例如读写分离、分库分表、或者如何利用缓存机制等，目前的数据存储也远不止传统的关系型数据库了。

关于具体开源框架的学习，建议：

• 从整体上把握主流框架的架构和设计理念，掌握主要流程，例如SQL解析生成、SQL执行到结果映射等处理过程到底发生了什么
• 掌握映射等部分的细节定义和原理
• 另外，对比不同框架的设计和实现，既有利于加深理解，也是面试考察的热点方向之一

O/R Mapping 框架 Hibernare，MyBatis

从架构设计的角度，可以讲MyBatis分为哪几层？每层都有哪些主要模块？ -自下而上分为基础支撑层、数据处理层、API接口层

1. 基础支撑层，主要是用来做连接管理、事务管理、配置加载、缓存管理等最基础组件，为上层提供最基础的支撑
2. 数据处理层，主要是用来做参数映射、SQL解析、SQL执行、结果映射等处理，可以理解为请求到达，完成一次数据库操作的流程
3. API接口层，主要堆外提供API，提供诸如数据的增删改查、获取配置等接口

Share 一篇有观点和思考的技术文章

因为上周全身心投入了微服务，所以趁热打铁，写了篇关于微服务入门遇到问题的总结，在这里和大家分享。

公众号地址： Spring Cloud微服务初探