分类算法下的文章

PHP按特定key进行多维数组排序

作者: sprite
时间: 2021-06-23
分类: 后台,算法
评论

这个排序在网上直接搜索的结果有这样一个:

array_multisort(array_column($array,'sort'),SORT_ASC,$array);

这个是错误的。切忌不要以讹传讹了。

分析排查最终结果

分析排查

实际上array_multisort 是PHP内置的方法，官方有说明： PHP - array_multisort

- 阅读剩余部分 -

C/C++判断素数(质数)为什么到根号x就可以而不是x/2？

作者: sprite
时间: 2021-06-05
分类: 高数,Cpp,C++,算法
评论

隐约记得之前做过一个c++的题目是判断一个数是否素数（质数）我当时给的算法是判断 2 - x/2, 因为被除数大于 x/2 那商一定小于2，所以被除数必须大于x/2

最近看书的时候发现通用的算法是计算 2- sqrt(x) 即根号x 这就让我产生疑问了，毋庸置疑，这个算法的效率更高，时间复杂度是logn。那为什么到sqrt(x)就够了呢？

我反复思考总算得出了结论，这里用反证法即可：

已知 n 不是素数，且a，b是 n的两个根， a*b = n
假设 b>sqrt(n)，且a>=sqrt(n)
则a*b > sqrt(n) * sqrt(n) 即 a*b > n 与条件相悖

得出若存在一个根大于sqrt(n)，
那必定存在另一个小于sqrt(n)的根

与此对应的逆否命题是

若不存在小于sqrt(n)的根，则不存在大于sqrt(n)的根

根据这个证明的结论，判断是否是素数，最多只需要判断到 n 的平方根即可。

iOS swift将文字转为竖排文字

作者: sprite
时间: 2021-03-30
分类: IOS,算法
1 条评论

在开发一款中国文化的app时，需要以竖排文字的方式展示诗文。在CSS中，有一个文字方向的属性可以用来直接显示竖排文字，但是在iOS中并没有直接提供，所以扩展一下String类，可以返回一个竖排多行文字

先看一下效果:

简单做一下说明：

convertVerticalText 是将多行文字转变为多列文字的处理过程，类似于矩阵的对角。

首先获取待转换的文字一共有多少行，那么也就对应着转换后每一行有几个字。

由于每一行的文字个数未必相同，在转换为列的时候，就意味着会有空白，所以要获取最长一行有多少个字符。每次在取完有效字符后，如果没有达到最长字符时，就要自动填入空白字符了。

- 阅读剩余部分 -

C++ 超大整数数学运算

作者: sprite
时间: 2020-08-05
分类: C++,算法
评论

数据结构、算法与应用习题6.1 69题 p143

给出一种整数表示法，用于对任意大小的整数进行数学运算(加减乘除),且不能有精度损失。

这里应该能支持两种表示法，1链表，2数组。

使用链表比较符合我们直观上对于数字的印象，其中将 rear链接到最后一位数，那么使用prev就可以陆续的取出每一个数字。并且在进行数学运算时，我们无需关注最终的位数，只需要将结果insert进入结果链表中即可。

由于没有规定一定是正整数，所以需要给一个符号。（在网上也搜索了一些大数运算的参考，没有提供有符号运算的版本）带符号的时候，逻辑会变复杂不少。

这里我给出一个带符号的方式其中isNegative true为负数，false为正数

为了表示符号对于运算的影响，我会写两个版本的加法

链表表示:


class BigInt: public Chain<int>{
public:
    bool isNegative = false;

    BigInt( int* a, int size ){ // 基于数组构造
        for( int i=0; i<size; i++ ){
            insert( a[i] );
        }
    }

    // 最基本的 正正 相加
    BigInt& operator+( BigInt& bigInt ){
        int plus = 0;  // 进位
        int res  = 0;  // 单次计算结果
        BigInt result = new BigInt; // 结果
        ChainNode<int>* cursor = last();
        ChainNode<int>* targetCursor = bigInt.last();

        // 使用倒序的方式取出元素并计算
        while( cursor->prev() && targetCursor->prev() ){
            res = cursor->element + targetCursor->element + plus;
            plus = res > 9 ? 1 : 0;

            result->prepend( res ); // prepend即为 addAfter( head )
            cursor = cursor->prev();
            targetCursor = targetCursor->prev();
        }
        while( cursor->prev() ){
            result->prepend( cursor->element );
            cursor = cursor->prev();
        }
        while( targetCursor->prev() ){
            result->prepend( targetCursor->element );
            targetCursor = targetCursor->prev();
        }
        return result;
    }

    // 完整版 带符号运算的加法 （不是重载!!!）
    BigInt& operator+( BigInt& bigInt ){

        BigInt result = new BigInt; // 结果
        result.isNegative = size() >= bigInt.size() ? isNegative : bigInt.isNegative; // 暂定为较大位数。 如果位数相同，根据最后一次计算结果修正。

        int plus = 0;   // 进位或借位
        int res;        // 单次计算结果
        ChainNode<int>* cursor = last();                // 当前游标
        ChainNode<int>* targetCursor = bigInt.last();   // 目标游标

        while( cursor->prev() && targetCursor->prev() ){

            res = isNegative ? -cursor->element : cursor->element
                + bigInt.isNegative ? -targetCursor->element : targetCursor->element
                + plus; // 我们把大数中的每一个数 都当成 a[i] * 10i来看。
            // 绝对值超过>9的都需要向上进一位(一定是同符号)
            // 不同符号 结果小于0的 需要借位
            // 同符号小于0，不同符号大于0小于10的都可以忽略
            // 小于0的时候 res需要取绝对值，保持元素的非负

            if( res >9 || res<-9 ){
                plus = 1;
            }else if( res < 0 ){
                plus = isNegative == bigInt.isNegative ? 0 : -1;
                res  = -res;
            }

            result.prepend(res);
        }

        if( size() == bigInt.size()  ){ // 修复位数相同的问题
            if( plus>0 ){
                result.prepend(1); // 一定是同符号的，直接+1
            }else if( plus<0 ){
                result.isNegative = true; // 此时已经无法借位了，确认最终结果为负数
            }
        }

        // 任意链表仍有元素未计算，继续补齐
        while( cursor->prev() ){
            result->prepend( cursor->element + plus );
            plus = 0;
            cursor = cursor->prev();
        }
        while( targetCursor->prev() ){
            result->prepend( targetCursor->element + plus );
            plus = 0;
            targetCursor = targetCursor->prev();
        }

        // 修复首位为0的情况 // 全部删除则为空 即0
        while( result.first().element == 0 ){
            result.remove( result.first() );
        }

        return result;
    }

    // 在有符号加法的前提下，减法运算就简单多了
    BigInt& operator-( BigInt& bigInt ){

        bigInt.isNegative = !bigInt.isNegative; // 符号位颠倒
        BigInt result = *this + bigInt;

        bigInt.isNegative = !bigInt.isNegative; // 恢复
        return result;
    }
}

0	1	2	3	4	5	6	7	8	9
a	b	c	d	e

0	1	2	3	4	5	6	7	8	9
f	a	b	c	d	e

0	1	2	3	4	5	6	7	8	9
f	a	b	g	c	d	e

0	1	2	3	4	5	6	7	8	9
f	a	b	g	c	d	e	h

0	1	2	3	4	5	6	7	8	9
a	b	g	c	d	e	h

0	1	2	3	4	5	6	7	8	9
a	b	g	c	e	h

字符串匹配算法KMP, BM_BC/BM_GS如何理解？ C++语言

作者: sprite
时间: 2020-07-16
分类: C++,算法
评论

字符串匹配： 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++ 创建动态二维数组

作者: sprite
时间: 2020-07-03
分类: 笔记,C++,算法
评论

在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();
}

C++ 祖玛 ZUMA

作者: sprite
时间: 2020-06-29
分类: C++,算法
评论

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

C++ 格雷码位置变化序列 Gray Code

作者: sprite
时间: 2020-06-28
分类: C++,算法
评论

格雷码

数据结构、算法与应用第一张练习 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)

- 阅读剩余部分 -

C++ 最大公约数 Greatest Common Divisor GCD

作者: sprite
时间: 2020-06-28
分类: C++,算法
评论

数据结构、算法与应用第一张练习 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 );
}

C++ 阶乘和斐波那契 Factorial Fibonacci

作者: sprite
时间: 2020-06-28
分类: C++,算法
评论

数据结构、算法与应用第一张练习 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;
    }
}

这段代码会输出:

C++ 最长公共子序列 Sub Sequence

作者: sprite
时间: 2020-06-25
分类: C++,算法
评论

最长公共子序列是一个经典的基础算法问题在两个序列中如果序列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	a	b	q	c	b
0	0	0	0	0	0
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

- 阅读剩余部分 -

C++ 子集生成 Subset Generation

作者: sprite
时间: 2020-06-25
分类: C++,算法
评论

数据结构、算法与应用 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 上述算法已经成功解题，但是思维略显复杂，直觉上就感觉不是一个优质解。

- 阅读剩余部分 -

正则表达式的梳理和练习笔记

作者: sprite
时间: 2019-09-13
分类: 笔记,算法
评论

正则表达式的重要性不言而喻，平时写的时候都是拼拼凑凑感觉还是不太好，趁着今天做一个梳理，要让正则的用法深入血液才好。

MDN | Javascript 正则表达式介绍

正则表达式(regular expression)描述了一种字符串匹配的模式（pattern），可以用来检查一个串是否含有某种子串、将匹配的子串替换或者从某个串中取出符合某个条件的子串等。

创建一个正则表达式节

你可以使用以下两种方法之一构建一个正则表达式：

使用一个正则表达式字面量，其由包含在斜杠之间的模式组成，如下所示：

var re = /ab+c/; 使用正则表达式字面量为正则表达式提供了脚本加载后的编译。当正则表达式保持不变时，使用此方法可获得更好的性能。

或者调用RegExp对象的构造函数，如下所示：

var re = new RegExp("ab+c"); 使用构造函数为正则表达式提供了运行时的编译。使用构造函数的方式，当你知道正则表达式的模式将会改变，或者你不知道模式，并且从其他来源获取它，如用户输入。

- 阅读剩余部分 -