今天依旧是字符串！2道简单＋3道中等
1、仅仅反转字母（难度：简单）
该题对应力扣网址
错误做法
一开始是“原始”思路，交了之后果然不对，错误的思路我也就不解释了。
class Solution {
public:
string reverseOnlyLetters(string s) {
int n=s.length();
int i,temp;
for(i=0;i<n/2;i++){
if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z')){
temp=s[i];
s[i]=s[n-i-1];
s[n-i-1]=temp;
}
}
return s;
}
};
AC代码
想了一下还是用前几天刚学过的双指针就行（真香了）
class Solution {
public:
bool alphabet(char ch){
if((ch>='a' && ch<='z') || (ch>='A' && ch<='Z')){
return true;
}
return false;
}
string reverseOnlyLetters(string s) {
int n=s.length();
int left=0,right=n-1,temp;
while(left<=right){
if(alphabet(s[left]) && alphabet(s[right])){
temp=s[left];
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
else if(!alphabet(s[left]) && alphabet(s[right])){
while(!alphabet(s[left])){
left++;
}
temp=s[left];
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
else if(alphabet(s[left]) && !alphabet(s[right])){
while(!alphabet(s[right])){
right--;
}
temp=s[left];
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
else{
left++;
right--;
}
}
return s;
}
};
2、回文子串（难度：中等）
该题对应力扣网址
AC代码
一开始没啥思路，只有笨方法，（觉得写了肯定也超时） 大概看了题解推荐的方法，其中这个双指针中心点的方法还是挺简单的，dp那个方法没看懂，等做dp类型的时候再说。
这道题就是和普通的判断是否是回文串反过来了，判断回文串，一般都是从两边往中间，双指针。
这道题是找字符串里有多少回文串，是从中心点往两边，双指针。
思路：
中心点分两类：一个中心点、两个中心点
然后从中间往两边看两边对应位置的字符是否一样
class Solution {
public:
int countSubstrings(string s) {
int n = s.length();
int i,j,k;
int left,right;
int num = 0;
//遍历字符串里每个字符
for(i=0;i<n;i++){
//确定一个或两个中心点
for(j=0;j<=1;j++){
left=i;
right=i+j;
if(j==1){
if(s[left]!=s[right]){
continue;
}
}
while(left>=0 && right<=n && s[left--]==s[right++]){
num++;
}
}
}
return num;
}
};
3、最长回文子串（难度：中等）
该题对应力扣网址
AC代码
没啥，和上一题的思路基本一致
class Solution {
public:
static bool cmp(const pair<string,int> &a,const pair<string,int> &b){
return a.second>b.second;
}
string longestPalindrome(string s) {
int i,j,k,l,r,count;
int n = s.length();
vector <pair<string,int>> str;
for(i=0;i<n;i++){
for(j=0;j<=1;j++){
count=0;
l=i;
r=i+j;
if(j==1){
if(s[l]!=s[r]){
continue;
}
}
while(l>=0 && r<=n-1 &&l<=r && s[l--]==s[r++]){
count++;
}
if(j==1){
str.push_back({s.substr(i-count+1,count*2), count*2});
}
if(j==0){
str.push_back({s.substr(i-count+1,(count-1)*2+1), (count-1)*2+1});
}
}
}
sort(str.begin(),str.end(),cmp);
return str[0].first;
}
};
4、验证回文串（难度：简单）
该题对应力扣网址
AC代码
没啥说的
class Solution {
public:
//判断是不是大写字母
bool daxie(char ch){
if(ch>='A' && ch<='Z'){
return true;
}
return false;
}
//判断是不是小写字母
bool xiaoxie(char ch){
if(ch>='a' && ch<='z'){
return true;
}
return false;
}
//判断是不是数字
bool shuzi(char ch){
if(ch>='0' && ch<='9'){
return true;
}
return false;
}
//判断是不是回文串
bool huiwen(string str){
int n = str.length();
int l=0,r=n-1;
while(l<=r){
if(str[l]==str[r]){
l++;
r--;
}
else{
return false;
}
}
return true;
}
bool isPalindrome(string s) {
int i,j=0,k;
int n = s.length();
string str="";
for(i=0;i<n;i++){
if(daxie(s[i])){
str+=s[i]+32;
}
else if(xiaoxie(s[i])){
str+=s[i];
}
else if(shuzi(s[i])){
str+=s[i];
}
}
return huiwen(str);
}
};
5、反转字符串中的单词（难度：中等）
该题对应力扣网址
AC代码
没看题解，思路依旧是双指针，r指针从后往前，遍历完一个单词之后，l指针从前往后，遍历这个单词，并加入到新的字符串str中。
主要有四种情况，按照代码的顺序依次是：
1、单词左面第一个空格
2、字符串第一个字符且该字符不是空格
3、存在连续的多个空格
4、单词中的字符
注意：写代码的时候，不注意的话，数组容易溢出，建议在判断条件里把边界放在前面，例如while(r>=0 && s[r]==' ')
class Solution {
public:
string reverseWords(string s) {
int i,j,k,count=0;
int l,r;
string str="";
r=s.length()-1;
while(r>=0){
if(s[r]==' ' && s[r+1]!=' ' && r+1<=s.length()-1){
l=r;
cout<<r<<" "<<count<<endl;
while(count>0){
l++;
str+=s[l];
count--;
}
count=0;
str+=' ';
}
else if(r==0 && s[r]!=' '){
l=r;
while(count>=0){
str+=s[l];
l++;
count--;
}
count=0;
}
//存在多个空格
else if(s[r]==' '){
while( r>=0 && s[r]==' '){
r--;
}
continue;
}
else{
count++;
}
r--;
}
int n=str.length()-1;
//把多余的最后的空格删掉
if(str[n]==' '){
str.pop_back();
}
return str;
}
};
中间出去玩儿了两天，今天才补上，慢慢来吧
