分类 算法 下的文章

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

- 阅读剩余部分 -

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

MDN | Javascript 正则表达式介绍

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

创建一个正则表达式节

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

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

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

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

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

- 阅读剩余部分 -