字符串匹配: KMP算法, BM_BC, BM_GS算法

字符串匹配是搜索算法的基础,也是数据结构中一个十分有用的算法分支,我在学习KMP和BMBC算法的时候就觉得听的云里雾里,但经过一些实操和分析不难发现,这几个算法都是很好理解,并且对算法有很务实启发的。

以下我从零开始梳理以下如何建立一个清晰,并且有一定模式的理解这两个算法的思路。


1. 什么是字符串匹配

从一个字符串中查询是否完全包含另一个字符串的过程。如果有则返回起始位置,无则匹配失败。 例: 在 "这是一个多美丽又遗憾的世界" 匹配 "美丽" 应该返回5. 匹配"太美丽" 失败。

前菜开始:


2. 直观解法 循环遍历

令 字符串 S = "这是一个多美丽又遗憾的世界" 模式串(待匹配子串) s = "美丽" 循环遍历S并且在每一次S[i]与 s[j=0]匹配时,依次比较 S[i++] 与 s[j++], 若成功则可以返回当前的 i-j 即为第一个字符所在的位置,失败则 i = i-j,再右移1位继续比较。

* 边界情况,当 i> m-n 时,宣告失败。 也就是说剩余可以配的元素已经不足够了,无需比较即告失败。 另外,约定查找失败时,返回-1;

算法示例:

int matchStr( char * S, char * s )
{
    size_t m = strlen(S), n = strlen(s);
    int i =0, j = 0;
    while( i < m-n+1 && j<n ){
        if( S[i] == s[j] ){
            i++;j++;
        }else{
            i -= j-1; // i = i-j+1
            j = 0;
        }
    }
    return j==n ? i-j : -1;
    // 当且仅当j与n相等时,模式串最后一位匹配成功
}
循环遍历的方式有什么问题呢? 那就是机械,无论如何都需要完整遍历S,并且每一次至少需要比对1次,而从渐进角度来说总体来说复杂度是达到O(m*n)。

接下来才是正餐:


3. 优化方向/算法策略

优化的可能性仔细分析一下,就是如何减少没必要的匹配。 首先我们看一下,模式串都有哪些可能性呢? (这里只需要考虑前缀,因为如果不是前缀重复,发生失配的时候一定是要从第一位开始比较的)

1 . 真前缀永不重复

a b c d e f g

2 . 单元素真前缀重复 / 真·一元前缀字串 重复

a a a a b c a a e

3 . 真·多元前缀字串重复

a b c a b c a b c a a b

那么接下来,分别看一下这几种不同的模式串,分别有怎样的优化方式。

- 阅读剩余部分 -

C++ 几乎可以重载全部的运算符,而且只能够重载C++中已经有的。

· 不能重载的运算符:“.”、“.*”、“::”、“?:” · 重载之后运算符的优先级和结合性都不会改变。

可以重载为类的非静态成员函数; 可以重载为非成员函数。

重载单目运算符,前置的单目运算符不需要提供形参。如 ++ -- *= +=...

而后置的单目运算符是需要提供参数来区别前置(为了重载)的。

class Even{
    int number=0;
    public:
    A & operator ++ (){
        number +=2;
        return *this;
    }
    A operator ++ ( int ){
        int old = number;
        ++(number);
        return old;
    }
}

前置++ 返回的是左值,而后置++ 返回的只是一个右值。

重载双目运算符,需要提供一个形参。如 + - * % /...

class Matrix{
    int ** elements;
    int sizeX;
    int sizeY;
    public:
    Matrix & operator + ( const Matrix & m ) const{
        int newX = m.getX() > this.sizeX ? m.getX() : this.sizeX;
        int newY = m.getY() > this.sizeY ? m.getY() : this.sizeY;
        Matrix _new(newX,newY);
        for( int i = 0; i< newX; i++ ){
            for( int j =0; j< newY; j++ ){
                _new[i][j] = m[i][j] + elements[i][j];
            }
        }
        return _new;
    }
}

重载为非成员函数

当需要对当前程序没有权限的类型进行操作符重载的时候,或是将不同类型重载到一起运算,都需要进行非成员函数重载。

重载时需要从左至右依次声明参与预算的各个参数

这个时候可以理解为以重载的形式写的常规函数。

非成员函数的重载操作符参数,不能全为普通类型。

构造函数

c++在进行实例化的时候通常需要使用构造函数,没有显示构造函数的时候,系统会默认一个所有参数为空的默认构造函数。

C++中的构造函数有很多细节,其中从语法上来说,定义在函数声明的部分,是会优先于构造函数本身执行。 譬如说以下的两种方式,会有不同的效果。

class A{
    int X;int Y;
    public:
    A( int x, int y ){
        std::cout << X << std::endl;
        X = x; Y = y;
    }
}
class B{
    int X;int Y;
    public:
    B( int x, int y ): X(x),Y(y){
        std::cout << X << std::endl;
    }
}

A,B都能分别完成对象的构造,区别在于B由于是在声明阶段定义了两个形式参数将要被放置到的对象属性中,所以A的构造函数不能在函数体内的第一行输出我们期望的值。而B中,X属性已经完成了初始化,可以顺利的输出我们的期望值。 另外由于省略了建立、销毁局部参数的过程,这种声明式的构造函数效率更好。

派生类中的构造函数

在派生类中使用构造函数时,需要同时构造基类的构造函数,如果同时继承多个基类,则需要依次构造基类。 在没有进行基类构造的时候,c++会默认使用基类的默认构造函数进行构造,但如果不满足这样的条件,就会报错。

class A{
    int a;
    public:
    A( int a ):a(a){}
}
class B{
    char b;
    public:
    B( char b ):b(b){}
}

class C : public A, public B{
    bool c;
    C( int a, char b, bool c ):A(a),B(b),c(c){}
}

这是一个最基本的多继承构造函数的形式。

有些时候我们可能会需要一些变种构造函数,也就是重载。譬如说当我们基于Matrix设计一个九宫格类的时候,实际上matrix的行和列都是固定的3x3.我们并不需要这两个参数来初始化。 这样的话,我们就可以使用单参数的形式重载九宫格类的构造函数:

template <typename T>
class sMatrix : public Matrix<T>{
private:
    int _sign;
public:
    sMatrix( int sign ): Matrix<T>(3,3), _sign(sign){ cout<< _sign << endl; }
    sMatrix( int x, int y, int s ):Matrix<T>( x, y ){
        cout << _sign << endl;
        _sign = s;    
        cout << _sign << endl;
    }
};



在C++中创建数组的时候需要声明数组的长度,在声明一个二维数组的参数时,则至少需要确认第二维的长度,否则就无法完成编译。 为什么呢,我们可以用一张图来表示c++二维数组在内存中的表示就理解了。

实际上在创建数组的时候,c++是根据最低维,也就是最靠后的那个维度最大值来分配连续内存空间的。譬如int[2][5]就会分配10*4个字节空间出来,如果不知道最后一个维度,c++就不知道如何开辟内存空间了。

二维数组返回的就是整个数组的首元素地址。 而访问则是根据最后维的长度进行运算后得出:

/*
 * c++ 二维数组
 * 
 * hello@shezw.com 2020.07.03
 */

#include <iostream>
#include <string>

using namespace std;

int main()
{
   int a[2][5] = {1,2,3,4,5,6,7,8,9,10};

    for( auto e:a ){
        printf( "%p : %d \n",e,*e );
    }
    printf( "%p : %d \n",&a[1][3],a[1][3] );
    printf( "%p : %d \n",&a[0][8],a[0][8] );

}

输出:

0x7fffa508a870 : 1 
0x7fffa508a884 : 6 
0x7fffa508a890 : 9 
0x7fffa508a890 : 9 

可以看到 a[0][8] 其实是完全等价于 a[1][3] 的,实际上a[1][3] 就是从第一个空间开始往后数第3+1*5 = 8个。

在数据结构、算法与应用一书中约定了一种动态创建二维数组的方式。

这种方式的核心是 先构造一维指针数组,再将每个指针指向对应列的首元素。

为了调用和使用方便,我这里设计一个Matrix模板类,专门用于这样的动态二维数组的使用。

/*
 * c++ 二维数组
 * 
 * hello@shezw.com 2020.07.03
 */

#include <iostream>
#include <string>

using namespace std;

template <typename T>
class Matrix{
private:
    T ** _elements;
    int _colSize;
    int _rowSize;

public:
    Matrix( int rows, int cols ){
        _colSize = cols;
        _rowSize = rows;
        _elements = new T * [rows];
        for( int i=0;i<rows;i++ ){
            _elements[i] = new T [cols]();
        }
    }

    ~Matrix(){
        for( int i=0;i<_rowSize;i++ ){
            delete [] _elements[i];
        }
        delete [] _elements;
    }

    int getSize(){ return _colSize * _rowSize; };
    int colSize(){ return _colSize; };
    int rowSize(){ return _rowSize; };

    // 函数形式
    const T & get( int row, int col ){
        return _elements[row][col];
    }
    // 重载操作符形式
    T* & operator[]( int row ){
        return _elements[row];
    }
    // 重载操作符形式 只读
    const T* & operator[]( int row) const{
        return _elements[row];
    }
    void print(){

        for( int i=0; i< _rowSize; i++ ){

            printf( "\n row %p: \n", _elements[i] );

            for( int j=0; j< _colSize; j++ ){
                printf( "  col %p - %d\n", &_elements[i][j], _elements[i][j] );
            }

        }

    }
};

int main()
{
   Matrix<int> m(3,5);
    m[2][1] = 15;
   m.print();
}

* 指针运算符 可作为左值。表示查询到指针所对应的内存空间这样的操作。

& 地址运算符,可以概括为 取址运算符,从变量或对象等获取到该元素所在的内存空间中对应的地址。

指针定义

int i = 0;
int * pt = &i;

/* 
 未定义类型指针
 void类型指针可以存入任何类型的变量地址,但是不能直接被使用。使用的时候需要强制转换类型。
*/
int  i = 10;
bool b = false;
void * tentativePointer;
tentativePointer = & i;
i += static_cast<int *>(tentativePointer);
tentativePointer = & b;
b = !static_cast<bool *>(tentativePointer);

// 常量指针  指针所对应的地址的值被保护
int a;
a = 10; // √ a是变量 可以修改
const int *p1 = &a; // 指针
*p1 = 5; // × 不能通过p1 给a赋值

int b = 5;
p1 = &b; // √ 可以将p1转向其他变量

// 常指针  指针的地址被保护,即确定地址之后 不能修改,但对应的值可以修改。
int a;
a = 10;
int * const p2 = &a;
*p2 = 5; // √

int b = 5;
p2 = &b; // ×

指向对象的指针

指向对象的指针和其他类型的区别在于,访问对象的属性或方法不能通过.操作符。需要使用->

实际上这里的object->method()等价于 (* object).method(),这是c++提供的一种语法糖。

另外,每个对象的方法内,默认隐含了一个this属性,实际上是指向该对象本身的。

指针的运算

算数运算

对指针的运算并非对地址进行修改,而是对于指针所指向的内存空间进行偏移定位。 而每一次移动的单位,取决于指针所表示的类型,例如 char 占用一个字节,那么 p++则会从010A0000前往010A0001,而如果是 int 类型,那么每次会移动4个字节,如从010A00B0前往010A00B4。 由于数组在内存中是紧密相连排列的,所以我们也就可以通过第一个元素的地址和[n]下标来查询对应的元素。

int a[] = {1,2,3,4,5};
cout << *(a+3) << endl;
// 会输出4 
// *(a+3) 等价于 a[ 0 + 3 ]

关系运算

一般来说同类型的指针可以进行比较操作。 另外可以将指针与0做比较,判断指针是否为空。(如果是新标准 可能不行)

指针传参

指针传参是十分重要的一个特性了,失去了指针,C++也就失去了他最大的性能优势。 传递指针本身是很容易的,即使用 * type param_name这样的形式定义参数即可。外部调用时,将对应的实参地址进行填入即可。

这时,如果为了保护数据的可靠性,可以用const修饰参数类型。

普通参数

// 批量打印
void printArray( const int * arr, int len ){
    for( int i=0; i<len; i++ ){
        cout << arr[i] << endl;
    }
}
int a[] = {1,2,3,4,5};
printArray( a,5 );

// 批量修改
void batchIncrease( int * arr, int len, int n ){
    for( int i=0; i<len; i++ ){
        arr[i] += n;
    }
}
int b[] = {1,2,3,4,5};
batchIncrease( b, 5, 2 );
printArray( b );

// 输出 3,4,5,6,7

当实参不是数组类型的时候,我们无法通过[]操作符进行寻秩操作,这个时候需要使用 * 运算符来获取地址对应的值。

void splitFloat(float x, int *intPart, float *fracPart) {
   *intPart = static_cast<int>(x); //取x的整数部分
   *fracPart = x - *intPart; //取x的小数部分
}

函数参数

需要实现传递函数作为回调函数的时候,我们可以将函数名作为 函数指针参数传递进去。比较典型的用法是,遍历回调。 例如我们对一系列的对象进行遍历的时候,我们设计的遍历函数是一个通用 或者说一个接口,它能够支持调用者用各式各样的方式来处理遍历时的元素,那么这个时候函数指针是非常有用的。

函数指针参数的格式为:return_type( * function_name )( function_params )

template <typename T>
void forEach( T * elements, int len , void(* callback)( const T el ) ){

    for( int i=0; i<len; i++ ){
        callback( T )
    }
}

// 可以再考虑一下传递的T 采用引用的类型如何编写

除此之外,函数指针不仅限于传参,和普通类型一样,函数指针一样可以先定义,后赋值为各个具体的函数。

void (*pf)(int,char*);
void fun(int n,char *s) {......}
pf=fun;

指针类型函数

指针类型函数就是返回一个指针(内存地址)的函数。定义十分简单,在返回类型后增加 * 标识符即可。 但是需要注意,返回的指针应当是一个返回后依然有效的指针,否则会产生越界,野指针或是更多错误。

这个问题很好理解,如果你在网上购物,给了一个地址,千万不要给酒店门牌号,因为快递送过来的时候,你已经不在酒店了。无论是租房还是买房,只要你收货的时候,你这个地址还是有效的,那就可以~

所以无论是返回外部变量中的有效地址,还是通过new 进行动态分配的空间地址,都是可以顺利返回给调用者。 而动态分配的地址,永恒的点就是不要忘了delete。

其他补充

基于范围循环

for( type & e : array ){} 基于范围循环是类似于很多其他语言中提供的in循环,比如Javascript中的for( var k in arr ){}

SLT版本 string,queue


/*
 * 祖玛 Zuma
 * 
 * hello@shezw.com 2020.06.29
 */

#include <iostream>
#include <string>
#include <queue>

using namespace std;

struct opr{
    int t;
    char c;
    opr( int target, char color ){
        t = target;
        c = color;
    }
};

void checkElimination( string & balls, int cursor ){
    if( balls.empty() ){ return; }
    int i = 1; int l = cursor, r = cursor, len = balls.size();
    while( cursor-i > -1 ){
        if( balls[cursor-i] != balls[cursor] ) break;
        l = cursor - (i++);
    }
    i = 1;
    while( cursor+i < len ){
        if( balls[cursor+i] != balls[cursor] ) break;
        r = cursor + (i++);
    }
    if( r - l > 1 ){
        balls.erase( l,r-l+1 );
        if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时,原右侧必不为空,右侧第一个将取代原L。
    }
}

int main()
{
    string balls; int count;    // 主要变量
    int t; char c;              // 缓存变量

    cin>>balls;                 // 读取初始化彩球
    cin>>count;                 // 读取初始化数量

    queue<opr> oprs;            // 操作队列

    while( cin >> t ){          // 读取数字
        cin >> c;               // 读取颜色
        oprs.push( opr(t,c) );  // 压入队列
    }

    while( !oprs.empty() ){
        // cout<< oprs.front().t << " " << oprs.front().c << endl;
        t = oprs.front().t;
        c = oprs.front().c;
        balls.insert( t, 1, c );
        checkElimination( balls, t );
        oprs.pop();
        cout << (balls.empty() ? "-" : balls) << endl;
    }
    // cout << oprs.size() << endl;
    // cout<< balls << endl << count << endl << oprs.front().c << endl;
}

由于清华judge是不允许使用SLT的,所以使用自建QUEUE来完成。

非SLT版

/*
 * 祖玛 Zuma
 * 
 * hello@shezw.com 2020.06.29
 */

#include <iostream>
#include <string>

using namespace std;


struct opr{
    int t;
    char c;
    opr(){}
    opr( int target, char color ){
        t = target;
        c = color;
    }
};

template <typename T>
struct qe{
    qe<T>* prev;
    qe<T>* next;
    T data;
    qe(){}
    qe( T d, qe<T>* p = NULL, qe<T>* n = NULL ){
        data = d; prev = p; next = n;
    }
}; 

template <typename T>
class queue{ // 专为本算法特别定制队列,简化版
private:
    int _size = 0;
public:
    qe<T>* _head;
    qe<T>* _tail;

    queue(){
        _size = 0;
        _head = new qe<T>;
        _tail = new qe<T>;
        _head->next = _tail; _head->prev = NULL;
        _tail->prev = _head; _tail->next = NULL;
    }
    ~queue(){
    }
    int size(){return _size;}

    void push( T data ){

        qe<T>* newQe = new qe<T>( data, _tail->prev, _tail );
        _tail->prev->next = newQe;
        _tail->prev = newQe;
        _size++;
    }

    void pop(){

        if( empty() ) return;

        _head->next = _head->next->next;
        delete _head->next->prev;
        _head->next->prev = _head;
        _size--;
    }

    bool empty(){
        return _size == 0;
    }

    const T & front(){
        return _head->next->data;
    }

};



void checkElimination( string & balls, int cursor ){
    if( balls.empty() ){ return; }
    int i = 1; int l = cursor, r = cursor, len = balls.size();
    while( cursor-i > -1 ){
        if( balls[cursor-i] != balls[cursor] ) break;
        l = cursor - (i++);
    }
    i = 1;
    while( cursor+i < len ){
        if( balls[cursor+i] != balls[cursor] ) break;
        r = cursor + (i++);
    }
    if( r - l > 1 ){
        balls.erase( l,r-l+1 );
        if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时,原右侧必不为空,右侧第一个将取代原L。
    }
}

int main()
{
    string balls; int count;    // 主要变量
    int t; char c;              // 缓存变量

    cin>>balls;                 // 读取初始化彩球
    cin>>count;                 // 读取初始化数量

    queue<opr> oprs;            // 操作队列

    while( cin >> t ){          // 读取数字
        cin >> c;               // 读取颜色
        oprs.push( opr(t,c) );  // 压入队列
    }

    while( !oprs.empty() ){
        // cout<< oprs.front().t << " " << oprs.front().c << endl;
        t = oprs.front().t;
        c = oprs.front().c;
        balls.insert( t, 1, c );
        checkElimination( balls, t );
        oprs.pop();
        cout << (balls.empty() ? "-" : balls) << endl;
    }
    // cout << oprs.size() << endl;
    // cout<< balls << endl << count << endl << oprs.front().c << endl;
}

编译结果 95/100 最坏结果 204ms 14388KB。

这样看来还需要进一步优化。 20200629

格雷码

数据结构、算法与应用 第一张练习 26

两个代码之间的 海明距离 (Hamming distance) 是对应位不等的数量。 例如:100和010的海明距离是2。 一个(二进制)格雷码是一个代码序列,其中任意相邻的两个代码之间的海明距离是1。 子集生成的序列 000,100,010,001...111 不是格雷码,因为100,010海明距离是2。 而三位代码序列 000,100,110,010,011,111,101,001是格雷码。

在代码序列的一些应用中,从一个代码到下一个代码的代价取决于它们的海明距离。因此我们希望这个代码序列是格雷码。格雷码可以用代码变化的位置序列简洁地表示。 对于上面的格雷码,位置序列是1,2,1,3,1,2,1.

令g(n)是一个n元素的格雷码的位置变化序列。以下是g的递归定义:

    1                   n=1
    g(n-1),n,g(n-1)     n>1

注意这个是位置变化序列,并不是格雷码生成。

以下为算法

递归版:

#include <iostream>
#include <cmath>
/*
 *  格雷码序列数量是 2^n,相应的变化序列数量是 2^n - 1
 */
int * GrayCodeChangeSequence( int n ){
    int len   = pow(2,n)-1;
    int * arr = new int[len];
    if( n<2 ){ arr[0]=1; return arr; }

    int half  = (len-1)>>1;
    int * half_arr = GrayCodeChangeSequence( n-1 );

    for( int i=0; i<half; i ++ ){
        arr[i] = half_arr[i];
    }
    arr[half] = n;
    for( int i=0; i<half; i ++ ){
        arr[i+half+1] = half_arr[i];
    }

    return arr;
}

void testGCCS( int n ){

    int * b = GrayCodeChangeSequence(n);
    for( int i = 0; i< pow(2,n)-1 ; i++ ){
        std::cout << b[i] << ' ';
    }
    std::cout << endl;
    delete[] b;
}

int main()
{
    testGCCS(1);
    testGCCS(2);
    testGCCS(3);
    testGCCS(4);
    testGCCS(5);
}

测试分别输出:

1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

优化

实际上格雷码修改序列生成和斐波那契数列的生成效率是需要进一步优化的,原因在于每一次收到递归结果,都需要遍历一次结果并且覆盖到当前的序列中。从渐进意义上来说,复杂度是O(n2) 而且相对于序列的长度增长渐进意义上远大于n,这个时候如果能够在一次遍历的情况下配合少量计算那么可以将复杂度降低至O(n)

- 阅读剩余部分 -

数据结构、算法与应用 第一张练习 23

当两个非负整数x和y都是0的时候,他们的最大公约数是0. 当两者至少有一个不是0的时候,他们的最大公约数是可以除尽二者的最大整数。 因此gcd(0,0)=0, gcd(10,0)=gcd(0,10)=10,而gcd(20,30)=10.

求最大公约数的欧几里得算法(Euclid's Algorithm)是一个递归算法:

    x                       (y=0)
    gcd(y,x mode y)         (y>0)

其中mod是模数运算子(modulo operator),相当于C++取余操作符%.

以下为算法

递归版:

int GCD( int x, int y ){

    if( y==0 ){
        return x;
    }
    return GCD( y, x%y );
}

数据结构、算法与应用 第一张练习 19,20

阶乘 n! Factorial

阶乘是非常常见的数学计算以及算法入门问题。 其中 0,1,2,6,24,120... fn = n ( n<=1 ) fn = n * fn(n-1) (n>1) 使用递归实现是非常直观和简单的:

递归版本
int factorial( int n ){
    return n>1 ? n*factorial(n-1) : n;
}
迭代版本
int factorial( int n ){
    int res = n;
    while( n>1 ){
        res *= --n;
    }
    return res;
}

斐波那契 Fibonacci

1.斐波那契数

斐波那契数列是算法里最基础的概念了。

其中 0,1,1,2,3,5,8... fn = n ( n<=1 ) fn = fn(n-2) + fn(n-1) ( n>1 )

同样递归版本是简单而直观的:

递归版:
int fabonacci( int n ){
    return n>1 ? fabonacci( n-1 ) + fabonacci( n-2 ) : n;
}

递归版的Fibonacci效率是有严重缺陷的,主要是由于在合并两次之和时,两边进行了重复的计算,而每次重复计算也都是包含了更多迭代版本中更多的重复。这里由于递归而造成的重复计算复杂度为 O( 2∧n )

迭代版:
/*
 * n>0 当n<=0时,默认不考虑
 * 使用双指针缓存本次和上次结果,并进一步迭代
 */
int fabonacci( int n ){
    int l = 1;
    int r = 1;
    for( int i = 2; i <= n; i ++ ){
        r = l + r;
        l = r - l;
    }
    return r;
}

迭代版的斐波那契数的复杂度仅为O(n)

2.Fibonacci数列

/*
 * 返回数组首元素,数组长度为n n>0
 */
#include <iostream>
#include <cstdlib>
int * fabonacci( int n ){
    int * a = new int[n];
    a[0] = 1;
    if( n<2 ) return a;
    a[1] = 1;
    for( int i = 2; i < n; i++ ){
        a[i] = a[i-1] + a[i-2];
        a[i-1] = a[i] - a[i-2];
    }
    return a;
}

int main()
{
    int n   = 8;
    int * b = fabonacci(n);
    for( int i = 0; i<n; i++ ){
        std::cout << b[i] << std::endl;
    }
}

这段代码会输出:

1
1
2
3
5
8
13
21

最长公共子序列是一个经典的基础算法问题 在两个序列中 如果序列1中的元素a也存在于序列2,则认为a是1,2的公共元素。 当序列3中的每一个元素都能够满足在不改变次序的情况下依次属于1,2,那么则认为3是1,2的公共子序列。多个公共子序列中,元素最多的即为最长公共子序列。

在学堂在线的算法课程中,有比较详细的课程讲述这个算法的构思。但是没有给出具体的实现,这里来自己实现一下。

首先使用表格模拟排列组合的所有情况: 以{a,b,c,d,e},{a,b,q,c,b}为例:

A\B a b q c b
a 1 1 1 1 1
b 1 2 2 2 2
c 1 2 2 3 3
d 1 2 2 3 3
e 1 2 2 3 3

实际上看到这样的填充,直觉上就应该反应出来,使用二维数组来解决。 其中当 A[i]!=B[j]时,取左方或者上方更大的,而A[i]==B[j]的时候,取T[i-1][j-1] + 1。这里i=0或j=0的时候就不方便了,所以给矩阵默认增加一行 0 行。即

A\B 0 a b q c b
0 0 0 0 0 0 0
a 0 1 1 1 1 1
b 0 1 2 2 2 2
c 0 1 2 2 3 3
d 0 1 2 2 3 3
e 0 1 2 2 3 3

- 阅读剩余部分 -

数据结构、算法与应用 C++语言描述

第一章 习题25

子集生成法(Subset Generation)

三元素集{a,b,c}的子集是:{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。 这些子集又可以使用01序列来表示,分别是000,100,010,001,110,101,011,111。 0/1分别代表着 含有/不含 原集合中的对应元素。

输出n个元素的所有子集(以01序列的形式)。

在网上看了一下基本上最终输出的都是数组,但并没有按照题目输出01序列。所以我这里严格按照题目来解。

分析

子集生成是一个完全排列组合问题,包括退化情况空集,以及极限情况自身。 其他的情况分别是[1,n)个元素的任意组合。 所以如果递归的话,也就是每一次元素数量+1 或者是-1,如果不是输出01序列,那么输出的元素个数就刚好等于递归中的n。输出序列的时候,只需要在其他位置补0即可。而补0逻辑也可以反过来考虑,即默认是n个0 e.g. 0000,随着循环的i改变,在不同的位置上填1e.g. 0001,0010,0100,1000,这样更加便捷。

至此,已经有了算法的模型了:

/* Subset Generation */
#include <iostream>
#include <string>

using namespace std;

template <typename T>
void subsetGeneration( T* const A, int len, string code = "", int focus = 0 ){

    if( focus > len ) return;
    if( focus == len ){ cout << string(len,'1') << endl; return; }
    if( focus == 0 ){ cout << string(len,'0') << endl; }

    if( code == "" ){ code = string(len,'0'); }

    code[focus] = '1';
    for( int i = focus; i<len; i++ ){
        code[i] = '1';
        cout << code << endl;
        code[i] = '0';
    }

    subsetGeneration( A, len, code, focus + 1 );
}
int main(){

    subsetGeneration( "abcd", 4 );
    return 0;
}

思考1 上述算法已经成功解题,但是思维略显复杂,直觉上就感觉不是一个优质解。

- 阅读剩余部分 -

遇到这个问题的时候在网上搜索 绝大部分都是同样的一个解决方案 就是改一下软件的某个设置。 这个方法是十分不严谨的,所以网仔细琢磨了一下这个错误说明。

首先看一下官方给的说明: 微软 - 编译器错误 C2760

有多种方法可导致此错误。 通常,它是由编译器无法识别的令牌序列引起的。
There are several ways to cause this error. Usually, it's caused by a token sequence that the compiler can't make sense of.

这里实际上是表示有某个标识符,无法被编译器识别。而问题不一定出在最后的“;”。

这个时候我也是很头大,因为我的代码简单明了,没有任何有问题的字符。

这里最好的方式是检查一下类的定义和使用 比如说你定义了一个 A类,但是在引入这个类声明之前,就已经在使用了,就会报这个错误。

最终,我找到了问题,由于我使用的 FibonacciHelper类,定义在了使用之后,这个时候类还没有定义,所以会被当成一个标识符,而此时编译器不认识这个标识符所以出现了一些难以理解的错误说明。

把类的定义放到该文件的上方,( 有的时候这种问题和 .h文件导入位置有关系。 ) 譬如导入的 .h文件中的类 在导入之前就使用,也会有同样的问题。

int main{
    TestClass t;
}

class TestClass{
    // ...
}
// 报错
TestClass c;

#include "TestClass.h";
// 也会报错

ZangoDB是一个indexedDB的类MongoDB轻量级接口库,主要是为了更轻松快速的编写indexedDB相关的操作。

关于indexedDB: IndexedDB - MDN

Github: ZangoDB

在MDN的推荐中介绍了几款不同的轻量级类库 来简化indexdb的使用,其中dexie.js也是不错的,但是在多条件筛选上并没有支持,所以介绍一下ZangoDB。

对于熟悉MongoDB这类NoSQL的开发者来说,应该简单看一下文档就能够快速上手。这里我将会对熟悉关系型数据库的来做一下说明。

ZangoDB主要将indexedDB简化为3个对象

Db - 数据库

Collection - 集合(表)

Cursor - 游标 查询( SQL )

不同于关系型数据库的初始化时数据库,表,所有字段名称和类型,索引结构都要确定。

NoSQL数据库通常只需要建立数据库的名称,表名称以及需要索引的字段。 其他的数据可以任意存储。

ZangoDB的主要特性集中在运算符的部分,类似于SQL中的( GROUP BY, ORDER BY 等 ) 包括以下几类

文末会给出更详细的介绍

Filter Operators 筛选查询运算符

Expression Operators 表达式运算符

Update Operators 更新运算符

Group Operators 组运算符


- 阅读剩余部分 -

最近在基于chrome开发一个用于收集和整理 信息(知识)的插件,名称叫Memoreasy。 一贯以来我都是用自己写的AppSiteJS框架在写web前台的功能,很少去涉及到异步编程,一般来说也就只是在XMLRequest( Ajax )的时候会用。

而在开发chrome插件的时候,几乎所有的api都是异步API,在第一时间的时候还是让我有些不适应。

但是很多时候理解一个技术或者说模式,最重要的并不是强迫自己去理解很多别人的说明、解释或者说代码。最关键的是需要以一个好的思路领会到这个概念的精髓。

我们先说同步编程,大家肯定不陌生,最初学习编程的时候我们都是使用同步编程,同步编程就好比工厂的流水线。 同步编程-流水线

我们在进行同步编程的时候 每一个后续的步骤都依赖于前一步的计算或结果(返回值),如果其中一个过程出现问题,那后续的工作也无法继续了。 换言之,我进行后续工作的时候肯定已经获得了前一步的结果了。 从我们的思维习惯上来讲,这个过程的可控性是很好的。

// 一个简单同步编程的代码说明
var a = "hello", b = 10;
var u = getUseid();
if( u ){
    var obj = { text: a, number: b, user: u };
    console.log(obj);
}else{
    console.log( 'user not found' );
}
function getUserid(){
    return localStorage.getItem('userid');
}

在这段程序中,无论是否找到userid 控制流程实际上还是在当前这段代码中的。 这相当于开发者是公司的老板,让员工去完成一些任务,且无论完成的如何,都需要向老板汇报,然后老板再向员工发布下一步的任务。 这就是我们常识中的“集权"。 我们喜欢同步编程,也就是喜欢他的掌控度。

但是同步也会遇到问题。譬如说,从网络中请求数据(Ajax)时我们无法掌控对方的后续结果。 这就相当于我们在网上下单购物,快递走哪里,什么时间到什么位置,会不会被堵车,会不会在仓库里被堆积,被哪个快递员投递等等。 这种情况我称之为不可控编程,在这个时候,我们不可能一直在手机前面全程跟踪一直到收到商品,我们一般放下手机该吃吃该喝喝,等待快递员的电话。 其实我们也早已习惯了“放权”,只是在编程中,我们需要对那些习惯做一些适应。 来看一段示例代码:

// 购物异步编程 仅供参考 完全不严谨!

function 购物( 订单 ){
    return Promise( 付款之后, 没给钱 ){
        给钱( 订单.价格 ).then( function(){ 
            付款之后( 订单 ) 
        }).catch(function(){
            没给钱()
        })
    }
}

function 发快递( 订单 ){
    var 包裹 = 商家打包( 订单 ); // 打包好了才能发包裹,所以需要同步
    return Promise( 到货, 丢了 ){
        发货().then( function( 包裹 ){
            到货( 包裹 )
        }).catch(function(  ){
            丢了()
        })
    }
}

function 到货( 包裹 ){
    return Promise( 在家, 不在家 ){
        打电话( 包裹.收件人 ).then( function(){
            在家( 包裹 ); // 送货上门
        }).catch(function(){
            放到快递柜( 包裹 )
        })
    }
}

这里我们定义了多个购物相关的异步方法,而我们在调用的时候就很简单了

购物( 订单 ).then( 发快递 ).catch( 弹窗提示 );

是不是感觉打开了新世界,因为发快递之后的事情我都不用管了,放权也是很爽的。