LeetCode笔记—字符串篇

C++string类总结

一、string的初始化

使用string类型,必须引入相关头文件string,注意区分不是string.h,string.h是c语言字符串头文件。

1
2
3
#include<string>
using namespace std;
string str;

二、string的比较等操作

可以用 ==、>、<、>=、<=、和!=比较字符串,可以用+或者+=操作符连接两个字符串,并且可以用[]获取特定的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
cout << "Please input your name:"<<endl;
cin >> str;
if( str == "Li" ) // 字符串相等比较
cout << "you are Li!"<<endl;
else if( str != "Wang" ) // 字符串不等比较
cout << "you are not Wang!"<<endl;
else if( str < "Li") // 字符串小于比较,>、>=、<=类似
cout << "your name should be ahead of Li"<<endl;
else
cout << "your name should be after of Li"<<endl;
str += ", Welcome!"; // 字符串+=
cout << str<<endl;
for(int i = 0 ; i < str.size(); i ++)
cout<<str[i]; // 类似数组,通过[]获取特定的字符
return 0;
}

三、string的特性描述

1
2
3
4
5
6
int capacity()const;    //返回当前容量(即string中不必增加内存即可存放的元素个数)
int max_size()const; //返回string对象中可存放的最大字符串的长度
int size()const; //返回当前字符串的大小
int length()const; //返回当前字符串的长度
bool empty()const; //当前字符串是否为空
void resize(int len,char c); //把字符串当前大小置为len,多去少补,多出的字符c填充不足的部分

四、string的查找

1
2
3
4
size_type find( const basic_string &str, size_type index );  //返回str在字符串中第一次出现的位置(从index开始查找),如果没找到则返回string::npos
size_type find( const char *str, size_type index ); // 同上
size_type find( const char *str, size_type index, size_type length ); //返回str在字符串中第一次出现的位置(从index开始查找,长度为length),如果没找到就返回string::npos
size_type find( char ch, size_type index ); // 返回字符ch在字符串中第一次出现的位置(从index开始查找),如果没找到就返回string::npos

五、其他常用函数

1
2
3
4
5
6
7
8
9
string &insert(int p,const string &s);  //在p位置插入字符串s
string &replace(int p, int n,const char *s); //删除从p开始的n个字符,然后在p处插入串s
string &erase(int p, int n); //删除p开始的n个字符,返回修改后的字符串
string substr(int pos = 0,int n = npos) const; //返回pos开始的n个字符组成的字符串
void swap(string &s2); //交换当前字符串与s2的值
string &append(const char *s); //把字符串s连接到当前字符串结尾
void push_back(char c) //当前字符串尾部加一个字符c
const char *data()const; //返回一个非null终止的c字符数组,data():与c_str()类似,用于string转const char*其中它返回的数组是不以空字符终止,
const char *c_str()const; //返回一个以null终止的c字符串,即c_str()函数返回一个指向正规C字符串的指针, 内容与本string串相同,用于string转const char*

LeetCode题目

反转字符串

题目

编写一个函数,其作用是将输入的字符串反转过来。

示例 1:

1
2
输入: "hello"
输出: "olleh"

示例 2:

1
2
输入: "A man, a plan, a canal: Panama"
输出: "amanaP :lanac a ,nalp a ,nam A"

思路

对空间没有要求,新建一个字符串str2,从尾到头依次遍历字符串str1,将遍历的字符插入到字符串str2的末尾,输出str2即可。

参考代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
string reverseString(string s) {
string res;
int n=s.size();
for(int i=n-1;i>=0;i--)
res.push_back(s[i]);
return res;
}
};

颠倒整数

题目

给定一个 32 位有符号整数,将整数中的数字进行反转。

示例 1:

1
2
输入: 123
输出: 321

示例 2:

1
2
输入: -123
输出: -321

示例 3:

1
2
输入: 120
输出: 21

注意:

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

思路

依次取出整数的末位,将其放入到反转后的整数中。注意反转完后要判断是否溢出。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int reverse(int x) {
int y = x > 0 ? x : -x;
long long res = 0;
while (y > 0) {
res = res * 10 + (y % 10);
y = y / 10;
}
if (x < 0)
res = -res;
if (res<-(int)pow(2.0, 31) || res>(int)pow(2.0, 31) - 1)
return 0;
return res;
}
};

字符串中的第一个唯一字符

题目

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

案例:

1
2
3
4
5
s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项:您可以假定该字符串只包含小写字母。

思路

先统计每个字母出现的次数,再遍历字符串,找到第一个出现次数为1的字符。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int firstUniqChar(string s) {
int a[26]={0};
int len=s.size();
for(int i=0;i<len;i++)
a[s[i]-'a']++;
for(int i=0;i<len;i++){
if(a[s[i]-'a']==1)
return i;
}
return -1;
}
};

有效的字母异位词

题目

给定两个字符串 st ,编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

思路

利用哈希的思想,建立一个数组来存放字符串s中每个字符出现的次数,依次遍历字符串t,将数组中对应字符出现的次数减一,最后在判断数组中每个元素的出现次数是否为0.这里因为只考虑小写字母,因此建立一个长度为26的数组即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool isAnagram(string s, string t) {
int arry[26]={0};
int len1=s.size();
int len2=t.size();
if(len1 != len2)
return false;
for(int i=0;i<len1;i++)
arry[s[i]-'a']++;
for(int i=0;i<len2;i++)
arry[t[i]-'a']--;
for(int i=0;i<26;i++)
if(arry[i]!=0)
return false;
return true;
}
};

进阶

如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

这种情况的话就建立一个map来记录每个字符及每个字符出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
bool isAnagram(string s, string t) {
map<char,int> myMap;
int len=s.size();
int len1=t.size();
if(len!=len1)
return false;
for(int i=0;i<len;i++){
if(myMap.find(s[i])!=myMap.end())
myMap[s[i]]++;
else
myMap[s[i]]=1;
}
for(int i=0;i<len1;i++){
if(myMap.find(t[i])!=myMap.end()){
if(myMap[t[i]]==0)
return false;
myMap[t[i]]--;
}
else
return false;

}
for(int i=0;i<len;i++)
if(myMap[s[i]]!=0)
return false;
return true;
}
};

验证回文字符串

题目

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

1
2
输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

1
2
输入: "race a car"
输出: false

思路

因为只考虑字母和数字字符,并且忽略字母的大小写。所以要先对源字符串进行处理,提取出我们需要的字符,再进行判断。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool isPalindrome(string s) {
int len=s.size();
string res="";
for(int i=0;i<len;i++){
if((s[i]>='0' && s[i]<='9') || (s[i]>='a' && s[i]<='z'))
res+=s[i];
if(s[i]>='A' && s[i]<='Z')
res+=s[i]-'A'+'a';
}
int len1=res.size();
if(len1==0)
return true;
for(int i=0;i<len1/2;i++)
if(res[i]!=res[len1-1-i])
return false;
return true;
}
};

字符串转整数 (atoi)

题目

实现 atoi,将字符串转为整数。

该函数首先根据需要丢弃任意多的空格字符,直到找到第一个非空格字符为止。如果第一个非空字符是正号或负号,选取该符号,并将其与后面尽可能多的连续的数字组合起来,这部分字符即为整数的值。如果第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

字符串可以在形成整数的字符后面包括多余的字符,这些字符可以被忽略,它们对于函数没有影响。

当字符串中的第一个非空字符序列不是个有效的整数;或字符串为空;或字符串仅包含空白字符时,则不进行转换。

若函数不能执行有效的转换,返回 0。

说明:

假设我们的环境只能存储 32 位有符号整数,其数值范围是 $[−2^{31}, 2^{31}− 1]$。如果数值超过可表示的范围,则返回 INT_MAX ($2^{31}$− 1) 或 INT_MIN (−$2^{31}$) 。

示例 1:

1
2
输入: "42"
输出: 42

示例 2:

1
2
3
4
输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3:

1
2
3
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ,因为它的下一个字符不为数字。

示例 4:

1
2
3
4
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:

1
2
3
4
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

思路

根据题意,首先遍历字符串找到第一个非空字符。然后判断该字符如果是字母则直接返回0;否则的话将该字符和之后的字符组合起来,形成整数,如果形成的整数超过范围,则返回0;否则返回该整数。注意有多个返回0的情况都要考虑到。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
int myAtoi(string str) {
int len = str.size();
if (len == 0)
return 0;
int i = 0;
for (;i < len && str[i] == ' ';i++);
if (i == len)
return 0;
else if (str[i] != '-' && str[i] != '+' && (str[i]<'0' || str[i]>'9'))
return 0;
else {
int j = i;
if (str[i] == '-' || str[i] == '+')
j++;
long long res = 0;
for (;j < len && (str[j] >= '0' && str[j] <= '9');j++) {
res = res * 10 + (str[j] - '0');
if (res > (int)pow(2.0, 31)) {
if (str[i] == '-')
return -(int)pow(2.0, 31) - 1;
else
return (int)pow(2.0, 31);
}
}
if (str[i] == '-')
res = -res;

return res;
}

}
};

实现strStr()

题目

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1

示例 1:

1
2
输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

1
2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

分析

此题是字符串的模式匹配问题,在题目没对时间复杂度做要求的情况下课直接暴力匹配

参考代码

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:
int strStr(string haystack, string needle) {
int len1=haystack.size();
int len2=needle.size();
if(len2==0)
return 0;
if(len1==0 || len2>len1)
return -1;
for(int i=0;i<len1;i++){
int j=0;
while(j<len2 && haystack[i]==needle[j]){
i++;
j++;
}
if(j==len2)
return i-j;
else
i=i-j;
}
return -1;
}
};

进阶

字符串的模式匹配问题可以使用经典的KMP算法来解决,KMP的关键思路是求解next数组。(不知道为啥,用了KMP,战胜的人也不多。。。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int strStr(string haystack, string needle) {
int len1=haystack.size();
int len2=needle.size();
int* next = new int[len2];
getNext(next,needle);
int i=0,j=0;
while(i<len1 && j<len2){
if(j==-1 || haystack[i]==needle[j]){//注意这里一定要先判定j==-1,不然判定needle[-1]会越界
i++;
j++;
}
else
j=next[j];
}
if(j==len2)
return i-j;
else
return -1;
}
void getNext(int next[],string s){
int k=-1;
int len=s.size();
int j=0;
next[0]=-1;
while(j<len-1){ //注意这里是len-1,不然下面next[j]=k会越界
if(k==-1 || s[j]==s[k]){
j++;
k++;
next[j]=k;
}
else
k=next[k];
}

}
};

报数

题目

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

1
2
3
4
5
1.     1
2. 11
3. 21
4. 1211
5. 111221

1 被读作 "one 1" ("一个一") , 即 11
11 被读作 "two 1s" ("两个一"), 即 21
21 被读作 "one 2", “one 1""一个二" , "一个一") , 即 1211

给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。

注意:整数顺序将表示为一个字符串。

示例 1:

1
2
输入: 1
输出: "1"

示例 2:

1
2
输入: 4
输出: "1211"

思路

字符串的常规操作,依次遍历字符串,统计每个字符出现的次数,作为新字符串的内容。

参考代码

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 countAndSay(int n) {
if (n==1)
return "1";
string res="1";
for(int i=1;i<n;i++){
int len=res.size();
string temp="";
for(int j=0;j<len;j++){
int p=j;
for(;p<len && res[j]==res[p];p++);
int x=p-j;
temp=temp+to_string(x)+res[j];
j=p-1;
}
res=temp;
}
return res;
}
};

最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例 1:

1
2
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

1
2
3
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z

思路

先设最长前缀res为第一个字符串,然后拿res依次和后面的字符串作比较。当在和一个字符串作比较时,若res中的当前字符和改字符串中的字符不相等,则截掉res当前字符及其后面的所有字符,然后和下一个字符串比较。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()==0)
return "";
else if(strs.size()==1)
return strs[0];
else{
string res=strs[0];
int i=1;
int len=strs.size();
while(i<len){
int len1=res.size();
if(len1==0)
return "";
int len2=strs[i].size();
if(len2<len1)
res.erase(len2,len1-len2);
int j=0;
while(j< len1 && j<len2){
if(res[j] == strs[i][j]){
j++;
continue;
}
else{
res.erase(j,len1-j);
break;
}
}
i++;
}
return res;
}
}
};

相关函数

1
res.erase(pos,len)	//删除位置pos后面长度为len的字符。注意该字符串为string类型