目录
题目一：仅仅反转字母
题目描述：
给定一个字符串，返回“反转后的”字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
示例：
输入：“a-bC-dEf-ghIj”
输出：“j-Ih-gfE-dCba”
思路：
使用两个指针，开始时头指针指向字符串开头，尾指针指向字符串末尾（’\0’的前一个字符）。头指针先向后寻找待反转字母，尾指针再向前寻找待反转字母，然后反转这两个待反转字母即可。重复该步骤，直到头指针和尾指针发生错位为止。
动图演示：
代码
class Solution
{
public:
//判断字符ch是否是字母
bool IsLetter(char ch)
{
if ((ch >= 'a'&&ch <= 'z')
|| (ch >= 'A'&&ch <= 'Z'))
return true;
else
return false;
}
//仅仅反转字母
string reverseOnlyLetters(string s)
{
if (s.empty()) //若s为空字符串，则返回其本身
return s;
size_t begin = 0, end = s.size() - 1; //定义头指针和尾指针，用于反转字母
while (begin < end) //当还有字母可反转时，循环继续
{
while (begin < end && !IsLetter(s[begin])) //头指针寻找待反转字母
begin++;
while (begin < end && !IsLetter(s[end])) //尾指针寻找待反转字母
end--;
swap(s[begin], s[end]); //交换这两个待反转字母
begin++;
end--;
}
return s; //返回反转后的字符串
}
};
注意：若传入的字符串尾空字符串，则直接返回即可。
题目二：字符串中的第一个唯一字母
题目描述：
给定一个字符串，找到它的第一个不重复的字母，并返回它的索引。如果不存在，则返回-1。
示例：
s = “loveleetcode”
返回 2
思路：
用一个含义26个元素的数组统计26个字母在字符串中出现的次数，然后再遍历一次字符串，寻找字符串中第一个只出现一次的字母，并返回它的索引，若不存在，则返回-1。
代码：
class Solution
{
public:
int firstUniqChar(string s)
{
size_t table[26] = { 0 };
//统计26个字母在字符串中出现的次数
for (size_t i = 0; i < s.size(); i++)
{
table[s[i] - 'a']++;
}
//寻找字符串中的第一个只出现一次字母
for (size_t i = 0; i < s.size(); i++)
{
if (table[s[i] - 'a'] == 1)
return i; //返回下标索引
}
return -1; //不存在，返回-1
}
};
题目三：字符串最后一个单词的长度
题目描述：
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。
示例：
输入：“hello CSDN”
输出：4
思路：
先找到字符串中最后一个空格的位置，空格之后的字符个数就是最后一个单词的长度。若字符串中不存在空格，则字符串的长度就是最后一个单词的长度。
重点：
该题的思路非常容易想到，但该题真正的难点不是如何求得字符串中最后一个单词的长度，而是如何读取一个含有空格的字符串。因为操作符>>读取到空格便会停止，所以不能使用>>读取目标字符串，这时我们就需要用到getline函数了，该函数便可以读取含有空格的内容。
代码：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
getline(cin, s); //从cin读取一行含有空格的字符串
size_t pos = s.rfind(' '); //获取字符串中最后一个空格的位置
if (pos == string::npos) //字符串中不含空格
{
//输出字符串的长度
cout << s.size() << endl;
}
else //字符串中含有空格
{
//输出字符串的长度 - 最后一次出现空格的位置 - 1
cout << s.size() - pos - 1 << endl;
}
return 0;
}
题目四：验证回文串
题目描述：
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
示例：
输入：“A man, a plan, a canal: Panama”
输出：true
思路：
题目中说到可以忽略字母大小写，即’a’可与’a’匹配，‘a’还可与’A’匹配，所以我们可以先将字符串中所有的大写字母转换为小写字母，然后再进行进一步判断。
判断时使用两个指针，开始时头指针指向字符串开头，尾指针指向字符串末尾（’\0’的前一个字符）。头指针先向后寻找待判断的字母或数字字符，尾指针再向前寻找待判断的字母或数字字符，然后判断这两个字符是否相等，若相等，则继续下一次判断；若不相等，则该字符串不是回文串。重复该步骤，直到头指针和尾指针发生错位为止，此时便可确定该字符串是回文串。
代码：
class Solution
{
public:
//判断ch是否是小写字母或数字字符
bool isLetterOrNumber(char ch)
{
if ((ch >= 'a' && ch <= 'z')
|| (ch >= '0' && ch <= '9'))
return true;
else
return false;
}
//验证回文串
bool isPalindrome(string s)
{
//将字符串中所有大写字母转为小写字母
for (auto& ch : s)
{
if (ch >= 'A' && ch <= 'Z')
ch += 32;
}
int begin = 0, end = s.size() - 1; //定义头指针和尾指针，用于验证回文串
while (begin < end) //当还有字母未判断时，循环继续
{
while (begin < end && !isLetterOrNumber(s[begin])) //头指针寻找待判断的字母或数字字符
begin++;
while (begin < end && !isLetterOrNumber(s[end])) //尾指针寻找待判断的字母或数字字符
end--;
if (s[begin] == s[end]) //待判断字符相等，继续下一次判断
{
begin++;
end--;
}
else
{
return false; //待判断字符不相等，该字符串不是回文串
}
}
return true; //字符串中所有字符判断完毕，该字符串是回文串
}
};
题目五：字符串相加
题目描述：
给定两个字符串形式的非负整数num1和num2，计算它们的和。
示例：
输入：“999”, “1”
输出：“1000”
思路：
和我们平时计算两个数的和一样，我们从两个字符串的最后一个数字开始进行相加，并设置一个变量记录是否需要进位，这样一来，两个字符串相加的时候，每一位置的数字 = 字符串1对应位置的数字 + 字符串2对应位置的数字 + 进位变量，若相加后该位置的数字大于9，则说明需要进位，这时我们设置进位变量为1（两个数字相加，最多只能进位1），并将该位置的数字减去10后的结果作为相加后该位置的数字即可，如此进行下去，直到两个字符串都遍历完毕即可。特别注意，两个字符串相加结束后还需要判断进位变量是否为1，若为1，则需要头插一个字符1到最终的字符串中。
代码：
class Solution
{
public:
string addStrings(string num1, string num2)
{
int end1 = num1.size() - 1, end2 = num2.size() - 1; //定义两个字符串的尾指针
string RetStr; //存储两个字符串相加后的结果
int next = 0; //标识进位
while (end1 >= 0 || end2 >= 0) //两个字符串中有一个未遍历完，则继续循环
{
int val1 = 0; //第一个字符串等待相加的数字
if (end1 >= 0)
{
val1 = num1[end1] - '0';
end1--;
}
int val2 = 0; //第二个字符串等待相加的数字
if (end2 >= 0)
{
val2 = num2[end2] - '0';
end2--;
}
int RetVal = val1 + val2 + next; //两个数字相加后的结果，注意需要加上进位
if (RetVal > 9) //判断是否需要进位
{
RetVal -= 10;
next = 1; //需要进位，设置next为1
}
else
{
next = 0; //不需进位，设置next为0
}
RetStr.insert(0, 1, RetVal + '0'); //将RetVal头插到RetStr
}
if (next == 1) //判断是否还需进位
RetStr.insert(0, 1, '1'); //将'1'头插到RetStr
return RetStr; //返回这两个字符串相加后的结果
}
};
优化：
代码中，我们每得到一个位置（个位、十位、百位…）的结果就需要头插一个数字到最终的字符串中。而我们知道，头插的代价是比较大的，因为我们每次进行头插就需要将所有的数据都向后挪动一位，留出最前面的位置以供插入，这种算法的时间复杂度达到O ( N ) O(N)O(N)。
解决这个问题也不难，我们可以将得到的每一位数字都尾插到字符串后面，只需最后进行一次字符串反转即可。
优化后的代码：
class Solution
{
public:
string addStrings(string num1, string num2)
{
int end1 = num1.size() - 1, end2 = num2.size() - 1; //定义两个字符串的尾指针
string RetStr; //存储两个字符串相加后的结果
int next = 0; //标识进位
while (end1 >= 0 || end2 >= 0) //两个字符串中有一个未遍历完，则继续循环
{
int val1 = 0; //第一个字符串等待相加的数字
if (end1 >= 0)
{
val1 = num1[end1] - '0';
end1--;
}
int val2 = 0; //第二个字符串等待相加的数字
if (end2 >= 0)
{
val2 = num2[end2] - '0';
end2--;
}
int RetVal = val1 + val2 + next; //两个数字相加后的结果，注意需要加上进位
if (RetVal > 9) //判断是否需要进位
{
RetVal -= 10;
next = 1; //需要进位，设置next为1
}
else
{
next = 0; //不需进位，设置next为0
}
RetStr += (RetVal + '0'); //将RetVal尾插到RetStr
}
if (next == 1) //判断是否还需进位
RetStr += '1'; //将'1'尾插插到RetStr
reverse(RetStr.begin(), RetStr.end()); //将字符串RetStr进行反转
return RetStr; //返回这两个字符串相加后的结果
}
};