数组和字符串

发表于 2022-08-14 分类于算法阅读次数： Waline：本文字数： 4k 阅读时长 ≈ 4 分钟

堆和栈的区别

1.1 知识要点

1.1.1数组

在栈上创建：

1	int array[M][N];

在堆上创建：

1	int *array = new int[M]; \\或者(int*) malloc (M sizeof(int*))

数组可以通过下标随机访问元素，所以在修改、读取某个元素的时候效率很高，具有O(1)的时间复杂度。在插入、删除的时候为O(n)。

1.1.2 哈希表

哈希表(Hash Table)主要基于“键(key)“的查找，存储的基本元素是键-值对。

哈希表的本质是当使用者提供一个键，根据哈希表自身定义的哈希函数（Hash Function），映射出一个下标，根据这个下标决定需要把当前的元素存储在什么位置。在一些合理的假设情况下，查找一个元素的平均时间复杂度是 O(1)，插入一个元素的平摊（amortized）时间复杂度是 O(1)。

当对于不同的键，哈希函数提供相同的存储地址时，哈希表就遇到了所谓的冲突（collision）。解决冲突的方式有链接法（chaining）和开放地址法（Open Addressing）两种。简单来说，链接法相当于利用辅助数据结构（比如链表），将哈希函数映射出相同地址的那些元素链接起来。而开放地址法是指以某种持续的哈希方式继续哈希，直到产生的下标对应尚未被使用的存储地址，然后把当前元素存储在这个地址里。

链接法实现相对简便，但是可能需要附加空间，并且利用当前空间的效率不如开放地址法高。开放地址法更需要合理设计的连续哈希函数，但是可以获得更好的空间使用效率。

C++标准库中提供 map 容器，可以插入、删除、查找键-值对，底层以平衡二叉搜索树的方式实现，根据键进行了排序。严格来说，map 并不是一个哈希表，原因是查找时间从 O(1)变为了 O(log n)，但是好处在于能够根据键值，顺序地输出元素，对于某些应用场景可能更为合适。在 C++11 中，标准库添加了 unordered_map，更符合哈希表的传统定义，平均查找时间 O(1)。

1.1.3 String

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

2.1 模式识别

2.1.1 使用哈希表

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

例题1：

判断一个字符串所有的字符是否都是唯一的

如果运用哈希表，我们可以直接用字符作为键，出现的次数作为值。

如果运用 bitset，我们需要建立字符到整数下标的映射关系。

复杂度分析：哈希表和 bitset 做法都需要扫描整个字符串，每次插入操作时间复杂度 O(1)，假设字符串长度为 n，则平均时间复杂度都是 O(n)。空间上，每个合法字符都有可能出现，假设字符集大小为 m，则平均空间是 O(m)。哈希表的数据结构需要占用更多空间，所以 bitset 是更合理的数据结构。

参考答案：

法一: 用hashmap

class Solution {
public:
    bool isUnique(string astr) {
      //判断位数
        if(astr.size() <= 1){
          return true;
        }
      unordered_map<char,int>mp;
      for(const char c:astr){
        if(mp.count(c)){
          return false;
        }
        mp[c] = 1;
      }
      return true;
    }
};

法二：先排序，看看是否存在相邻的两个字符相同的情况

class Solution {
public:
    bool isUnique(string astr) {
      //判断位数
        if(astr.size() <= 1){
          return true;
        }
      sort(astr.begin(),astr.end());
      int i = 0, j = 1;
      while(j != astr.size()){
        if(astr[i] == astr[j]){
          return false;
        }
        ++i;
        ++j;
      }
      return true;
    }
};

法三：位运算：

1、假如字符串不在['a'-'z']之间

2、设置一个26位的二进制数，将其中某一位置为1表示对应的char字符，0000...0001（26位）表示a，用dist表示当前字符在二进制数中的位置。

3、用now_post记录26个位置中有多少个位置已经出现1

class Solution {
public:
    bool isUnique(string astr) {
      int dist = 0;
      int now_pos = 0;
      for(const char c:astr){
        dist = c -'a';			//得到所在的位置
        if(now_pos & 1 << dist) {	//如果这个位置已经出现过1，即表示该字符已经出现过
          return false;
        }
        now_pos |= (1<<dist);			//更新存在1的位置
      }
      return true;
    }
};

例题2:

给定两个字符串，判断它们是否互为字符重排

解题分析：

我们需要找到两个字符串之间的共同点，即通过某种映射，使得所有置换得到相同的结果。考虑到置换的特性：无论如何变化，每个字符出现的次数一定相同。一旦需要统计一个元素集中元素出现的次数，我们就应该想到哈希表。

复杂度分析：

哈希表需要扫描整个字符串，每次插入操作时间复杂度 O(1)，假设字符串的长度为 n，则平均时间复杂度都是 O(n)。最后比较两个 hash 是否相同，每个合法字符都有可能出现，假设字符集大小为 m，则需要的时间复杂度是 O(m)，故总的时间复杂度 O(m+n)。空间上，平均空间是 O(m)。

参考答案：

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        // 若 s1, s2 长度不同，则不互为重排
        if (s1.length() != s2.length())
            return false;
        // 初始化哈希表 dic
        unordered_map<char, int> dic;
        // 统计字符串 s1 各字符数量，遇到 +1
        for (char c : s1) {
            dic[c] += 1;
        }
        // 统计字符串 s2 各字符数量，遇到 -1
        for (char c : s2) {
            dic[c] -= 1;
        }
        // 遍历 s1, s2 中各字符的数量差
        for (auto kv : dic) {
            // 若 s1, s2 中某字符的数量不一致，则不互为重排
            if (kv.second != 0)
                return false;
        }
        // 所有字符数量都一致，因此互为重排
        return true;
    }
};

2.1.2 利用哈希表实现动态规划的思想

当处理当前节点需要依赖于之前的部分结果时，可以考虑使用哈希表记录之前的处理结果。其本质类似于动态规划（ Dynamic Programming），利用哈希表以 O(1)的时间复杂度利用之前的结果。

例4:

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可

解题分析：