C++ 字符串与数组

字符串匹配问题

Brute-Force

顺序遍历母串,将每个字符作为匹配的起始字符,判断是否匹配字串。时间复杂度为$O(m*n)$。

Rabin-Karp

将每一个匹配字串映射为一个hash5值。例如,将子串看成是一个多进制数,比较它的值与母串中相同长度子串的hash值,如果相同,再细致地按照字符确认字符串是否确实相同。顺序计算母串hash值的过程中,使用增量计算的方法:扣除最高位的hash值,增加最低位的hash值。因此能在平均情况下做到$O(m+n)$

什么是hash值

散列函数(Hash Function)是一种从任何一种数据中创建小的数字”指纹”的方法。该函数将数据打乱混合,重新创建一个叫做散列值的指纹。相同数据的hash值相同。好的散列函数在输入域中很少出现散列冲突。

Array

定义方式

  • 在Stack上定义长度为arraySize的整型数组
    int array[arraySize];
  • 在Heap上定义长度为arraySize的整型数组,使用完后需要释放内存
    int *array = new int[arraySize];
    在heap中数组使用完后需要释放内存
    delete[] array;
    注意,在旧的编译器中,不能在stack上定义一个长度不确定的数组,即只能定义如下:
    int array[10];
    新的编译器没有如上限制。但是如果数组长度不定,则不能初始化数组
    int array[arraySize] = {0};//编译报错

    关于stack

    stack主要是指由操作系统自动管理的内存空间。当进入一个函数,操作系统会为该函数中的局部变量分配储存空间。事实上,系统会分配一个内存块,叠加在当前stack上,并且利用指针指向前一个内存块的地址。
    函数的局部变量就储存在当前的内存块上。当该函数返回时,系统“弹出”内存块,并且根据指针回到前一个内存块。所以,stack总是以后进先出的方式工作。

    关于heap

    Heap是用来储存动态分配变量的空间。对于heap而言,并没有像stack那样后进先出的规则,程序员可以选择随时分配或者回收内存。这就意味着程序员自己用命令回收内存,否则会产生内存泄漏(memory leak).
    在C/C++中,程序员需要调用free/delete来释放动态分配的内存。在JAVA,Objective-C中,语言本身引入垃圾回收和计数规则帮助用户决定在什么时候自动释放内存。

二维数组

  • 在Stack上创建:

    int array[M][N];

    传递给子函数:

    void func(int arr[M][N])

    M可以省略,但N必须存在,以便编译器确定移动内存的间距

  • 在Heap上创建:

    int **array = new int*[M];
    //或者 (int**)malloc(M* sizeof(int*));
    for(int i=0; i<M; i++)
    {
       array[i]= new int[N];
    	//或者 (int*)malloc(N *sizeof(int));
     }

    传递给子函数:

    void func(int **arr, int M, int N){}

    使用完后需要释放内存:

    for(int i=0; i<M; i++)
    delete[] array[i];//先释放二维指针
    delete[] array;//再释放一维指针

    Vector

  • Vector 可以用云算法[]直接访问元素

  • size_type size()) const;//返回vector的元素个数

  • void push_back(const value_type val);//末端插入

  • pop_back()删除最后一个元素

  • erase()可以删除一个由iterator指出的元素,也可以删除一个指定的元素

  • remove()也可以删除vector容器中的元素(不建议使用)

  • 不同的是,remove()一般情况下不会改变容器大小,popback()和erase()等成员函数会改变容器大小。

  • 正确的使用iterator删除元素

    for(vector<int>::iterator it = v.begin();it!=v.end();)
    {
      //使用if else语句删除元素防止越界
      if(condition){
    	it = v.erase(it);
    	}else{
    	++it;
    	}
    }

    Hash Table

    Hash Table 几乎是最为重要的数据结构,主要用于基于“key”的查找,存储的基本元素是key-value的pair。逻辑上,数组可以作为Hash Table的一个特例:key是一个非负整数。
    C++标准库中提供map容器,可以插入,删除,查找key-value pair,底层以平衡二叉搜索树的方式实现,根据key进行了排序。
    在C++11中,标准库添加了unordered_map,更符合Hash table的传统定义,平均查找时间$O(1)$

String

在C语言中,字符串指的是一个以’\0’结尾的char数组。关于字符串的函数通常需要传入一个字符型指针。
在C++中,String是一个类,并且可以通过调用类函数实现判断字符串长度,字串等操作。

  • C语言中String常用函数

    • char* strcpy(char* destination, const char* source) - 复制原字符串到目标字符串
    • char* strcat(char* destination, const char* source) - 将原字符串插入目标字符串
    • int strcmp(const char* str1, const char* str2) - 比较两个字符串,若相等则返回0,否则返回正数
    • char* strstr(char* str1, const char* str2) - 返回一个指针,指向str2在str1的所在位置,如果str2不在str1中则返回NULL
    • size_type strlen(const char* str) - 返回C字符串的长度
    • double atof(const char* str) - 将一个字符串转换成double类型
    • int atoi(const char* str) - 将一个字符串转换成int类型
  • C++中String类常用函数

    • String类重载了+,>,<,=,==等运算符,比较是否相等,附加子串等都可以用运算符来实现。
    • size_t find(const string str, size_type pos = 0)const - 搜索子串在字符串中首次出现的位置,返回索引
    • string substr(size_t pos=0, size_t len=npos)const; - 从一个指定位置开始复制字符串
    • string erase(size_t pos=0, size_t len=npos) - 消除从某个位置开始的某个长度的子串
    • size_t length() - 返回字符串的长度

      模式识别

      当遇到某些题目需要统计一个元素集中元素出现的次数,应该直觉反应使用Hash Table,即使用std::unordered_map或std::map: key是元素,value是出现的次数。特别地, 有一些题目仅仅需要判断元素出现与否(相当于判断value是0还是1),可以用bitvector, 即bitset,利用一个bit来表示当前的下标是否有值。

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!