【C++】9道经典面试题带你玩转string类
一.把字符串转换成整数(atoi)
题目链接:
https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/
题目描述:
请你来实现一个
myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的atoi函数）。 函数myAtoi(string s)的算法如下：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为
0。必要时更改符号（从步骤 2 开始）。 - 如果整数数超过 32 位有符号整数范围
[
,
] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于
的整数应该被固定为
，大于
的整数应该被固定为
。
- 返回整数作为最终结果。
注意：
- 本题中的空白字符只包括空格字符
' '。 - 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
题目详情:
解题思路:
- 丢弃无用的前导空格
- 录入有效数据
- 判断正负性后返回数据
本题程序编写思路不难,需要注意的细节问题很多,稍微处理不好就可能导致一千多个测试点中的几个无法通过.因此大家在解题时一定要特别小心注释中标注的细节问题.
解题代码:
#define INT_MAX 2147483648
class Solution {
public:
int myAtoi(string str) {
long long int num=0;
int sign_flag=0;//标志符号
int neg_sign_flag=0;//标志负号
int num_flag=0;//标志数字
int i=0;
//丢弃无用的前导空格
while(str[i]==' ')
i++;
//开始录入有效数据
for(;str[i]!=' '&&i<str.size();i++){
//如果录入到数字数据,将其转换成整数
if(str[i]>='0'&&str[i]<='9'){
num=num*10+(str[i]-'0');
//标志已经开始录入数字
num_flag=1;
}
//如果录入到负号
else if(str[i]=='-'){
//如果该'-'录入先于符号和数字,则认为该数字为负数,并标志该数已经存在符号位
//否则判定无效数据,录入结束
if(sign_flag==1||num_flag==1)
break;
sign_flag=1;
neg_sign_flag=1;
}
//如果录入到正号
else if(str[i]=='+'){
//如果该'+'录入先于符号和数字,则认为该数字为正数,并标志该数已经存在符号位
//否则判定无效数据,录入结束
if(sign_flag==1||num_flag==1)
break;
sign_flag=1;
}
//如果录入到其他无效数据,录入结束
else
break;
//如果循环录入过程中数字已经大于INT_MAX
//则截断数据,停止录入
if(num>INT_MAX)
break;
}
//如果num没超过范围
if(num<INT_MAX)
//有负号返回负的它本身,没有负号返回它本身
return pow(-1,neg_sign_flag)*num;
//如果num超过了范围,是负数返回-INT_MAX,不是负数返回INT_MAX-1
else
return pow(-1,neg_sign_flag)*INT_MAX-1+neg_sign_flag;
}
};提交运行:
二.字符串相加
题目链接:
https://leetcode.cn/problems/add-strings/
题目描述:
给定两个字符串形式的非负整数
num1和num2，计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库（比如BigInteger）， 也不能直接将输入的字符串转换为整数形式。
题目详情:
解题思路:
我们的解题思路是从两个字符串的末位逐位相加,记录本位的结果和进位信息,将本位结果加等到结果字符串上,最后再统一逆置一下这个结果字符串即可.
解题代码:
class Solution
{
public:
string addStrings(string num1, string num2)
{
string ret;
int end1=num1.size()-1;
int end2=num2.size()-1;
int carry=0;//标志进位
while(end1>=0||end2>=0||carry!=0)
{
int val1 = (end1<0?0:num1[end1]- '0');
int val2 = (end2<0?0:num2[end2]- '0');
int sum = val1 + val2 + carry;
carry=sum/10;
sum%=10;
ret+=('0'+sum);
end1--;
end2--;
}
reverse(ret.begin(),ret.end());
return ret;
}
};提交运行:
三.反转字符串
题目链接:
https://leetcode.cn/problems/reverse-string/
题目描述:
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
题目详情:
解题思路:
思路一:直接调用逆置库函数reverse()
思路二:前后指针元素互换 我们可以使用一个指针从前向后迭代,一个指针从后向前迭代,每迭代一个元素,两个指针指向的元素互换,直到两个指针相遇.
解题代码:
思路一解题代码:
//库函数法
class Solution
{
public:
void reverseString(vector<char>& s)
{
reverse(s.begin(),s.end());
}
};提交运行:
思路二解题代码:
//前后指针互换法
class Solution
{
public:
void reverseString(vector<char>& s)
{
int end=s.size()-1;
int begin=0;
while(begin<=end)
{
char tmp=s[begin];
s[begin]=s[end];
s[end]=tmp;
begin++;
end--;
}
}
};提交运行:
四.字符串中的第一个唯一字符
题目链接:
https://leetcode.cn/problems/first-unique-character-in-a-string/
题目描述:
给定一个字符串
s，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回-1。
题目详情:
解题思路:
这道题的解题思路比较暴力,就是用双循环找第一个唯一的元素即可,如果直到外层循环结束都没有找到,则返回-1即可.
解题代码:
class Solution {
public:
int firstUniqChar(string s)
{
for(int i=0;i<s.size())
{
int flag=0;
for(int j=0;j<s.size();j++)
{
if(s[j]==s[i]&&j!=i)
{
flag=1;
break;
}
}
if(flag)
{
i++;
}
else
{
return i;
}
}
return -1;
}
};提交运行:
五.字符串最后一个单词的长度
题目链接:
题目描述:
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
题目详情:
解题思路:
该题我们利用string类的成员函数先找到最后一个空格的位置,而后用字符串的总长度减去最后一个空格的位置再减1即为最后一个单词的长度.图示如下:
解题代码:
#include <iostream>
using namespace std;
int main()
{
string str;
getline(cin,str);
//找到最后一个空格的位置
int pos=str.rfind(' ');
//字符串总长度减去最后一个空格位置再减1就是最后一个单词的长度
cout<<str.size()-pos-1<<endl;
}提交运行:
六.验证回文串
题目链接:
https://leetcode.cn/problems/valid-palindrome/
题目描述:
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串
s，如果它是 回文串 ，返回true；否则，返回false。
题目详情:
解题思路:
- 将字符串中的有效数据项(包括字母和数字字符)摘到新字符串中
- 验证摘出的新字符串是否是回文串
- 注意验证回文串时有三个条件(回文判断条件&&大小写回文判断条件&&数字回文判断条件,这三个有一个不满足就返回false)
解题代码:
class Solution {
public:
bool isPalindrome(string s) {
string st1="";
//将有效的数据项摘到一个新字符串里方便后续判断
for(auto e:s)
{
if((e>='a'&&e<='z')||(e>='A'&&e<='Z')||(e>='0'&&e<='9'))
{
st1+=e;
}
}
//验证摘出的有效数据是否是回文串
string::iterator it=st1.begin();
string::iterator eit=st1.end()-1;
while(it<=eit)
{
//回文判断条件&&大小写回文判断条件&&数字回文判断条件,这三个有一个不满足就返回ifalse
if((*it!=*eit) && (*it+32!=*eit) && (*it-32!=*eit)||((*it>='0'&&*it<='9')&&*it!=*eit))
return false;
//如果满足,则继续向后验证
it++;
eit--;
}
return true;
}
};提交运行:
七.反转字符串 II
题目链接:
https://leetcode.cn/problems/reverse-string-ii/
题目描述:
给定一个字符串
s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
题目详情:
解题思路:
对于这道题,我们以k为组距,分组,创建一个新的字符串,偶数组正序拷贝进新字符串,单数组反序拷贝进新字符串,最后一组单独考虑,是偶数就正序追加在字符串末尾,是单数就反序拷贝在字符串末尾即可. 情况一图示如下:
情况二图示如下:
解题代码:
class Solution {
public:
string reverseStr(string s, int k) {
string tmp="";
int n=s.size()/k+1;
//以k为组距,分组,双数组正加,单数组反加,最后一组单独考虑
for(int i=0;i<n-1;i++)
{
if(i%2==0)
{
//反着加
for(int j=i*k+k-1;j>=i*k;j--)
tmp+=s[j];
}
else
{
//顺着加
for(int j=i*k;j<=i*k+k-1;j++)
tmp+=s[j];
}
}
if(n%2==0)
{
//组数为偶数,最后一组正加
while(tmp.size()<s.size())
tmp+=s[tmp.size()];
}
else
{
//组数为奇数,最后一组反加
for(int i=s.size()-1;tmp.size()<s.size();i--)
tmp+=s[i];
}
return tmp;
}
};提交运行:
八.反转字符串中的单词 III
题目链接:
https://leetcode.cn/problems/reverse-words-in-a-string-iii/
题目描述:
给定一个字符串
s，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
题目详情:
解题思路:
迭代寻找空格,每当找到空格的时候就逆置新空格和旧空格之间的单词.直到逆置完最后一个单词,返回逆置后的字符串即可.
解题代码:
class Solution {
public:
string reverseWords(string s) {
string tmp = "";
int pos = 0;
int prev_pos = 0;
//迭代向后寻找空格,逆置空格之间的单词字符
while (prev_pos <= s.size())
{
prev_pos = s.find_first_of(" ", pos + 1);
if (prev_pos == string::npos)
break;
for (int i = prev_pos - 1; i >= pos; i--)
{
tmp += s[i];
}
if (pos == 0)
{
tmp += ' ';
}
pos = prev_pos;
}
//逆序最后一个单词
for (int i = s.size() - 1; i >= pos; i--)
{
tmp += s[i];
}
//去掉最后一个多的空格
if(pos!=0)
tmp.resize(tmp.size()-1);
return tmp;
}
};提交运行:
九.字符串相乘
题目链接:
https://leetcode.cn/problems/multiply-strings/
题目描述:
给定两个以字符串形式表示的非负整数
num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
题目详情:
解题思路:
要计算字符串乘法,我们首先要从位与位的乘法下手,先求出位与位相乘的结果字符串:
再将该位与另一个字符串的所有位与位的乘积都加起来,就得到了位与'数'(字符串)相乘的结果:
再将该字符串的所有位与另一个字符串的所有位的乘积加起来,就得到了'数'与'数'相乘的结果:
综上所述,因为我们在前面的题目中实现过字符串加法,所以在这里直接使用即可:
解题代码:
class Solution {
public:
string addStrings(string num1, string num2)
{
string bit;
int end1 = num1.size() - 1;
int end2 = num2.size() - 1;
int carry = 0;
while (end1 >= 0 || end2 >= 0 || carry != 0)
{
int val1 = (end1 < 0 ? 0 : num1[end1] - '0');
int val2 = (end2 < 0 ? 0 : num2[end2] - '0');
int ret = val1 + val2 + carry;
carry = ret / 10;
ret %= 10;
bit += ('0' + ret);
end1--;
end2--;
}
reverse(bit.begin(), bit.end());
return bit;
}
string multiply(string num1, string num2)
{
//不需要有进位,因为每次算完有加法函数帮忙加
string mul = "";
string ret = "0";
string flag = "0";
int end1 = num1.size() - 1;
int end2 = num2.size() - 1;
for (int i = end2; i >= 0; i--)
{
//这个bit得搞成string,创建一个tmp记录乘积
int tmp = 0;
string bit = "";
mul = "";
int val2 = (i < 0 ? 0 : num2[i] - '0');
for (int j = end1; j >= 0; j--)
{
bit = "";
int val1 = (j < 0 ? 0 : num1[j] - '0');
tmp = val1 * val2;
while (tmp)
{
bit += ('0' + tmp % 10);
tmp /= 10;
}
reverse(bit.begin(), bit.end());
int num0 = end1 + end2 - i - j;
while (num0-- && bit!=flag)
{
bit += '0';
}
mul = addStrings(bit, mul);
}
ret = addStrings(ret, mul);
}
return ret;
}
};提交运行:
结语
希望通过上面的题目能使大家对string类的理解以及运用能够更上一层楼,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
腾讯云开发者
