归并排序

导论第二章再讲时间复杂度的计算,通过写插入排序( 插入排序与循环不变式 )讲了循环的时间复杂度的计算,而接着通过归并排序介绍分治法以及分治法的时间复杂度。

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 那个位置上的值将被忽略掉。

2017/7/5 posted in  算法&数据结构

插入排序与循环不变式

插入排序

《算法导论》第一部分中并没有详细讲解某一种算法,而是以讲解算法这个概念,而插入排序是讲解算法基础的例子。

输入: 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] 始终保持了递增这一个属性,因此验证了插入排序这个算法的正确性。

2017/6/29 posted in  算法&数据结构

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;
    }
}
2015/11/17 posted in  算法&数据结构

KMP字符串匹配算法

KMP是一种不太常用的字符串匹配算法,但是在某些情况下,依然可以发挥作用,而它的next思想,更是可以应用在别的地方。

这是我第三次总结KMP算法,第一次是在ACM集训后填坑期间,第二次是在学《数据结构》补充笔记的时候,因为三次的目的不同,这次的侧重点应该是KMP算法本身,希望写出来的总结能对周老师和大家有些许帮助。

朴素算法

在说KMP算法前,必然要说朴素算法,也就是我们常用的字符串匹配算法。

假设我们有一个S串和一个T串,我们需要判断S串中是否包含一个T串,或者找到T串首次出现的位置等操作。一般情况下,我们会进行如下的操作:

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        char[] S = scanner.next().toCharArray();
        char[] T = scanner.next().toCharArray();

        boolean isFind = false;
        for(int i = 0;i < S.length;i++){

            isFind = true;
            for(int j = 0, ti = i;j < T.length;j++, ti++){
                
                if(ti == S.length){
                    isFind = false;
                    break;
                }
                
                if(S[ti] != T[j]){
                    isFind = false;
                    break;
                }
            }

            if(isFind){
                break;
            }
        }

        System.out.println(isFind ? "YES" : "NO");
    }
}

当然,如果硬要说这种情况不好还想进行优化的话,可以进行优化的地方还是很多的,KMP便是针对指针回溯进行优化的算法。

什么是指针回溯

如上文的两个for循环,其中的 i,ti 和 j 分别对 S 和 T 串进行位置标记,然后进行比较等操作,我们可以把 i,ti 和 j 看做三个标记指针,而在每一轮的比较中(也就是内循环break前算作一轮比较),ti 和 j 进行不断向后移动进行比较,然而如果比较失败(发现了不同),那么,ti 就会回溯到 i + 1 的位置(当本次内循环结束,再次执行内循环时 i 已经进行了自增操作。),而 j 指针会回溯到 0 (也就是T串的开始位置),然后进行再次比较,以此重复直到找到匹配位置或者外循环结束。

如果看算法流程的话,可以更明显的看出指针回溯。

算法流程

  1. i 指向S串开始
  2. j 指向T串开始,ti 指向和 i 相同的位置
  3. 对 j 指向的字符和 ti 指向的字符判断 相同?执行4:执行6
  4. j 指针后移,ti指针后移
  5. j 或 ti 指向 S 或 T 串的结尾 ? 执行6:执行3
  6. i 自增
  7. i 指向S串的结束?执行8:执行2
  8. 打印结果

改良方向假设

很明显,如果我们可以做到两个指针减少回溯,或者保证一个不回溯,是不是就可以减少无用的匹配。

为了方便说明,我们可以举一个极端的栗子:

对于S串和T串是上图的样子,如果使用朴素算法,在匹配失败的时候,i指针(现在指向S串的第10个元素'a')应该会回溯到S串的第4个元素 'b' 上,而 j 指针,也会从T串的第8个元素'c',回溯到T串的第1个元素'a'上,然后进行重新循环比较。

而我们很明显可以看出来,这并不是最佳方案,最佳方案应该是i指针稳住不动,继续指向第10个元素,而j指针回溯到第1个元素上。因为很明显,i在前10个元素处不会有全匹配。

当然,这是我们已经可以一眼看到全局而能做出的最佳方案,而程序是不可能眼观全局的,但不意味着程序做不出这样的判断。

我们假设程序虽然不知道S串后面是什么样子,但已经知道了 T 串的构造和 T 串与 S 串已经匹配的部分,那么就应该可以做到清楚的知道指向 T 串的 j 指针应该怎么移动而可以避免回溯指向 S 串的 i 指针。

那么,如果上面说的不是神话,则明白 T 串的构造便是实现上述想法的关键。

因此,KMP算法诞生了。

KMP算法

终于讲到正题了,正如上文所说,与朴素算法相比,KMP算法多了对 T 串的构造进行分析,从而诞生了next数组。而next数组,便是整个KMP算法的核心,不仅仅是字符串匹配,在前缀,后缀,循环节判断等方面,next也能发挥重大作用。

next数组的意义

要想清楚什么是next数组,next数组的意义,切入点便是next数组在匹配中起到的作用。

还是这张图,朴素算法的缺点是什么呢,就是说:匹配过的就是做的无用功,不管你匹配多么长,都是按照没匹配过,无情的从开头再来一遍,这就导致了时间的浪费

如果我们匹配过以前的,不再放弃了,而是利用匹配过的信息推导出有用的信息。目的就是:匹配过的 S 串中还有多少直接等于 T 串的 ,假设知道了这个信息,是不是将会节省不少事件。

因此,next中就是保存的匹配过的 S 串中还有多少直接等于 T 串的

假设我们开始匹配的时候i指针指向了S[e],j指针指向T[0],进行了k次比较之后发现不同,也就是比对失败了,我们是不是可以得出结论:S[e,e+k] = T[0,k]

而如果我们的next数组已经记录了匹配过的S串中还有多少直接等于T串的,假设这个值为t,那么是不是也就意味着:S[e',e'+k] = T[0,t]。

如下图所示:

利用意义上的 next 数组得出 kmp 算法

定义: 此字符串的开头到某一位置称为这个字符串的前缀,,从某一个位置到这个字符串的最后位置称为这个字符串的后缀。

于是,我们需要截取所有的前缀来匹配后缀,因为 T 串在匹配时可能会用到各式各样的前缀,我们 next[]数组就是为了,一个前缀一个最大前后缀匹配值。

因此,求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;
}

(这是从今天的KMP题目SDUTOJ 2784中直接取出来的一个方法)

有了next数组后,当失配时,固定 i 指针不动,直接利用 T 串的 next 值滑,将我们知道的信息(我们知道到哪里的前缀和后缀相等)再次验证一遍来浪费时间。

那么我们的匹配算法就可以写作下面这个样子:

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        char[] S = scanner.next().toCharArray();
        char[] T = scanner.next().toCharArray();

        boolean isFind = false;
        int j = 0;
        for(int i = 0;i < S.length;i++){
            
            if(j == T.length){

                isFind = true;
                break;
            }
            if(S[i] == T[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }

        System.out.println(isFind ? "YES" : "NO");
    }
}

由两个for循环嵌套变成一个是不是很爽的样子!!

当然,这只是next的常规用法(字符串匹配),而next的灵活用法还有很多(比如刚才说的前缀后缀什么的,还包括SDUTOJ 2784)。

结束语

这篇文章只是KMP总结和next数组的介绍,作为SDUTOJ 2784解题报告的前置技能 _(:з」∠)_。

文中插图/定义引用了王政(@9cai)同学在队期间写的《Kmp 算法引论》(好流弊的名字_),因为Linux下做图片麻烦,也懒得去做图片了。

文章写成仓促,重点放在KMP与朴素算法比较和next的引入上,可能文章中存在些许问题,欢迎指正。

最后,引用我第二次对KMP总结文的内容作为结束语:

  1. 传统算法(朴素算法)最坏情况是O(nm),但一般是在O(n+m),也不是太坏,所以一般没有特殊要求的程序还在用这种算法;
  2. KMP算法在有大量重复的情况下优化明显,对主串较大时比较有效;
  3. next函数还是有缺陷的,比如模式串’aaaab’与主串’aabaaaab’匹配时,用时几乎和朴素算法一样;
  4. 以发展的眼光看问题,其实作为常用算法之一,匹配算法也有发展,KMP已经不是主流。
2015/11/16 posted in  算法&数据结构

有关双向BFS的一次尝试

什么是双向BFS

双向BFS在寒假解决图论中搜索问题时就已经遇到了,单向BFS是从一个起点到一个终点搜索,找最短路,而双向BFS是不仅从起点到终点搜索,而且同时从终点出发,向起点进行搜索。双向BFS看起来能快很多。

当时和龙哥讨论,感觉双向BFS理论上不会快到哪去,毕竟搜索就是枚举的过程,加上当时我还不会双向BFS,就没有细究。

双向BFS为什么快

昨天开始学双向BFS并拿了一个题进行试验,发现双向BFS的确快(有图有真相):

第一次提交(11:46)是用普通的BFS写的,然后在普通的BFS基础上改为了双向BFS然后提交发现确实快了。

双向BFS为什么快本身就是个很奇妙的问题,有两张图也许能很好的说明问题:


单向BFS(上图)


双向BFS(上图)

(图出自:红黑联盟

如果把搜索看成一个圆,那么圆的面积可以看做能表示搜索次数的一个值。而起点s和终点e之间的距离可以大体看为园的半径。

对于单向BFS(第一个图)来说,假设路径为L,那么搜索次数为 LLPI(PI为圆周率)。

对于双向BFS(第二个图)来说,假设路径为L,那么搜索次数为2(L/2)(L/2)*PI。

相比较来说,的确可以节省很多时间,而能节省多少是根据图的大小和L的大小来决定的,图越大,L越小,节省时间越明显。

双向BFS怎么实现

双向BFS有好几种实现,我只说我自己用的这种。

先贴出HDU1195题的单向BFS和双向BFS代码,不同之处显而易见:

单向:

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

struct Node
{
    int num;
    int t;
};

int bj[10000];

void fen(int num[4],int n)
{
    num[0] = n / 1000;
    num[1] = (n / 100) % 10;
    num[2] = (n / 10) % 10;
    num[3] = n % 10;
}

int he(int num[4])
{
    int sum = 0;

    for(int i = 0;i < 4;i++)
        sum = sum * 10 + num[i];

    return sum;
}

int bfs(int s,int e)
{
    queue<Node> que;

    while(!que.empty())
        que.pop();

    Node now,tmp;

    now.num = s;
    now.t = 0;
    que.push(now);
    bj[now.num] = 1;

    while(!que.empty())
    {
        now = que.front();
        que.pop();

        if(now.num == e)
            return now.t;

        int tn[4];
        //枚举每一位
        for(int i = 0;i < 4;i++)
        {
            //加一
            fen(tn,now.num);
            tn[i] += 1;

            if(tn[i] == 10)
                tn[i] = 1;

            tmp.num = he(tn);
            tmp.t = now.t + 1;

            if(bj[tmp.num] == 0)
            {
                bj[tmp.num] = 1;
                que.push(tmp);
            }

            //减一
            fen(tn,now.num);
            tn[i] -= 1;

            if(tn[i] == 0)
                tn[i] = 9;

            tmp.num = he(tn);
            tmp.t = now.t + 1;

            if(bj[tmp.num] == 0)
            {
                bj[tmp.num] = 1;
                que.push(tmp);
            }
        }

        //交换相邻两个数位置
        for(int i = 0;i < 3;i++)
        {
            fen(tn,now.num);

            tn[i] ^= tn[i + 1];
            tn[i + 1] ^= tn[i];
            tn[i] ^= tn[i + 1];

            tmp.num = he(tn);
            tmp.t = now.t + 1;

            if(bj[tmp.num] == 0)
            {
                bj[tmp.num] = 1;
                que.push(tmp);
            }
        }

    }
    return -1;
}

int main()
{
    int N;
    cin >> N;

    while(N--)
    {
        int num1,num2;
        memset(bj,0,sizeof(bj));

        cin >> num1 >> num2;

        int ans = bfs(num1,num2);

        cout << ans << endl;
    }
}

双向:

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

struct Node
{
    int num;
    int t;
};

int bj[10000];
int ti[10000];

void fen(int num[4],int n)
{
    num[0] = n / 1000;
    num[1] = (n / 100) % 10;
    num[2] = (n / 10) % 10;
    num[3] = n % 10;
}

int he(int num[4])
{
    int sum = 0;

    for(int i = 0;i < 4;i++)
        sum = sum * 10 + num[i];

    return sum;
}

int bfs(int s,int e)
{
    queue<Node> que;

    while(!que.empty())
        que.pop();

    Node now,tmp;

    now.num = s;
    now.t = 0;
    que.push(now);
    bj[now.num] = 1;
    now.num = e;
    now.t = 0;
    que.push(now);
    bj[now.num] = 2;

    while(!que.empty())
    {
        now = que.front();
        que.pop();

        int tn[4];
        //枚举每一位
        for(int i = 0;i < 4;i++)
        {
            //加一
            fen(tn,now.num);
            tn[i] += 1;

            if(tn[i] == 10)
                tn[i] = 1;

            tmp.num = he(tn);
            tmp.t = now.t + 1;

            if(bj[tmp.num] == 0)
            {
                bj[tmp.num] = bj[now.num];
                ti[tmp.num] = tmp.t;
                que.push(tmp);
            }else if(bj[tmp.num] != bj[now.num])
            {
                return ti[tmp.num] + ti[now.num] + 1;
            }

            //减一
            fen(tn,now.num);
            tn[i] -= 1;

            if(tn[i] == 0)
                tn[i] = 9;

            tmp.num = he(tn);
            tmp.t = now.t + 1;

            if(bj[tmp.num] == 0)
            {
                bj[tmp.num] = bj[now.num];
                ti[tmp.num] = tmp.t;
                que.push(tmp);
            }else if(bj[tmp.num] != bj[now.num])
            {
                return ti[tmp.num] + ti[now.num] + 1;
            }
        }

        //交换相邻两个数位置
        for(int i = 0;i < 3;i++)
        {
            fen(tn,now.num);

            tn[i] ^= tn[i + 1];
            tn[i + 1] ^= tn[i];
            tn[i] ^= tn[i + 1];

            tmp.num = he(tn);
            tmp.t = now.t + 1;

            if(bj[tmp.num] == 0)
            {
                bj[tmp.num] = bj[now.num];
                ti[tmp.num] = tmp.t;
                que.push(tmp);
            }else if(bj[tmp.num] != bj[now.num])
            {
                return ti[tmp.num] + ti[now.num] + 1;
            }
        }

    }
    return -1;
}

int main()
{
    int N;
    cin >> N;

    while(N--)
    {
        int num1,num2;
        memset(bj,0,sizeof(bj));

        cin >> num1 >> num2;

        int ans = bfs(num1,num2);

        cout << ans << endl;
    }
}

两份代码一共有两大区别,一个是标记数组,一个是记录到当前位置的距离数组。

第一个大区别就是标记,单向BFS的标记很单纯,就是标记有没有走过,而双向BFS不仅标记有没有走过,还进行区分标记,来记录到底是从起点走到当前点的还是从终点走到当前点的。也可以认为这是不同的两层搜索同时进行,分别标记。如果两层标记相遇,就认为已经找到了一条路径连通了起点和终点。

第二大区别就是距离数组,单向BFS不需要这个数组因为队列里的t变量就足够记录到当前位置的最短路(如果当前位置为终点,这个最短路就是答案)。而双向这个t的含义是从起点到当前位置的最短距离,因为有两个起点,所以不能记录两条路径(不同起点)的路径和,因此需要一个距离数组保存不同路径到当前位置的距离,当两条路径相接之后,只需要将保存接触点的距离相加便是答案。

2015/2/12 posted in  算法&数据结构