字符串专题

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode 38. Count and Say

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution { //一个模拟问题
public:
    string countAndSay (int n) {
        string s = "1";
        for (int i = 0; i < n - 1; i++) {
            string ns;
            for(int j = 0; j < s.size(); j++) {
                int k = j;
                while (k < s.size() && s[k] == s[j]) k++;
                ns += to_string(k - j) + s[j] ;  //这里要用`+=` ，  或者 ns = ns +... ，不要用 ns = ... + ns， 因为这是字符串相加， 要顾及顺序
                j = k - 1; //因为下一步循环时， j要+1之后 到达k的位置， 所以这里要如此更新一下j。
            }
            s = ns; //把这一次的ns值赋给 s， 这样下次循环时， s中存放的就是上一次的字符串了。
        }

        return s;
    }
}；

to_string :

1
2
3
4
5
6
7
8
9
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val)

49. Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> hash;  //first 是string ，  second是vector<string>
/*
        for (int i = 0; i < strs.size(); i++) {
            string t = strs[i];
            sort(t.begin(), t.end());
            hash[t].push_back(strs[i]);
        }
        */
        for (auto item : strs) {    //这里用range for 似乎更好
            string t = item;          //sort(x.begin(), x.end())之后会改变x，因此这里设一个string来缓存之。
            sort(t.begin(), t.end());  //对string也可以用 sort()排序 （这里是字典序）
            hash[t].push_back(item); 
        }

        for (auto x : hash) 
            res.push_back(x.second); //x是hash中的一个元素， 这里x.second是 x这个元素的vector<string>部分
        return res;        
    }
};

151. Reverse Words in a String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string reverseWords(string s) {
        int k = 0; //因为会有很多多余空格， 我们最终要把这些空格压缩掉，即把单词从后向前复制， k就是复制操作后的下一个位置。
        for (int i = 0; i < s.size(); i++) {
            while(i < s.size() && s[i] == ' ') i++; //跳过开头所有空格。
            if(i == s.size()) break;   //跳过结尾的空格
            int j = i;
            while (j < s.size() && s[j] != ' ') j++; //这样， [i , j)就是一个单词了
            reverse(s.begin() + i, s.begin() + j);
            if (k) s[k++] = ' '; //这样保证反转之后，每个单词之间只有一个空格
            while(i < j) s[k++] = s[i++]; //向前填充
        }
        s.erase(s.begin() + k, s.end()); //k及之后的位置都是多余的了。
        reverse(s.begin(), s.end());    //最后反转整个字符串即可完成
        return s;
       
    }
};

erase()

  1. basic_string & erase(size_type pos=0, size_type n=npos);
    从给定起始位置pos处开始删除，要删除的字符长度为 n， 返回值为修改后的string对象的引用。

  2. iterator erase(const_iterator position)
    删除迭代器位置处的单个字符，并返回下个元素的迭代器。

  3. iterator erase(const_iterator first, const_iterator last)
    删除迭代器[first, last)区间的所有字符,返回一个指向被删除的最后一个元素的下一个字符的迭代器。

  4. 除了erase方法用于删除string中的元素, void pop_back();方法也可以用来删除元素, 但是只能删除string的最后一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <string>
#include <algorithm>

using namespace std;

int main() {
	string s = "Harry Potter";
	int i = 0;
	int j = i;
	while (j < s.size() && s[j] != ' ') j++;
	
	//s.erase(2, 2);                     1.
	//s.erase(s.begin() + j);            2.
	//s.erase(s.begin() + j, s.end());   3.

	cout << s << endl;

	return 0;
}

输出分别为
1.Hay Potter
2.HarryPotter
3.Harry

string::find()

int vis = a.find(b) 从string a 开头开始查找第一个遇到的string b, 返回string a中所匹配字符串的第一个字符的下标位置，找不到则返回-1.

每个单词之间可能不止有一个空格

reverse(s.beign(), s.end())

关于 reverse(s.beign(), s.end()); 这里特别注意 reverse()的两个迭代器参数 是 前闭后开的。
程序中使用的reverse(s.begin() + i, s.end() + j) 也是如此。
如图， reverse(s.begin() + i, s.end() + j) 实际的反转范围是红圈内的部分。

下面这个套路很常用

1
2
int j = i;
while (j < s.size() && s[j] != '.') j++;

165. Compare Version Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int compareVersion(string s1, string s2) {
        int i = 0, j = 0; // 分别指向s1 , s2的起点
        while(i < s1.size() || j < s2.size())  { //这里要用 ||  ， 用来判断 s1: 1.0000  s2 : 1.0这种情况
            int x = i, y = j;
            while (x < s1.size() && s1[x] != '.') x++;
            while (y < s2.size() && s2[y] != '.') y++;
            int a = i == x ? 0 : atoi(s1.substr(i, x - i).c_str()); //首先要做一个判断： 如果i == x 也就是说 i已经到了尽头...
            int b = j == y ? 0 : atoi(s2.substr(j, y - j).c_str());
            if (a > b) return 1;
            if (a < b) return -1;
            i = x + 1, j = y + 1; //更新i , j 让他们指向 '.' 的下一个字符（即一个数字字符）
        }
        return 0;
    }
};

比较版本号。

c_str() 返回字符串所在字符数组的起始地址

atoi() 的参数必须是字符数组的指针

  • stoi() 参数是 const string*

  • 会做范围检查， 默认范围是在int的范围内的， 如果越界就会 runtime error

  • atoi() 参数是 const char, 因此要调用 c_str() 把string转换成 const char

  • aoti()不会做范围检查，如果超出上界，则输出上界； 超出下界， 则输出下界。

substr()

1
2
3
4
5
6
7
8
9
#include<string>
#include<iostream>
using namespace std;
int main()
{
　　string s("12345asdf");
　　string a = s.substr(0,5);     //获得字符串s中从第0位开始的长度为5的字符串
　　cout << a << endl;
}

上述程序输出为： 12345

  • s.substr(pos, n) 返回一个string, 包含s中从pos开始的n个字符的拷贝（pos默认值是0， n默认值是s.size() - pos， 即无参数会默认拷贝整个s）
  • 若pos的值超过了string的大小，则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾

929. Unique Email Addresses

STL C++11 还有很多要总结的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> hash;                  //这里不需要映射，所以用 set即可（unordered_set<string>）
        for (auto email : emails) {
            int at = email.find('@');
            string name;
            for (auto c : email.substr(0, at)) {      //遍历string里的每一个元素
                if (c == '+') break;
                if (c =='.') continue;                //这里的 break, continue用法精髓
                name += c;                            //拼接字符串 用+= 似乎效率更高
            }
            string domain = email.substr(at + 1);
            name += '@' + domain;
            hash.insert(name);                        //向关联容器中insert一个元素
        }
        return hash.size();                
    }
};

5. Longest Palindromic Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        
        for (int i = 0; i < s.size(); i++) { //枚举回文串中心点
            for(int j = i, k = i; j >= 0 && k < s.size() && s[j] == s[k]; j--, k++) { //s是奇数
                if(k - j + 1 > res.size()) 
                    res = s.substr(j, k - j + 1);
                
            }
            
            for(int j = i, k = i + 1; j >= 0 && k < s.size() && s[j] == s[k]; j--, k++) {//s是偶数时有两个中心点
                if(k - j + 1 > res.size()) 
                    res = s.substr(j, k - j + 1);
                
            }
        }
        return res;
    }
};

双指针 暴力枚举

3. Longest Substring Without Repeating Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int res = 0;
        for (int i =0, j = 0; i < s.size(); i++) {
            hash[s[i]]++;  //如果有重复字符，那么一定是新加进来的这个s[i]
            while (hash[s[i]] > 1) hash[s[j++]]--; // j指针移动到重复字符的下一个位置
            res = max(res, i - j + 1);
        }
        return res;
    }
};

双指针 暴力枚举

0%