2016-09-28

数据结构

Trie树/字典树/前缀树

Trie数定义

Trie树，即字典树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

Trie树有一些特性：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。
如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
插入查找的复杂度为O(n)，n为字符串长度。

Trie树构建

假如现在给你10万个长度不超过10的单词，对于每一个单词，我们要判断它出没出现过，如果出现了，求第一次出现在第几个位置。对于这个问题，我们该怎么解决呢？

如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于10万的范围难以接受。

换个思路想：

假设我要查询的单词是abcd，那么在它前面的单词中，以b，c，d，f之类开头的显然不必考虑，而只要找以a开头的中是否存在abcd就可以了。
同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。
即如果现在有b，abc，abd，bcd，abcd，efg，hii 这6个单词，我们可以构建一棵如下图所示的树：

如上图所示，对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。

那么，对于一个单词，只要顺着他从根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。

这样一来我们查询和插入可以一起完成，所用时间仅仅为单词长度（在这个例子中，便是10）。这就是一棵trie树。

我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间，我们还可以用动态链表，或者用数组来模拟动态。而空间的花费，不会超过单词数×单词长度。

查询

Trie树是简单但实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时，就是Trie开始。本质上，Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。和普通树不同的地方是，相同的字符串前缀共享同一条分支。

下面，再举一个例子。给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：2

可以看出：

每条边对应一个字母。
每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀”a”，所以他们共享从根节点到节点”a”的边。

查询操纵非常简单。比如要查找int，顺着路径i -> in -> int就找到了。

搭建Trie的基本算法也很简单，无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边。比如要插入单词add，就有下面几步：

考察前缀”a”，发现边a已经存在。于是顺着边a走到节点a。
考察剩下的字符串”dd”的前缀”d”，发现从节点a出发，已经有边d存在。于是顺着边d走到节点ad
考察最后一个字符”d”，这下从节点ad出发没有边d了，于是创建节点ad的子节点add，并把边ad->add标记为d。

问题实例

1、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析

提示：用trie树统计每个词出现的次数，时间复杂度是O(n*logle)（le表示单词的平均长度），然后是找出出现最频繁的前10个词。当然，也可以用堆来实现，时间复杂度是O(n*log10)。所以总的时间复杂度，是O(n*logle)与O(n*log10)中较大的哪一个。

2、寻找热门查询

原题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

提示：利用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

2016-09-28

数据结构

红黑树详解

定义

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

特性

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

应用

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

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

基本操作

###

2016-09-27

Algorithm

排序算法之计数排序

待排序的数要满足一定的范围的整数，比如 [0~100]，[10000~19999] 这样的数据，而且计数排序需要比较多的辅助空间，仅适用于数据比较集中的情况。

基本思想是：对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数。

需要三个数组:

待排序数组 int[] arr = new int[]{4,3,6,3,5,1};
辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1
输出数组 int[] res = new int[arr.length];

步骤：

建一个长度为K+1的的数组C，里面的每一个元素初始都置为0(Java里面默认就是0)。
遍历待排序的数组，计算其中的每一个元素出现的次数，比如一个key为i的元素出现了3次，那么C[i]=3。
累加C数组，获得元素的排位，从0开始遍历C, C[i+1]=C[i]+C[i-1]
建一个临时数组T，长度与待排序数组一样。从数组末尾遍历待排序数组，把元素都安排到T里面，直接从C里面就可以得到元素的具体位置，不过记得每处理过一个元素之后都要把C里面对应位置的计数减1。

计数排序的时间复杂度也是O(n)，稳定排序算法。

public class CountSort {

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

        int max = max(arr);

        int[] count = new int[max+1];
        Arrays.fill(count, 0);

        for(int i=0; i<arr.length; i++) {
            count[arr[i]] ++;
        }

        int k = 0;
        for(int i=0; i<=max; i++) {
            for(int j=0; j<count[i]; j++) {
                arr[k++] = i;
            }
        }
    }

    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int ele : arr) {
            if(ele > max)
                max = ele;
        }
        return max;
    }
}

2016-09-26

Algorithm

排序算法之归并排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序的时间复杂度也是O(nlogn)，稳定排序方式。

public class MergeSort {
    public static void mergeSort(int [] array) {
        divide(array, 0, array.length-1);
    }

    public static void divide(int [] array, int left, int right) {
        if (left == right) {
            return ;
        }
        int middle = (left + right) / 2;
        divide(array, left, middle);
        divide(array, middle+1, right);
        merge(array, left, middle, right);
    }

    public static void merge(int [] array, int left, int middle, int right) {
        //[left, middle][middle+1, right]
        int[] tempArray = new int[right - left + 1];

        int i = left;
        int j = middle + 1;
        int k = 0;

        //把较小的数先移到tempArray
        while (i <= middle && j <= right) {
            if (array[i] < array[j]) {
                tempArray[k++] = array[i++];
            }else {
                tempArray[k++] = array[j++];
            }
        }
        //把左边或者右边剩余数组移入新数组
        while(i < middle)
            tempArray[k++] = array[i++];
        while(j < right)
            tempArray[k++] = array[j++];

        //一次遍历，新数组覆盖原数组
        for (int m = 0; m < tempArray.length; m++) {
            array[m + left] = tempArray[m];
        }
    }
}

2016-09-25

Algorithm

排序算法之希尔排序

希尔排序（缩小增量插入排序）
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

public class ShellSort {
	public static void shellSort(int[] array) {
		if (array == null || array.length == 0) 
			return ;
		//每次将步长缩短为原来的一半
		for (int increment = array.length / 2; increment > 0; increment /= 2) {
			for (int i = increment; i < array.length; i++) {
				int temp = array[i];
				for (int j = i; (j >= increment) && (temp < array[j - increment]); j -= increment) {
					array[j] = array[j-increment];
				}
				array[j] = temp;
			}
		}
	}
}

2016-09-24

Algorithm

排序算法之堆排序

堆排序是一种树形选择排序方法，它的特点是：在排序的过程中，将array[0，…，n-1]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（最小）的元素。

若array[0，…，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下

任意一节点指针 i：
父节点：i==0 ? null : (i-1)/2
左孩子：2i + 1
右孩子：2i + 2
堆的定义：n个关键字序列array[0，…，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)
- array[i] <= array[2i + 1] 且 array[i] <= array[2i + 2]；称为小根堆；
- array[i] >= array[2i + 1] 且 array[i] >= array[2i + 2]；称为大根堆；
建立大根堆：

n个节点的完全二叉树array[0，…，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆。

对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。

之后向前依次对各节点（(n-2)/2 - 1）~ 0为根的子树进行调整，看该节点值是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构建下一级的堆，直到以该节点为根的子树构成堆为止。

反复利用上述调整堆的方法建堆，直到根节点。

4.堆排序：（大根堆）
　　1. 将存放在array[0，…，n-1]中的n个元素建成初始堆；
　　2. 将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；
　　3. 但此时堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再重复第②③步，直到堆中仅剩下一个元素为止。

堆排序算法的性能分析：

空间复杂度:O(1)；
时间复杂度:建堆：O(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);
稳定性：不稳定

public class HeapSort {

    //将元素array[k]自上往下逐步调整树形结构
	public static void heapAdjust(int[] array, int k, int length) {
        int temp = array[k];
        //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
        for(int i = 2 * k + 1; i < length -1  ; i = 2 * i + 1) {
            //左右孩子的节点分别为2*i+1,2*i+2

            //选择出左右孩子较小的下标
            if(i < length && array[i] < array[i+1]) {
                i ++; //如果节点的右孩子>左孩子，则取右孩子节点的下标
            }
            if(temp >= array[i]) { //根节点 >=左右子女中关键字较大者，保持稳定
                break; 
            }else {
                array[k] = array[i]; //将子节点上移
                k = i; //【关键】修改k值，以便继续向下调整
            }
        }
        array[k] = temp; //插入正确的位置
    }

    public static void heapSort(int[] array) {
        if(array == null || array.length == 0)
            return ;
        //建堆：从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            heapAdjust(array, i, array.length);
        }
        //排序过程
        for(int i=array.length-1; i>0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            heapAdjust(array, 0, i);//整理，将剩余的元素整理成堆
        }

    }
}

2016-09-23

Algorithm

排序算法之快速排序

基于分治的思想，是冒泡排序的改进型。

首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，

首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值
然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环
直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了
以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了

快速排序的时间复杂度也是O(nlogn)

public class QuickSort {
	//查找基准点所在位置，并划分为左右两半
	public static int partition(int [] array, int low, int high) {
		int key = array[low];//固定基准点的划分方式,数组第一个数
		while(low < high) {
			while(low < high && array[high] >= key) //从后向前扫描，找到小于key的值
				high --;
			array[low] = array[high];
			while(low < high && array[low] <= key)  //从前向后扫描，找到大于key的值
				low ++;
			array[high] = array[low];
		}
		array[high] = key;//跳出循环后low==high
		return high;

	}
	//递归形式的分治排序算法
	public static void quickSort(int[] array, int low, int high) {
		if(low > high)
			return ;
		int keyIndex = partition(array, low, high);
		quickSort(array, low, keyIndex-1);
		quickSort(array, keyIndex+1, high);
	}

	//快速排序调用
	public static void quick(int[] array) {
		if (array != null && array.length != 0) {
			quickSort(array, 0, array.length-1);
		}
	}
}

2016-09-22

Algorithm

排序算法之插入排序

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置中

简单插入排序的时间复杂度也是O(n^2)

public class InsertSort {
	public static void insertSort(int[] array) {
		if(array == null || array.length == 0)
			return ;
		for (int i = 1; i < array.length; i++) {
			int j = i;
			int temp = array[i];
			for(int j = i; (j > 0) && (temp < array[j-1]); j--) //比较并将大于target的数后移
				array[j] = array[j-1];
			//将target插入合适位置
			array[j] = temp;
		}
	}
}

2016-09-21

Algorithm

排序算法之选择排序

在未排序序列中找到最小元素，并与待排序列的首位进行交换。
选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

选择排序的时间复杂度为O(n^2)

public class SelectSort {
	public static void selectSort(int [] arr) {
		if(arr.length == 0 || arr == null)
			return ;
		int minIndex = 0;
		for(int i = 0; i < arr.length-1; i++) {
			minIndex = i;
			for (int j = i+1; j < arr.length-i-1; j++) {
				if (arr[minIndex] > arr[j])
					minIndex = j;
			}
			if(minIndex != i)
				swap(arr, i, minIndex);
		}
	}

	public void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}

2016-09-21

Java

SpringMVC学习

什么是SpringMVC？