问答项目笔记

Day1

参数解析

1
2
3

@Controller
public class IndexController {
    @RequestMapping("/") 
    @ResponseBody public String index() {
        return "Hello NowCoder"; 
    }
}

1
2
3
4
5

@RequestMapping(value = "/profile/{groupId}/{userId}") 
@ResponseBody
public String profile(@PathVariable("groupId") String groupId,
        @PathVariable("userId") int userId,
        @RequestParam(value = "type", defaultValue = "1") int type,
        @RequestParam(value = "key", defaultValue = "nowcoder") String key) {
    return String.format("{%s},{%d},{%d},{%s}", groupId, userId, type, key);

Read More

Velocity笔记

参考：http://velocity.apache.org/engine/devel/user-guide.html

1.变量

(1)变量的定义：

1

#set($name = "hello")     说明：velocity中变量是弱类型的。

Read More

判断单链表里面有没有环系列

1.判断单链表是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。

2.求有环单链表的环长

在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：
环长=2*len-len。

3.求有环单链表的环连接点位置

第一次碰撞点Pos到连接点Join的距离 = 头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。

在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。

第一次相遇时，slow走的长度 S = LenA + x;

第一次相遇时，fast走的长度 2S = LenA + n*R + x;

所以可以知道，LenA + x = n*R;　　LenA = n*R -x 　

4.求有环单链表的链表长

2中求出了环长，3中求出了连接点的位置，相加就是链表长。

5.如何判断两个链表（不带环）是否相交

将其中的一个链表首尾相连，然后判断另一个链表是否带环即可。

判断单链表里面有没有环系列问题

1.判断单链表是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。

2.求有环单链表的环长

在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：
环长=2*len-len。

3.求有环单链表的环连接点位置

第一次碰撞点Pos到连接点Join的距离 = 头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。

1. 当fast与slow相遇时，show肯定没有走完链表，而fast已经在还里走了n（n>= 1）圈，设环长为R。假设slow走了S步，那么fast走了2S步。fast的步数还等于S走的加上环里转的n圈，所以有：2S = S + nR。因此，S = nR。
2. 设整个链表长为L，入口据相遇点lenB，起点到入口的距离为lenA。因为slow指针并没有走完一圈，所以：lenA + lenB = S，带入第一步的结果，有：lenA + lenB = nR = (n-1)R + R = (n-1)R + L - lenA；即：lenA = (n-1)R + L - lenA - lenB;即从头结点到入口的距离，等于转了(n-1)圈以后，相遇点到入口的距离。因此，我们可以在链表头、相遇点各设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

4.求有环单链表的链表长

2中求出了环长，3中求出了连接点的位置，相加就是链表长。

5.如何判断两个链表（不带环）是否相交

将其中的一个链表首尾相连，然后判断另一个链表是否带环即可。

刷剑指Offer遇见一题

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。(长度不超过9(可能有字符重复),字符只包括大小写字母。)

这种全排列问题是经典的回溯法问题

回溯法，把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。经典问题有：字符串全排列，八皇后，正方体八个数等。

递归方法求全排列

对于无重复值的情况

1. 固定第一个字符，递归取得首位后面的各种字符串组合；
2. 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。

有重复值的情况

由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。

例如abb，第一个数与后面两个数交换得bab，bba。
然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！

Read More

二叉查找树 & B树 & B+树 & B*树

网上有些说法是不对的，把Binary Search Tree 和 B树的概念相混淆了，又因为 B-Tree 和 B+Tree 将B树叫做 B-树，在这里澄清这个概念。

• 二叉查找树即Binary Search Tree
• B树即 B-Tree
• B+树即 B+Tree

下面将对这些概念进行一一详解

二叉查找树/二叉搜索树

1. 所有非叶子结点至多拥有两个儿子（Left和Right
2. 所有结点存储一个关键字
3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树

二叉查找树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

如果二叉查找树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么二叉查找树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变二叉查找树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

但二叉查找树在经过多次插入与删除后，有可能导致不同的结构：

右边也是一个二叉查找树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用二叉查找树还要考虑尽可能让二叉查找树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；

实际使用的二叉查找树都是在原二叉查找树的基础上加上平衡算法，即“平衡二叉树”；如何保持二叉查找树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的策略；

B树

是一种多路搜索树（并不是二叉的）：

1. 定义任意非叶子结点最多只有M个儿子；且M>2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5. 非叶子结点的关键字个数=指向儿子的指针个数-1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子结点位于同一层；

如：（M=3）

B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B树的特性：

1. 关键字集合分布在整颗树中；
2. 任何一个关键字出现且只出现在一个结点中；
3. 搜索有可能在非叶子结点结束；
4. 其搜索性能等价于在关键字全集内做一次二分查找；
5. 自动层次控制；

由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；
所以B树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

B+树

B+树是B树的变体，也是一种多路搜索树：

1. 其定义基本与B树同，除了：
2. 非叶子结点的子树指针与关键字个数相同；
3. 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B树是开区间）；
4. 为所有叶子结点增加一个链指针；
5. 所有关键字都在叶子结点出现；

如：（M=3）

B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的特性：

1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2. 不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储关键字）数据的数据层；
4. 更适合文件索引系统；

B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

小结

二叉查找树：每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

B树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

排序算法之基数排序

基数排序（radix sorting）将所有待比较数值(正整数)统一为同样的数位长度，数位较短的数前面补零。 然后 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后， 数列就变成一个有序序列

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

public class RadixSort {
    public static void radixSort(int[] arr) {
        if(arr == null && arr.length == 0)
            return ;
        int maxBit = getMaxBit(arr);

        for(int i=1; i<=maxBit; i++) {

            List<List<Integer>> buf = distribute(arr, i); //分配
            collecte(arr, buf); //收集
        }

    }

    //分配
    public static List<List<Integer>> distribute(int[] arr, int iBit) {
        List<List<Integer>> buf = new ArrayList<List<Integer>>();
        for(int j=0; j<10; j++) {
            buf.add(new LinkedList<Integer>());
        }
        for(int i=0; i<arr.length; i++) {
            buf.get(getNBit(arr[i], iBit)).add(arr[i]);
        }
        return buf;
    }

    //收集
    public static void collecte(int[] arr, List<List<Integer>> buf) {
        int k = 0;
        for(List<Integer> bucket : buf) {
            for(int ele : bucket) {
                arr[k++] = ele;
            }
        }

    }

    //获取最大位数
    public static int getMaxBit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int ele : arr) {
            int len = (ele+"").length();
            if(len > max)
                max = len;
        }
        return max;
    }

    //获取x的第n位，如果没有则为0.
    public static int getNBit(int x, int n) {

        String sx = x + "";
        if(sx.length() < n)
            return 0;
        else
            return sx.charAt(sx.length()-n) - '0';
    }
}

堆与堆排序

堆排序与快速排序，归并排序一样都是时间复杂度为O(NlogN)的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。

二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆：

由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。

Read More

排序算法之桶排序

桶排序算是计数排序的一种改进和推广，要比计数排序复杂许多。

桶排序的基本思想：
假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶)。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。bindex=f(key) 其中，bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：
如果关键字k1 < k2，那么f(k1)<=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然，映射函数的确定与数据本身的特点有很大的关系。

对N个关键字进行桶排序的时间复杂度分为两个部分：

1. 循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。
2. 利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为 ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。

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
38

public class BucketSort {

    public static void bucketSort(int[] arr) {
        if(arr == null && arr.length == 0)
            return ;

        int bucketNums = 10; //这里默认为10，规定待排数[0,100)
        List<List<Integer>> buckets = new ArrayList<List<Integer>>(); //桶的索引

        for(int i=0; i<10; i++) {
            buckets.add(new LinkedList<Integer>()); //用链表比较合适
        }

        //划分桶
        for(int i=0; i<arr.length; i++) {
            buckets.get(f(arr[i])).add(arr[i]);
        }

        //对每个桶进行排序
        for(int i=0; i<buckets.size(); i++) {
            if(!buckets.get(i).isEmpty()) {
                Collections.sort(buckets.get(i)); //对每个桶进行快排
            }
        }

        //还原排好序的数组
        int k = 0;
        for(List<Integer> bucket : buckets) {
            for(int ele : bucket) {
                arr[k++] = ele;
            }
        }
    }
    //映射函数
    public static int f(int x) {
        return x / 10;
    }
}

红黑树详解

定义

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

特性

1. 每个节点或者是黑色，或者是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。(确保没有一条路径会比其他路径长出俩倍)

应用

主要是用它来存储有序的数据，它的时间复杂度是O(logn)，效率非常之高。

Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

基本操作

###