目录
1. 仅仅反转字母
给你一个字符串 s ，根据下述规则反转字符串：
所有非英文字母保留在原有位置。
所有英文字母（小写或大写）位置反转。
返回反转后的 s 。
示例 1：
输入：s = "ab-cd"
输出："dc-ba"
示例 2：
输入：s = "a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"
示例 3：
输入：s = "Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"
提示：
1 <= s.length <= 100
s 仅由 ASCII 值在范围 [33, 122] 的字符组成
s 不含 '\&;' 或 '\\'
思路：
使用左右指针法。
假设left指向字符串首个字符，right指向字符串最后一个字符：
当left和right指向的字符都是字母时使用swap函数进行交换；
当left指向的不是字母时，right–；
right指向的不是字母时，left++；
如果left和right指向的都不是字母时，同时移动；
代码：
//左右指针法解决
class Solution {
public:
//判断是否是字母
bool IsWord(char c)
{
if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
{
return true;
}
return false;
}
string reverseOnlyLetters(string s) {
//判断是否为空
if(s.empty())
{
return s;
}
int left = 0;
int right = s.size() - 1;
//切记不能等于，否则会陷入死循环
while (left < right)
{
//两个都是字母。交换
if (IsWord(s[right]) && IsWord(s[left]))
{
swap(s[left], s[right]);
right--;
left++;
}
//右边为字母，左边向右进
else if (IsWord(s[right]))
{
left++;
}
//左边为字母，右边向左走
else if (IsWord(s[left]))
{
right--;
}
//两边都不为字母，同时移动
else
{
left++;
right--;
}
}
return s;
}
};
时间复杂度：O(N)
空间复杂度：O(1)
2.字符串中的第一个唯一字符
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
示例 1：
输入: s = "leetcode"
输出: 0
示例 2:
输入: s = "loveleetcode"
输出: 2
示例 3:
输入: s = "aabb"
输出: -1
提示:
1 <= s.length <= 10的5次方
s 只包含小写字母
思路：
因为s只包含小写字母也就是一共有26个字母，所以可以使用一个数组将字符串中出现字母的次数统计起来，然后在数组中按照字符串顺序找第一个只出现一次的字符。
代码：
class Solution {
public:
int firstUniqChar(string s) {
//使用int数组存放累加个数
int str[26] = {0};
for(int i = 0; i < s.size(); i++)
{
//将字符串中的字母出现次数统计到数组中
str[s[i] - 'a']++;
}
for(int i = 0; i < s.size(); i++)
{
//当数组中次数为1时，返回下标即可
if(str[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};
时间复杂度：O(N)
空间复杂度：O(1)
3.字符串最后一个单词的长度
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
输入描述：输入一行，代表要计算的字符串，非空，长度小于5000。
输出描述：输出一个整数，表示输入字符串最后一个单词的长度。
示例1：
输入：hello nowcoder
输出：8
说明：最后一个单词为nowcoder，长度为8
思路1：
通过rfind函数或者find_last_of函数从后往前找到第一个空格，此时这个空格往后知道结尾的长度就是最后一个单词的长度，可以通过size() - pos - 1计算得到最后一个单词的长度；如果函数返回值pos = string::npos，说明这个字符串就只有一个单词，直接返回size即可。注意不能使用cin>>输入字符串，因为字符串中含有空格，所以要使用getline函数获取字符串。
代码：
#include <iostream>
using namespace std;
int main() {
string s1;
getline(cin,s1);
//通过rfind函数从前往后查找空格，也可以使用find_last_of函数
size_t pos = s1.rfind(' ');
//size_t pos = s1.find_last_of(' ');
if(pos == string::npos)//此时说明只有一个单词
{
cout << s1.size() << endl;
return 0;
}
//找到第一个空格，然后通过计算得到最后一个单词长度
cout << s1.size() - pos - 1 << endl;
return 0;
}
// 64 位输出请用 printf("%lld")
时间复杂度：O(N)，最坏情况下rfind函数遍历完整个字符串，N为字符串长度。
空间复杂度：O(1)
4.验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
示例 2：
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。
示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。
提示：
1 <= s.length <= 2 * 10的5次方
s 仅由可打印的 ASCII 字符组成
思路一：
通过去除字符串中不是字母或者数字的字符之后，再将字符串中的大写字母全部转换成小写，将原字符串经过上述修改之后保存在新字符串s1中，最后通过reverse翻转函数将s1翻转之后比较s和s1两个字符串是否相等；或者使用左右指针的方法比较s字符串中左右两边的字符是否相同。我们将字符串中的大写字母转换成小写也可以使用库中提供的tolower函数。
代码1：使用reverse函数
class Solution {
public:
//判断是否是字母或者数字
bool IsWAN(char ch)
{
if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
{
return true;
}
return false;
}
//大写转换成小写
void StoB(char& ch)
{
if (ch >= 'A' && ch <= 'Z')
{
ch = ch + 'a' - 'A';
}
}
bool isPalindrome(string s) {
if (s.empty())
return true;
//先移除所有非字母数字字符
string s1;
for (auto e : s)
{
//也可以使用tolower函数
if (IsWAN(e))
{
StoB(e);//如果是大写抓换成小写
s1 += e;
}
}
s = s1;
//翻转后是否相等，如果相等就是回文串
reverse(s1.begin(), s1.end());
if (s1 == s)
return true;
else
return false;
}
};
时间复杂度：O(N)，reverse函数的时间复杂度为O(N)
空间复杂度：O(N)
代码2：使用左右指针方法
class Solution {
public:
bool IsWAN(char ch)
{
if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
{
return true;
}
return false;
}
void StoB(char& ch)
{
if (ch >= 'A' && ch <= 'Z')
{
ch = ch + 'a' - 'A';
}
}
bool isPalindrome(string s) {
if (s.empty())
return true;
//先移除所有非字母数字字符
string s1;
for (auto e : s)
{
if (IsWAN(e))
{
//也可以使用tolower函数
StoB(e);
s1 += e;
}
}
s = s1;
int left = 0;
int right = s.size() - 1;
while (left <= right)
{
if (s[left] != s[right])
{
return false;
}
left++;
right--;
}
return true;
};
时间复杂度：O(N)
空间复杂度：O(N)
思路二：
通过erase函数和左右指针搭配。此方法时间复杂度比较高，不推荐。
代码：
class Solution {
public:
bool IsWAN(char ch)
{
if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
{
return true;
}
return false;
}
//大写转换成小写
void StoB(char& ch)
{
if (ch >= 'A' && ch <= 'Z')
{
ch = ch + 'a' - 'A';
}
}
bool isPalindrome(string s) {
if (s.empty())
return true;
//先移除所有非字母数字字符
string s1;
int i = 0;
//注意迭代器失效问题
while(i < s.size())
{
if (!IsWAN(s[i]))
{
s.erase(s.begin() + i);
}
else
{
i++;
}
}
//再将字符串中的大写字母全部转换成小写
for(auto& e : s)
{
StoB(e);
}
//使用tolower函数
/*for(auto& e : s)
{
if(e >= 'A' && e <= 'Z')
{
e = tolower(e);
}
}*/
int left = 0;
int right = s.size() - 1;
while (left <= right)
{
if (s[left] != s[right])
{
return false;
}
left++;
right--;
}
return true;
}
};
时间复杂度：O(N*N)，最坏情况下，每次循环都要移动，字符串长度为N，所以一共需要移动N次，而erase函数的时间复杂度为O(N)。
空间复杂度：O(1)
5.字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = "11", num2 = "123"
输出："134"
示例 2：
输入：num1 = "456", num2 = "77"
输出："533"
示例 3：
输入：num1 = "0", num2 = "0"
输出："0"
提示：
1 <= num1.length, num2.length <= 10的4次方
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
思路：
将两个字符串从右边开始向前遍历，即从低位到高位开始计算，定义一个新的字符串s，将位数从低到高依次放在新字符串；
还需要定义标记位用来确定是否需要进位；
当right1不为0，即num1没有遍历完，单独遍历num1；
当right2不为0，即num2没有遍历完，单独遍历num2；
还要判断标记位是否还为1，如果是还需要再向前进位；
因为字符串中是从低位到高位记录的，所以最后还要翻转一下才能得到正确结果。
无论是同时处理还是单独处理字符串num1和num2，其基本逻辑都差不多。
代码：
class Solution {
public:
string addStrings(string num1, string num2) {
string s;
//从字符串的右边开始
int right1 = num1.size() - 1;
int right2 = num2.size() - 1;
int flag = 0;//标记位是否需要向前进一
int p = 0;//位数上的值
while(right1 >= 0 && right2 >= 0)
{
//计算出对应位置上的整数
int n1 = num1[right1] - '0';
int n2 = num2[right2] - '0';
int n = n1 + n2;
//当flag=1时需要向前进一
if(flag)
{
n += 1;
flag = 0;
}
//n大于9时，需要标记下，下次进一
if(n > 9)
{
flag = 1;
p = n % 10;
}
else
{
flag = 0;
p = n;
}
s += p + '0';
right1--;
right2--;
}
//right1不为0，即num1没有遍历完，基本逻辑和上面相同
while(right1 >= 0)
{
int n = num1[right1] - '0';
if(flag)
{
n += 1;
flag = 0;
}
if(n > 9)
{
flag = 1;
p = n % 10;
}
else
{
flag = 0;
p = n;
}
s += p + '0';
right1--;
}
//right2不为0，即num2没有遍历完，基本逻辑和上面相同
while(right2 >= 0)
{
int n = num2[right2] - '0';
if(flag)
{
n += 1;
flag = 0;
}
if(n > 9)
{
flag = 1;
p = n % 10;
}
else
{
flag = 0;
p = n;
}
s += p + '0';
right2--;
}
//当最后标记位仍为1时，向前进
if(flag)
{
s += flag + '0';
}
//从个位上开始加，所以最后需要翻转一下
reverse(s.begin(),s.end());
return s;
}
};
时间复杂度：O(N)
空间复杂度：O(1)
6.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
提示：
- 1 <= s.length <= 10的5次方
- s[i] 都是 ASCII 码表中的可打印字符
思路：
左右指针法进行交换，该函数是引用传参直接对字符数组修改即可。也可以直接使用reverse函数进行逆置。
代码：
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = s.size() - 1;
while(left < right)
{
swap(s[left],s[right]);
left++;
right--;
}
}
};
时间复杂度：O(N)
空间复杂度：O(1)
class Solution {
public:
void reverseString(vector<char>& s) {
//使用reverse函数
reverse(s.begin(),s.end());
}
};
时间复杂度：O(N)
空间复杂度：O(1)
