什么是AOP

AOP（Aspect-Oriented Programming，面向方面编程）是对OOP（Object-Oriented Programming，面向对象编程）的补充和完善。OOP引入封装、继承和多态等概念来建立对象层次结构，当需要为分散的对象引入公共行为时，OOP就显得无能为力。OOP适合定义从上到下的关系，但不适合定义从左到右的关系。例如日志功能的代码往往水平地分散在所有对象层次中，这种水平分布的代码称为横切（cross-cutting）代码，在OOP设计中会导致大量的代码重复，不利于代码复用和系统维护。

AOP采用“横切”技术，将那些影响了多个类的公共行为封装到一个可重用的模块（Aspect即方面）中。如果对象是一个空心的圆柱体，其中封装的是对象的属性和行为，那么AOP就像一把利刃，将这些空心圆柱体剖开，剖开的切面就是Aspect切面。

AOP把软件分为两个部分：核心关注点和横切关注点。业务处理的主要流程是核心关注点，与之关系不大的部分是横切关注点。横切关注点经常发生在核心关注点的多处，各处基本相似。比如权限认证、日志、事务处理。AOP的核心思想就是将业务逻辑同对其提供支持的通用服务进行分离。

实现AOP的技术分为两类：一是采用动态代理技术，利用截取消息的方式，对消息进行装饰，以取代原有对象行为的执行；二是采用静态织入的方式，引入特定的语法创建Aspect，从而使编译器可以在编译期间织入Aspect代码。

AOP使用场景

1. Authentication权限
2. Caching缓存
3. Context passing内容传递
4. Error handling错误处理
5. Lazy loading懒加载
6. Debugging调试
7. logging，tracing，profiling and monitoring记录，追踪，优化校准
8. Performanceoptimization性能优化
9. Persistence持久化
10. Resource polling资源池
11. Synchronization同步
12. Transaction事务

AOP中的概念

切面（Aspect）：切面用于组织多个Advice，Advice放在切面中定义。在Spring AOP 底层来, Aspect 的概念使用 Advisor 代替, 一个 Advisor 只有一个 Pointcut 和 相应的 Advice。
连接点（Joinpoint）：程序执行中明确的点，如方法的调用，或者异常的抛出。
增强处理（Advice）：AOP框架在特定的切入点执行增强处理，有Before、After、Around、Throws、Introduction等类型
切入点（Pointcut）：可以插入增强处理的连接点，当某个连接点满足指定要求时，该切入点被添加增强处理，该连接点也就变成了切入点
引入（Introduction）：将方法或字段添加到被处理的类中，Spring允许将新的接口引入到任何被处理的对象中，例如，可以使用一个引入使任何对象实现IsModified接口，以简化缓存
目标对象（Target Object）：包含连接点的对象，也被称为增强的对象，如果AOP采用动态AOP实现，那么该对象就是一个被代理的对象
AOP代理（AOP Proxy）：AOP框架创建的对象，代理就是对目标对象的加强。Spring AOP中使用JDK动态代理为实现接口创建代理，cglib为没有实现接口的目标创建代理。
织入（Weaving）：将增强处理添加到目标对象中，并创建一个被增强的对象（AOP代理）的过程就是织入。织入有两种方式：编译时增强（AspectJ）和运行时增强（如Spring AOP）

参考资料

控制反转IoC（Inverse of Control）与依赖注入DI（Dependency Injection）：依赖注入和控制反转是对同一件事情的不同描述，从某个方面讲，就是它们描述的角度不同。依赖注入是从应用程序的角度在描述，可以把依赖注入描述完整点：应用程序依赖容器创建并注入它所需要的外部资源；而控制反转是从容器的角度在描述，描述完整点：容器控制应用程序，由容器反向的向应用程序注入应用程序所需要的外部资源。

其实IoC/DI对编程带来的最大改变不是从代码上，而是从思想上，发生了“主从换位”的变化。应用程序原本是老大，要获取什么资源都是主动出击，但是在IoC/DI思想中，应用程序就变成被动的了，被动的等待IoC/DI容器来创建并注入它所需要的资源了。

这么小小的一个改变其实是编程思想的一个大进步，这样就有效的分离了对象和它所需要的外部资源，使得它们松散耦合，有利于功能复用，更重要的是使得程序的整个体系结构变得非常灵活。

BeanFactory与ApplicationContext

Spring IoC有两个主要的容器系列：

1. 实现BeanFactory接口的简单容器系列，这一系列容器只实现了容器的最基本功能
2. ApplicationContext应用上下文，它作为容器的高级形态存在。应用上下文在简单容器的基础上，增加了许多面向框架的特性，同时对应用环境做了许多适配

BeanFactory是IoC容器体系结构中最基本的接口类
BeanDefinition是对依赖反转模式中管理对象依赖关系的数据抽象，也是容器实现依赖反转功能的核心数据结构

BeanFactory接口定义了基本的IoC容器的规范，包含了getBean()这样的IoC容器的基本方法（通过这个方法可以从容器中取得Bean）。HierarchicalBeanFactory接口继承了BeanFactory接口之后，增加了getParentFactory()接口功能，使BeanFactory具备了双亲IoC管理的功能。在ConfigurableBeanFactory接口中，定义了一些对BeanFactory的配置功能，比如通过setParentBeanFactory()设置双亲IoC容器，通过addBeanPostProcessor()配置bean后置处理器等等。通过这些接口设计的叠加，定义了BeanFactory就是简单IoC容器的基本功能。

在ApplicationContext设计中，一方面它继承了BeanFactory接口体系中的ListableBeanFactor、HierachicalBeanFactory等BeanFactory的接口，具备了BeanFactory IoC的基本功能（并未继承AutowireCapableBeanFactory接口，因为几乎不会被程序用到，但是可以通过ApplicationContext的getAutowireCapableBeanFactory()获得）；另一方面，通过继承MessageSource、ResourceLoader、ApplicationEventPublisher这些接口，为ApplicationContext赋予更高级的IoC容器特性。

BeanFactory容器设计原理（以XmlBeanFactory为例）

运行时类型信息（RTTI）的作用

通过运行时类型信息可以在程序运行时使用类型信息，这一特性使程序员从只能在编译期执行面向类型的操作中解脱出来，从而可以构建更加强大的程序。

Class对象

类的运行时类型信息由Class对象表示的，每个类都有一个Class对象，每当编写并编译一个新类，就会产生一个Class对象。

Instances of the class Class represent classes and interfaces in a running Java application. An enum is a kind of class and an annotation is a kind of interface. Every array also belongs to a class that is reflected as a Class object that is shared by all arrays with the same element type and number of dimensions. The primitive Java types (boolean, byte, char, short, int, long, float, and double), and the keyword void are also represented as Class objects.

Class类没有构造器，当某个类被加载时，这个类的Class对象由虚拟机自动创建。

反射

Class类与java.lang.reflect类一起实现了Java的反射，reflect类库包含了Field、Method以及Constructor类（都实现了Member接口）、这些类型的对象是由JVM在运行时创建的，用以表示未知类对应的成员。可以通过Constructor创建新的对象，用get()和set()方法读取和修改与Field对象关联的字段，用invoke()方法调用与Method对象关联的字段，还可以调用getField()、getMethod()和getConstructor()返回字段、方法以及构造器的数组。这样匿名对象的类信息就能在运行时被确定下来，在编译期不需要知道任何信息。

当通过反射与一个未知类型的对象打交道时，JVM只是简单地检查这个对象，看它属于哪个特定的类（与RTTI一样）。RTTI与反射之间的区别只在于：对RTTI来说，编译器在编译时打开和检查.class文件，可以用普通方式调用对象的所有方法；而对于反射机制来说，.Class文件在编译时是不可获取的，只能在运行时打开和检查.class 文件。

参考资料

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

For “(()”, the longest valid parentheses substring is “()”, which has length = 2.

Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

https://leetcode.com/problems/longest-valid-parentheses/

解法一

使用一个栈保存字符串中字符的下标，扫描字符串，如果字符串与栈顶元素指向的字符配对，则弹出栈顶元素，并计算当前坐标与当前栈顶元素之间的距离，该距离即为当前匹配字符串长度。如果不匹配则将当前字符下标压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int longestValidParentheses(String s) {
    if(s == null) return 0;
    
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    
    int result = 0;
    for(int i = 0; i < s.length(); ++i) {
        int top = stack.peek();
        if(s.charAt(i) == ')' && top != -1 && s.charAt(top) == '(') {
            stack.pop();
            result = Math.max(result, i - stack.peek());
        } else
            stack.push(i);
    }
    return result;
}

解法二

使用动态规划，用一个数组longest记录已经匹配的结果，longest[i]表示以i结尾的字串中最长匹配长度。每次计算longest[i]时，需要加上包含在匹配括号内部的长度，以及加上匹配括号左边的长度。当s[i] == ‘)’ && s[i - longest[i - 1] - 1] == ‘(‘ 时发生转移，转移方程为：
longest[i] = longest[i - 1] + 2; (i - longest[i-1] - 2 < 0)
longest[i] = longest[i - 1] + 2 + longest[i - longest[i - 1] - 2]; (i - longest[i-1] - 2 >= 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int longestValidParentheses(String s) {
    if(s == null) return 0;
    
    int result = 0;
    int[] longest = new int[s.length()];
    for(int i = 1; i < s.length(); ++i) {
        int left = i - longest[i - 1] - 1;
        if(s.charAt(i) == ')' && left >= 0 && s.charAt(left) == '(') {
            longest[i] = longest[i - 1] + 2 + (left - 1 >= 0 ? longest[left - 1] : 0);
            result = Math.max(result, longest[i]);
        }
    }
    
    return result;
}

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public int myAtoi(String str) {
    if(str == null) return 0;
    //清除字符串首尾空格
    str = str.trim();
    if(str.length() == 0) return 0;
    
    boolean positive = true;
    int index = 0;
    long result = 0;
    
    //确定符号位并向后扫描一位
    if(str.charAt(index) == '-') {
        ++index;
        positive = false;
    } else if(str.charAt(index) == '+')
        ++index;
       
    //从符号位向后扫描，注意result = result * 10 + (c - '0')
    //这种字符串转数字的方法，这种方法只需要从前向后扫描一次
    //每次只需要一次乘法和一次加法（不用分别计算结果和基）
    while(index < str.length()) {
        char c = str.charAt(index);
        if(c >= '0' && c <= '9') {
            result = result * 10 + (c - '0');
            ++index;
        } else
        //如果遇到非数字字符，提前退出循环
            break;
        //超出Integer表示范围时，返回边界值
        if(positive && result >= Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if(!positive && (-result) < Integer.MIN_VALUE) return Integer.MIN_VALUE;
    }
    return positive ? (int) result : (int)(-result);
}

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given “aacecaaa”, return “aaacecaaa”.

Given “abcd”, return “dcbabcd”.

https://leetcode.com/problems/shortest-palindrome/

中心点扩散法

只能在字符串头部插入字符，因此需要首先找出包含头部字符的最长回文子串，然后将剩下的字符翻转后插入头部即可，采用中心点扩散法求包含头部的最长回文子串代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public String shortestPalindrome(String s) {
    int maxLen = 0;
    for(int i = 0; i < s.length(); ++i) {
        int len = scanMaxLen(s, i, i);
        if(maxLen < len)
            maxLen = len;
        len = scanMaxLen(s, i, i + 1);
        if(maxLen < len)
            maxLen = len;
    }
    StringBuilder add = new StringBuilder(s.substring(maxLen, s.length()));
    add.reverse();
    return add.append(s).toString();
}

private int scanMaxLen(String s, int l, int r){
    int i = l, j = r;
    while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
        --i;
        ++j;
    }
    if(i >= 0) return 0;
    return l == r ? (l - i) + (j - r) - 1 : (l - i) + (j - r);
}

Manacher算法

采用Manacher算法求包含头部的最长回文子串代码如下，注意p[i] - 1的值是以i为中心的最长回文子串的长度，i == p[i]时即表示以i为中心的回文子串包含首字符。

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
https://leetcode.com/problems/longest-palindromic-substring/

中心点扩散法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public String longestPalindrome(String s) {
    if(s == null || s.length() == 0) return "";
    int maxLen = 0;
    String result = null;
    for(int i = 0; i < s.length(); ++i) {
        String tmp = getPalindrome(s, i, i);
        if(maxLen < tmp.length()) {
            maxLen = tmp.length();
            result = tmp;
        }
        tmp = getPalindrome(s, i, i + 1);
        if(maxLen < tmp.length()) {
            maxLen = tmp.length();
            result = tmp;
        }
    }
    return result;
}

private String getPalindrome(String s, int beg, int end) {
    while(beg >= 0 && end < s.length() && s.charAt(beg) == s.charAt(end)) {
        --beg;
        ++end;
    }
    return s.substring(beg + 1, end);
}

Manacher算法

1. 对原字符串进行填充，使得每个字符都被两个’#’包围，这样处理，假设原字符串长度为n，那么处理后字符串长度为n + (n + 1) = 2 * n + 1，无论原字符串长度为奇数还是偶数，处理后的字符串长度一定是奇数，可以进行统一的处理。为了便于处理边界情况，在处理字符串头部和尾部分别插入两个不同于’#’的字符。
2. 遍历处理后字符串，根据前面已经计算好的对称信息，计算当前字符为中心的最长回文长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public String longestPalindrome(String s) {
    if(s == null || s.length() == 0) return "";
    String ps = process(s);
    int mx = 0, id = 0;
    int[] p = new int[ps.length()];
    for(int i = 1; i < ps.length() - 1; ++i) {
        p[i] = mx > i ? Math.min(p[2 * id - i], mx - i) : 1;
        while(ps.charAt(i + p[i]) == ps.charAt(i - p[i]))
            ++p[i];
        if(mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
    }
    int maxLen = 0, index = 0;
    for(int i = 1; i < ps.length(); ++i) {
        if(maxLen < p[i]) {
            maxLen = p[i];
            index = i;
        }
    }
    int beg = index - (maxLen - 1);
    int end = index + (maxLen - 1);
    return s.substring((beg - 1) / 2, (end - 1) / 2);
}

private String process(String s) {
    StringBuilder sb = new StringBuilder();
    sb.append('$');
    for(int i = 0; i < s.length(); ++i) {
        sb.append('#');
        sb.append(s.charAt(i));
    }
    sb.append('#');
    sb.append('^');
    return sb.toString();
}

参考资料

Longest Palindromic Substring 最长回文子串

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
https://leetcode.com/problems/median-of-two-sorted-arrays/

分析：
对于一个数x和连个排好序的数组a，b。如果x在a中是第ax个数，在b中是第bx个数。那么，x在a，b合并后的数组中是第（ax + bx - 1）个数。

充分利用两个数组已经排好序的特征，取a中前cntA = （k * lenA /（lenA + lenB））个元素（按数组中元素比例取元素，以避免边界情况），取b中cntB = k - 1 - cntA个元素。比较a[begA + cntA]和b[begB + cntB]：

1. a[begA + cntA] == b[begB + cntB]，a[begA + cntA]即为a，b中第k个元素
2. a[begA + cntA] < b[begB + cntB]，a[begA + cntA]，丢弃a[begA ~ begA + cntA]共cntA + 1个元素
3. a[begA + cntA] > b[begB + cntB]，a[begA + cntA]，丢弃b[begB ~ begB + cntB]共cntB + 1个元素

寻找两数组中第k大元素的函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int findKth(int[] a, int[] b, int k, int begA, int endA, int begB, int endB) {
    int lenA = endA - begA + 1;
    int lenB = endB - begB + 1;
    
    if(lenA == 0) return b[begB + k];
    if(lenB == 0) return a[begA + k];
    if(k == 0) return Math.min(a[begA], b[begB]);
    
    int cntA = k * lenA / (lenA + lenB);
    int cntB = k - 1 - cntA;
    
    if(a[begA + cntA] == b[begB + cntB]) return a[begA + cntA];
    else if(a[begA + cntA] < b[begB + cntB]) {
        k = k - cntA - 1;
        begA = begA + cntA + 1;
        endB = begB + cntB;
    } else {
        k = k - cntB - 1;
        begB = begB + cntB + 1;
        endA = begA + cntA;
    }
    return findKth(a, b, k, begA, endA, begB, endB);
}

寻找两数组中位数的主函数为：

1
2
3
4
5
6
7
8
9

public double findMedianSortedArrays(int[] a, int[] b) {
    int lenA = a.length, lenB = b.length;
    if((lenA + lenB) % 2 == 0) {
        return  (findKth(a, b, (lenA + lenB) / 2, 0, lenA - 1, 0, lenB -1) + 
        findKth(a, b, (lenA + lenB) / 2 - 1, 0, lenA - 1, 0, lenB - 1)) * 0.5;
    } else {
        return (double)findKth(a, b, (lenA + lenB) / 2, 0, lenA - 1, 0, lenB - 1);
    }
}

MySQl中，索引在存储引擎层实现而不是服务器层，

B-Tree索引

B-Tree（参考B-Tree，B+Tree）对索引列是按顺序组织存储的，所以很适合查找范围数据、全键值或键前缀查找。索引对多个值进行排序的依据是CREATETABLE语句中定义索引的顺序。B-Tree索引有以下限制：

1. 如果不是按照索引的最左列开始查找，则无法使用索引
2. 不能跳过索引中的列
3. 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查询。

哈希索引

哈希索引（Hash Index）基于哈希表实现，只有精确匹配所有列的查询才有效。哈希索引的结构非常紧凑，也使得哈希索引的速度非常快。但是，哈希索引也有它的限制：

1. 哈希索引只包含哈希值和行指针，不存储字段值。所以，不能使用索引中的值来避免读取行。
2. 哈希索引不是按照索引值顺序存储的，无法用于排序
3. 哈希索引也不支持部分索引列匹配查找
4. 哈希索引只支持等值比较查询
5. 当出现冲突时，需要遍历桶中的所有行指针，性能会有所下降

索引策略

独立的列

如果查询中的列不是独立的，MySql就不会使用索引，独立的列是指索引列不能使表达式的一部分。例如，SELECT id FROM user WHERE id + 1 = 5就无法使用id上的索引。

B-Tree

B-Tree即B树，是一种为磁盘等存储设备而设计的多路平衡查找树，很多数据库系统都使用了B树或者B树的各种变种来存取信息（InnoDB使用了B+树）。
m阶B树的定义

1. 树中每个节点最多含有m（m >= 2）个孩子
2. 除根节点和叶节点外，每个节点最少有ceil（m/2）个孩子
3. 若根节点不是叶节点，那么根节点最少有2个孩子
4. 所有叶节点位于同一层，叶节点中不包含任何信息，可以当做外部节点或者查询失败的节点
5. 每个非叶节点的节点包含n个关键字信息：n，p0，k1，p1，k2……p（n-1），k（n-1），pn，kn。其中，k（1…n）表示关键字，同一个节点中的关键字按递增次序排列，p(0…n)表示指向子树的指针，pi指向的子树中的所有关键字的值都大于p（i-1）并且小于p（i）。

B+树

B+树是应文件系统所需而产生的一种B-树的变形树。一棵m阶的B+树和m阶的B树的差异在于：

1. 有n 棵子树的结点中含有n 个关键码；
2. 所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。
3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大关键码。

通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始查找。

在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时，若非终端结点上的关键码等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

参考资料

B树，B+树，B*树
B树、B+树的应用