归并排序
导论第二章再讲时间复杂度的计算，通过写插入排序( 插入排序与循环不变式 )讲了循环的时间复杂度的计算，而接着通过归并排序介绍分治法以及分治法的时间复杂度。
A = [2, 5, 1, 3, 7, 6]
def merge_sort(nums, start, end):
if end <= start + 1:
return nums
m = (start + end ) / 2
merge_sort(nums, start, m)
merge_sort(nums, m, end) # not m + 1
l_nums = nums[start:m]
r_nums = nums[m:end]
l_nums_len = len(l_nums)
r_nums_len = len(r_nums)
s = j = 0
for i in range(start, end):
if s < l_nums_len and j < r_nums_len:
if l_nums[s] < r_nums[j]:
nums[i] = l_nums[s]
s += 1
else:
nums[i] = r_nums[j]
j += 1
else:
break
while i < end:
if s < l_nums_len:
nums[i] = l_nums[s]
s += 1
if j < r_nums_len:
nums[i] = r_nums[j]
j += 1
i += 1
return nums
我实现的代码可能不是很 pythonic，甚至也和导论中给出的伪代码有些区别。
在这里踩得坑是注释的地方，在我执行完 merge_sort(nums, start, m) 之后，想当然的执行了 merge_sort(nums, m + 1, end)，其实这是不对的，因为这里的区间是 [start, end)，如果在运行左边部分的时候，使用 m + 1，那么在 m 那个位置上的值将被忽略掉。
插入排序与循环不变式
插入排序
《算法导论》第一部分中并没有详细讲解某一种算法，而是以讲解算法这个概念，而插入排序是讲解算法基础的例子。
输入： n 个数的一个序列 <a1, a2, ..., an>。
输出： 输入序列的一个排列 <a1', a2', ..., an'>
因为算法很简单，就直接上代码：
A = [2, 5, 1, 3, 7, 6]
def instertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key: # compare nums[j] and key
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key # set nums[j + 1] is key
return nums
if __name__ == '__main__':
print(instertion_sort(A))
下午看完了第二章第二节之后，晚上尝试完全凭记忆敲这段代码，结果还是出了两个问题，就是我打注释的两个地方。
第一个是 while 的判断条件，j 的临界条件是不小于 0，可能因为导论的数组是从 1 开始的，进过我已经意识到了，在写 range 的时候就意识到了，但是我手写的时候依然写的是 j > 0，可能只是下意识的担心越界。
第二个地方就是 nums[j + 1] = key，我一开始的时候写的是，nums[i] = key，这个应该是纯粹脑残了，因为 while 以 key 为基准，对前 i 个数字排排坐，而 key 最后落座在哪里，是通过 while 循环跑出来的，也就是说是和 j 的值相关。
循环不变式
对于循环不变式这个概念，导论引入的的确有点突兀，不过在看了一些人有趣的解释之后也算是明白了（比如知乎的这个讨论：https://www.zhihu.com/question/26700198 ）
循环不变式是验证循环正确性的一种方法，关注循环体中的主要的属性（比如在插入排序中 nums[0...i-1] 这段数字是保持递增的属性），如果这种属性能在开始循环时，循环中，结束循环后，都一直保持，那么我们就认为这个循环是正常工作的。
在算法导论中尝试使用数学归纳法来验证这个循环：
初始化： 循环得第一次迭代之前，它为真
保持： 如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
终止： 在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。
因为这三个状态（开始，进行，结束），nums[0...i-1] 始终保持了递增这一个属性，因此验证了插入排序这个算法的正确性。
KMP算法next数组活用之前后缀问题
确切的说这是一篇解题报告（SDUTOJ 2784：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2784）。
前置技能 KMP字符串匹配算法: KMP字符串匹配算法
正如题目中描述：
你的任务是找出一个字串s，s既是String的前缀，又是String的后缀，并且s也出现在String的中间部分（既不是前缀，也不是后缀），s的长度越长越好。
很明显这是一道KMP算法周边题目，说是KMP算法是因为需要计算next数组，说是周边是因为这并不是一道匹配类型的题目。
正如《KMP字符串匹配算法》所说，next数组的目的是保存的匹配过的 S 串中还有多少直接等于 T 串的。但实际上，next中的数值的含义在不同的使用场景还有很多种理解。
比如求前后缀的题目中，我们就可以把next中的数组看做在next[i]（next[i]！=0 and next[i] != -1）出，存在重复的字段String[0,next[i]]。
而对于这个题目，对于长度为len-1的字符串，那么next数组的长度为len。
如果在next数组中，如果next[len]为0，这可以说明不存在后缀和前缀相同的情况。如果next[len]不为0，这说明前缀和后缀相同，但是还不能说明中间存在这一循环体。
如果next[len]不为0，而且存在和next[len]一样的值，也就是说在在字符串中间出现了循环题，也就可以断定存在符合题目要求的字符串，而长度就是next[len]（也就是后缀和前缀共同的长度）。
但如果串是一个循环串，比如像"papapapa"这种，那么next是递增的。因此不能用上段的方式判断十分满足题目要求。
因此需要判断出去最短循环节之后时候还是循环串。而除去最短循环串，便是String[0,next[len]]。因此，在该串的基础上进行判断，也就是判断next[next[i]]十分还是一个有效的值（非0和非-1），如果有效，说明依然存在字段重复。
因此这个题目就非常清楚了：只需要寻找next[i] == next[len]和判断 next[next[len]] != 0 且 next[next[len]] != -1。
把KMP相关算法封装，这个题目的核心代码就变成了：
/**
* SDUTOJ 2748
* Created by hypo on 15-11-15.
*/
class TestString{
private String str;
private int[] next;
//初始化 顺便获得next数组
public TestString(String str) {
this.str = str;
next = getNext();
}
//获取next数组
private int[] getNext(){
char[] chars = this.str.toCharArray();
int len = chars.length;
int[] next = new int[len + 1];
int k = -1, i = 0;
next[0] = -1;
while(i < len){
if(k == -1 || chars[k] == chars[i]){
i++;
k++;
next[i] = k;
}else{
k = next[k];
}
}
return next;
}
//获得结果 null表示不符合题目要求
public String getAns(){
int len = this.str.length();
if(next[len] == 0){
return null;
}
for(int i = 0;i < len;i++){
if(this.next[i] == next[len]){
return this.str.substring(0,next[len]);
}
}
if (next[next[len]] != 0 && next[next[len]] != -1)
{
return this.str.substring(0,next[next[len]]);
}
return null;
}
}
Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.