def subseque(s1, s2):
    res = [['0' for x in range(len(s2) + 1)] for y in range(len(s1) + 1)]
    m = [[0 for x in range(len(s2) + 1)] for y in range(len(s1) + 1)]
    # print m
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                m[i + 1][j + 1] = m[i][j] + 1
                res[i + 1][j + 1] = 'xie'
            elif m[i + 1][j] > m[i][j + 1]:
                m[i + 1][j + 1] = m[i + 1][j]
                res[i + 1][j + 1] = 'zuo'
            else:
                m[i + 1][j + 1] = m[i][j + 1]
                res[i + 1][j + 1] = 'shang'
    (i, j) = (len(s1), len(s2))
    print numpy.array(res)
    result = []
    while m[i][j]:
        c = res[i][j]
        if c == 'xie':
            result.append(s1[i - 1])
            i -= 1
            j -= 1
        if c == 'zuo':
            j -= 1
        if c == 'shang':
            i -= 1
    print result

def random_str(randomlength=20):
    str = ''
    chars = 'abcdefghigklmnopqrstuvwxyz'
    length = len(chars) - 1
    random = Random()
    for i in range(randomlength):
        str+=chars[random.randint(0, length)]
    return str

def MaxCrossSubarray(a, low, mid, high):
    left_sum=-65535
    sum=0
    for i in range(mid, low-1, -1):
        sum=sum+a[i]
        if sum>left_sum:
            left_sum=sum
            max_left=i
    right_sum=-65535
    sum=0
    for j in range(mid+1, high+1):
        sum=sum+a[j]
        if sum>right_sum:
            right_sum=sum
            max_right=j
    return (max_left, max_right, left_sum+right_sum)

def MaxSubarray(a, low, high):
    if high==low:
        return (low, high, a[low])
    else:
        mid=(low+high)/2
        (left_low, left_high, left_sum)=MaxSubarray(a, low, mid)
        (right_low, right_high, right_sum)=MaxSubarray(a, mid+1, high)
        (cross_low, cross_high, cross_sum)=MaxCrossSubarray(a, low, mid, high)
        if left_sum>=right_sum and left_sum>=cross_sum:
            return (left_low, left_high, left_sum)
        elif right_sum>=left_sum and right_sum>=cross_sum:
            return (right_low, right_high, right_sum)
        else:
            return (cross_low, cross_high, cross_sum)

a=[1,2,3,-1,5,8]
max = MaxSubarray(a, 0, len(a)-1)
print(max)

详细解释可看百度百科

下面只有python 的实现代码

def levenshtein(first, second):
    if len(first) > len(second):
        first, second = second, first
    if len(first) == 0:
        return len(second)
    if len(second) == 0:
        return len(first)
    first_length = len(first) + 1
    second_length = len(second) + 1
    distance_matrix = [range(second_length) for x in range(first_length)]
    # print distance_matrix
    for i in range(1, first_length):
        for j in range(1, second_length):
            deletion = distance_matrix[i - 1][j] + 1
            insertion = distance_matrix[i][j - 1] + 1
            substitution = distance_matrix[i - 1][j - 1]
            if first[i - 1] != second[j - 1]:
                substitution += 1
            distance_matrix[i][j] = min(insertion, deletion, substitution)
            # print distance_matrix
    return distance_matrix[first_length - 1][second_length - 1]
print levenshtein('hdsfhb','hhab')

介绍

1. 建立大顶堆
2. 然后将堆的根节点取出(一般是与最后一个节点进行交换)
3. 再将前length-1个数组重新建立大顶堆。不断重复

构建大顶堆图解

图是我用word画的，画的不好见谅

1.首先得到一个完全二叉树

2.选中第i/2个数

3.把此数与两个孩子作对比并将最大的数字放在此位置

4.然后不断向前寻找直到顶部

将根节点取出与最后一个数交换

最后将前length-1个数重新构建大顶堆不断循环

代码

 
/***
	  * 堆排序O(n*lgn)
	  * @param data
	  * @param i
	  * @param j
	  */
	 public static void swap(int[] data, int i, int j) {  
	        if (i == j) {  
	            return;  
	        }  
	        data[i] = data[i] + data[j];  
	        data[j] = data[i] - data[j];  
	        data[i] = data[i] - data[j];  
	    }  
	  
	    public  int[] heapSort(int[] data) {  
	        for (int i = 0; i < data.length; i++) { createMaxdHeap(data, data.length - 1 - i); swap(data, 0, data.length - 1 - i); // print(data); } return data; } public static void createMaxdHeap(int[] data, int lastIndex) { for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  
	            // 保存当前正在判断的节点  
	            int k = i;  
	            // 若当前节点的子节点存在  
	            while (2 * k + 1 <= lastIndex) {  
	                // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  
	                int biggerIndex = 2 * k + 1;  
	                if (biggerIndex < lastIndex) {  
	                    // 若右子节点存在，如果不存在此时biggerIndex应该等于 lastIndex  
	                    if (data[biggerIndex] < data[biggerIndex + 1]) {  
	                        // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值  
	                        biggerIndex++;  
	                    }  
	                }  
	                if (data[k] < data[biggerIndex]) {  
	                    // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k  
	                    swap(data, k, biggerIndex);  
	                    k = biggerIndex;  
	                } else {  
	                    break;  
	                }  
	            }  
	        }  
	    }  

介绍

今天呢，介绍下使用快排的思想求第k个小的数。

• 首先选中一个数字将数组中比此数字小的数字放在左边大的数字放在右边，并返回这个数字是数组中的第几位。
• 如果选中数字的位数比我们k大，则在此数字左边的序列中寻找k,否则在右边寻找，直到找到那个数字。
• 如果不存在返回-1

程序代码

/***
	 * 求第k个小的数
	 * @param arr
	 * @param st
	 * @param end
	 * @param k
	 * @return
	 */
	public int findk(int arr[],int st,int end,int k){
		if(k<0||st+k-1>end)
			return -1;//不存在第K小数  
	    if(st==end)
	    	return st;//只有一个元素  
	    int q = partition(arr,st,end);//这是枢轴的下标，我们需要知道它在[st..end]中是第几个   
	    int i = q-st+1;//枢轴是第i小数  
	    if(i==k)return i;//找到  
	    else if(i>k)return findk(arr,st,q-1,k);//如果第K小数小于第i小数，则应该在枢轴的左边继续找  
	    else return findk(arr,q+1,end,k-i);
	}
	/***
	 * 
	 * @param a
	 * @param p
	 * @param r
	 * @return
	 */
	 public int partition(int a[],int p,int r){
		 int x=a[r];
		 int tmp;
		 int middle=p;
		 for(int j=p;j