关于string和cstring

<string> 和 <cstring> 是 C++ 中的两个不同的头文件，它们有不同的作用和功能：

  • <string> 头文件包含了 C++ 标准库中的字符串类 std::string，以及与字符串相关的一些函数和操作符重载。这个头文件用于处理 C++ 中的字符串操作，提供了更多的字符串处理功能和便利。

  • <cstring> 头文件是 C 标准库中的头文件，其中定义了一些 C 语言字符串操作的函数，比如字符串复制、连接、比较等。在 C++ 中，这些函数通常被包含在 std 命名空间中，比如 std::strcpy、std::strcat 等。

总的来说，<string> 更适合用于 C++ 中的字符串操作，而 <cstring> 则更适合用于 C 风格的字符串操作。

关于string包含的常见函数

  • length() 或 size(): 返回字符串的长度。
  • append(str): 在字符串末尾添加另一个字符串。
  • insert(pos, str): 在指定位置插入另一个字符串。
  • erase(pos, len): 从指定位置删除指定长度的字符。
  • find(str): 查找字符串中是否包含指定的子字符串。
  • substr(pos, len): 返回从指定位置开始的指定长度的子字符串。
  • compare(str): 比较两个字符串。
  • replace(pos, len, str): 用另一个字符串替换指定位置的指定长度的字符。
  • push_back()、pop_back():类似数组的操作方式，对字符串依然使用。

异或：^.运算规则：N^0=N;N^N=0;

判断大小写：islower、isupper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool detectCapitalUse(string word) {
        if (word.size() >= 2 && islower(word[0]) && isupper(word[1])) {
            return false;//排除形如uSA的情况
        }
        for (int i = 2; i < word.size(); i++) {
            if (islower(word[i]) ^ islower(word[1])) {
                //除了第一个字母以外的字母大小写不一致
                return false;
            }
        }
        return true;
    }
};

转为小写：tolower/转为大写:toupper(注意，返回值类型为int。可以写作char ch = tolower(c);或者auto ch = char(tolower(c));)。如果是数字，则无变化，可以接受数字

检查一个字符是否是字母或数字:isalnum,需要头文件<cctype>.如果判断是否为字母:isalpha,判断是否为数字:isdigit.也是需要头文件<cctype>

定义b为a的逆序字符串：

1
string b(a.rbgin(),a.rend());

1.回文串的定义

验证回文串：125

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isPalindrome(string s) {
        string schange;
        for (char ch : s) {
            if (isalnum(ch)) {
                schange += tolower(ch); //防止大小写干扰之后的相等判断
            }
        }
        string schangeReverse(schange.rbegin(), schange.rend());
        return schange == schangeReverse;
    }
};

空间优化:使用双指针，在原字符串上直接判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isPalindrome(string s) {
        int n=s.size();
        int left=0,right=n-1;
        //每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同
        while(left<right){
            while(left<right&&!isalnum(s[left])){
                ++left;
            }
            while(left<right&&!isalnum(s[right])){
                --right;
            }
            if(left<right){
                if(tolower(s[left])!=tolower(s[right])){
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
};

取字符串str从索引 0 开始、长度为 index 的子字符串：(注意包括的是str[0]到str[i-1]的部分！)

1
str.substr(0, index);

2.公共前缀

最长公共前缀：14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//纵向扫描
//从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，
//如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，
//当前列之前的部分为最长公共前缀。
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        for (int i = 0; i < strs[0].size(); i++) {
            for (int j = 1; j < strs.size(); j++) {
                if (strs[0][i] != strs[j][i]) {
                    return strs[0].substr(0, i) ;
                }
            }
        }
        return strs[0];
    }
};

3.单词

判断单词数：434

关键在于看该字符的前一个字符s[i-1]是否为空(这样可以遍历到所有字符而且不需要额外判断)，而不是看下一个字符s[i+1]是否为空

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int countSegments(string s) {
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ' && (i == 0 || s[i - 1] == ' ')) {
                // i==0必须写在s[i-1]前面，否则会溢出
                count++;
            }
        }
        return count;
    }
};

4.字符串的反转

反转字符串s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void reverseString(vector<char>& s) {
    //法一
    int n = s.size();
    for (int i = 0; i <= n / 2 - 1; i++) {
        swap(s[i], s[n - 1 - i]);
    }
    //法二：自带方法
    reverse(s.begin(),s.end());
    //法三：双指针
    int n = s.size();
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        swap(s[left], s[right]);
    }
}

注：关于min()，两个参数都必须是int类型，而s.size()是unsigned int类型，需要转换！(或者一开始就写成int n=s.size()，然后后面用n代替)

1
reverse(s.begin() + i, s.begin() + min(i + k, (int)s.size()));

反转字符串中的各个单词：557(进阶：包括前置后置以后中间与多个空格时，stringstream能够很好解决,只不过用到了额外空间ans和t并非原地解法,时间复杂度为O(n * m + k)，空间复杂度为O(n)。原地解法应该用双指针)

1
2
3
4
5
6
7
8
9
10
11
12
string reverseWords(string s) {
    stringstream ss(s);
    string t, ans;
    while (ss >> t) {
        reverse(t.begin(), t.end());
        if (!ans.empty()) {
            ans += " ";
        }
        ans += t;
    }
    return ans;
}

5.统计字符串(哈希表)

5-1.字符串中的第一个唯一字符：387

1
2
3
4
5
6
7
8
9
10
11
12
13
int firstUniqChar(string s) {
    int n = s.length();
    unordered_map<char, int> count;
    for (char ch : s) {
        count[ch]++;
    }
    for (int i = 0; i < n; i++) {
        if (count[s[i]] == 1) {
            return i;
        }
    }
    return -1;
}

还可以用find()和rfind():(空间复杂度为$O(1)$,时间复杂度$O(n^2)$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstUniqChar(string s) 
    {
        int i = 0;
        for( i = 0; i < s.size(); i++)
        {
            if(s.find(s[i]) == s.rfind(s[i]))//find()时间复杂度O(n)
            {
                return i;
            }
        }
        return -1;
    }
};

优化：记录频数改为记录索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int firstUniqChar(string s) {
        int n = s.length();
        unordered_map<char, int> position;
        for (int i = 0; i < n; i++) {
            if (position.count(s[i])) { //该字符已经出现过至少一次
                position[s[i]] = -1;
            } else {
                position[s[i]] = i; //只出现第一次的，记录下对应索引
            }
        }
        int first = n;
        for (auto& [_, pos] : position) {
            if (pos != -1) {
                first = min(first, pos);
            }
        }
        return first == n ? -1 : first;
    }
};

注：（用纯数组更快，尽管时间复杂度和空间复杂度相同，但是哈希表牵涉到建表、哈希碰撞等等）

方法二：使用队列queue（时间空间复杂度同法一）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int firstUniqChar(string s) {
        int n = s.length();
        unordered_map<char, int> position;
        queue<pair<char, int>> q;
        for (int i = 0; i < n; i++) {
            if (position.count(s[i])) { //该字符已经出现过至少一次
                position[s[i]] = -1;
                while (!q.empty() && position[q.front().first] == -1) {
                    q.pop();
                }
            } else {
                position[s[i]] = i; //只出现第一次的，记录下对应索引
                q.emplace(s[i], i);
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};

emplace() 是 C++ 中容器类的一个成员函数，用于在容器中就地构造元素，而不是通过拷贝或移动构造函数。

对于容器类（如 std::vector、std::map、std::unordered_map 等），emplace() 函数接受构造函数的参数，并在容器中直接构造一个新的元素，而不是将一个已经构造好的对象插入容器。

这种就地构造的方式可以避免额外的拷贝或移动操作，提高代码的效率。它对于大型对象或者不可复制/移动的对象特别有用。

注：关于哈希表

统计出现次数(时间复杂度$O(1)$)：

1
position.count(s[i]);

内部定义：

1
2
3
4
5
6
7
8
9
unordered_map<char, int> mp = {
        {'I', 1},  
        {'V', 5},   
        {'X', 10},   
        {'L', 50},
        {'C', 100}, 
        {'D', 500}, 
        {'M', 1000},
    };

遍历元素：

1
2
3
4
5
for (auto& [_, pos] : position) {
     if (pos != -1) {
          first = min(first, pos);
     }
}

这段代码使用了 C++17 中的结构化绑定（structured bindings）语法，用于遍历名为 position 的容器中的元素。遍历的顺序并不是unordered_map中元素的插入顺序，由于unordered_map没有保证元素的插入顺序，遍历顺序为乱序，从而影响结果。这是因为 std::unordered_map 使用哈希表实现，元素的存储位置是根据哈希值计算得到的，而不是按照插入顺序或其他特定顺序。

在每次循环迭代中，auto& [_, pos] 将容器中的键值对解构为两个变量 _ 和 pos。这里使用 _ 表示不需要使用的变量，而 pos 则表示容器中的值。

这两个for循环等价：

1
2
3
for(auto& [_,strArray]:mp){
    res.emplace_back(strArray);
}
1
2
3
4
5
6
for (auto it = mp.begin(); it != mp.end(); ++it) {
     res.emplace_back(it->second);
}

//注：unordered_map<string, vector<string>> mp;
//vector<vector<string>> res;详细可见49题

哈希表中的每个元素的类型为pair

1
2
3
4
5
unordered_map<char, int> mp;
vector<pair<char, int>> cnt;
for (auto& it : mp) { // it的类型是pair<char,int>
     cnt.emplace_back(it);
}

自定义比较方法(这里second值大的排在前面)

1
2
3
4
sort(cnt.begin(), cnt.end(),
     [](const pair<char, int>& a, const pair<char, int>& b) {
         return a.second > b.second;
     });

5-2.字符串找不同：389、242

一、计数：首先遍历字符串 s，对其中的每个字符都将计数值加 1；然后遍历字符串 t，对其中的每个字符都将计数值减 1。也可以使用哈希表，但法一空间复杂度较高。(如果是Unicode字符就老老实实用这种方法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    char findTheDifference(string s, string t) {
        int n = t.size(), n1 = s.size();
        unordered_map<char, int> count;
        for (int i = 0; i < n1; i++) {
            count[t[i]]++;
            count[s[i]]--;
        }
        count[t[n - 1]]++;
        for (auto& [pos, cnt] : count) {//pos是key,cnt是值。都用到了不能写为_
            if (cnt != 0) {
                return pos;
            }
        }
        return ' ';
    }
};

二、求和:将字符串 s 中每个字符的 ASCII 码的值求和，得到 $A_s$​；对字符串 t 同样的方法得到 $A_t$。两者的差值 $A_t-A_s$​ 即代表了被添加的字符。

三、位运算:将两个字符串拼接成一个字符串，则问题转换成求字符串中出现奇数次的字符。(136题也是位运算，用到了异或^)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int ret = 0;
        for (char ch: s) {
            ret ^= ch;//异或运算时ch会先被转换成ASCII码(此处为int型)
        }
        for (char ch: t) {
            ret ^= ch;
        }
        return ret;
    }
};

因为在s和t之中都出现的ch,在异或运算之后变成了0，相当于ret^s[0]^s[1]...^t[0]^t[1]...=0^(s[0]^t[0])^(s[1]^t[1])^...^t[more]=0^0^0^...^0^t[more]=t[more].

(这里假设s[0]==t[0],s[1]==t[1]…)

容器角度一般的优化思路。完整的是多容器->多次新建容器->单容器->数组->二进制位。

5-3.字母异位词分组：49

法一：排序(由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。)可以不用sort()来排序以节省时间开销，但是可能增加空间开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> res;
        for (auto it = mp.begin(); it != mp.end(); it++) {
            res.emplace_back(it->second);
        }
        return res;
    }
};

法二：计数(将每个字母出现的次数使用字符串表示，作为哈希表的键。时间复杂度更低，空间复杂度更高)

5-4.根据字符串出现频率排序：451

桶排序：速度比sort()快

1.遍历字符串，统计每个字符出现的频率，同时记录最高频率 maxFreq；

2.创建桶，存储从 1 到 maxFreq 的每个出现频率的字符；

3.按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符，然后将每个字符按照出现频率拼接到排序后的字符串。

5-5.求连续递增子串的个数，并去重：467

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int k = 0;
        vector<int> dp(26);
        for (int i = 0; i < s.length(); i++) {
            if (i && (s[i] - s[i - 1] + 26) % 26 == 1) { // s[i-1]在s[i]前面
                k++;
            } else {
                k = 1;
            }
            dp[s[i] - 'a'] = max(dp[s[i] - 'a'], k);
        }
        return accumulate(dp.begin(), dp.end(), 0);
    }
};

5-6.URL的解密与加密：535

如果想要实现相同的 URL 加密成同一个 TinyURL，则额外保存一个从 URL到 TinyURL 的映射。

注：int->string:to_string(intVar);

string->int:stoi(stringVar);

关于随机数

time(0)函数返回当前的系统时间（从某一时刻开始的秒数），而srand函数是用来设置随机数生成器的种子。将time(0)的返回值传递给srand函数，可以使用当前时间作为随机数生成器的种子，从而使得每次程序运行时生成的随机数序列都不同。

在C++中，通常在使用随机数生成函数rand之前，会调用srand(time(0))来初始化随机数生成器。这样可以确保每次程序运行时都会生成不同的随机数序列，因为种子不同会导致不同的随机数序列。之后就可以使用randomNumber=rand();