Leetcode:125.验证回文串，917仅仅反转字母，387字符串的第一个唯一字符

125.验证回文串

题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。 给你一个字符串 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：我们先创建判断字符是否为字符（字母和数字都属于字符）的函数。如果为字符的话，就表示正确，否则就为错误。
2：创建通过循环遍历来将字符串中的大写字母转换为小写字母的函数。
3：其次，找出字符串中的字符。类似于快排的思想，用俩个下标分别循环遍历字符串的左边和右边，如果不是字符则跳出，如果是字符，则停下来。
4：最后判断两边字符是否相同。程序执行到这一步，说明数组下标所指的都为字符，通过判断比较这两个字符串是否相等。如果相等，则要继续循环上诉步骤。如果不相等，就说明，该字符串不是回文字符串。
5：当string类中遍历完毕，说明string类中的字符都想等，符合条件。

代码实现

class Solution {
public:
    bool isLetterOrNumber(char ch)
    {
        return ( ch >= '0' && ch <='9') || ( ch >= 'a' && ch <= 'z') || ( ch >= 'A' && ch <= 'Z');
    }
    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])
         {
               return false;
         }
               end--;
               begin++;
    }
    return true;;
    }
};
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

总结：
为了代码的可读性，设置多个功能独立的函数。编程思路采用先总后合，先概括实现目标进而设置实现方法。

917.仅仅反转字母

题目描述

给你一个字符串 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：首先我们先创建一个函数判断字符串中是否为字母，是的话就表示正确，否则就为错误。
2：其次，找到字符串中的字符。用类似快排的方法，设置两个初始值为0，size-1的两个下标，让两个下标分别循环判断是否为字符，如果不是字符就停下来，否则就跳过。（在循环的时候，我们要注意是否越界）
3：最后，进行字符交换。当两个下标停下来的时候，就代表这两个下标指的字符串位置就是字符，此时我们便可以采用swap函数对这两个字符串的位置进行交换，完成仅仅反转字母的最终目标。

代码实现

class Solution {
public:
bool Isletter( char ch)
    {
        if(( ch >= 'a' && ch <='z') || ( ch >= 'A' && ch <= 'Z'))
             return true;
        else
             return false;
    }

    string reverseOnlyLetters(string s) {
    size_t begin = 0;        
    size_t end = s.size() -1;
    while(  begin < end )
    {
        //不是字母的情况
        while( begin < end&& !Isletter(s[begin]))
       {
            begin++;
       }
        while( begin < end && !Isletter(s[end]))
       {
           end--;
       }
        //走到这里，说明此时s._str[begin] 和 s._str[end]都是字母
        swap( s[begin],s[end]);
        begin++;
        end--;
    }
    return s;
    }
};
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

总结：
这考查了string类常用特性，以及一个大循环包含着两个指针的小循环分别完成对应目标的过程。

387.字符串的第一个唯一字符

题目描述

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

示例

示例 1：

输入: s = “leetcode” 输出: 0

示例 2:

输入: s = “loveleetcode” 输出: 2

示例3：

输入: s = “aabb” 输出: -1

思路分析

1：这道题让我们想到计数排序里面的映射思想。首先，我们可以创建一个计数数组CountArray，通过循环遍历的方式（范围for)分别储存对应字母映射在对应CountArray的数组内存空间中。
2：其次，我们可以遍历字符串通过映射关系访问到数组CountArray，如果对应字符映射到对应数组CountArray的内容为1的话，说明该字符重复次数为1，符合目标，否则，继续按照上诉方式循环遍历，直到找到字符串的第一个唯一字符。当遍历完字符串还找不到的话，就说明不存在。

代码实现：

class Solution {
public:
    int firstUniqChar(string s) {
        int CountArray[26] = {0};
        //统计每个字符出现的次数
        for( auto &ch : s ) //使用范围for，对数组里面的值进行访问修改。
        {
            CountArray[(ch -'a')]++; 
        }
        for( size_t i = 0; i < s.size(); ++i )
        {
             if( CountArray[s[i] - 'a'] == 1)
             {
                 return i;
             } 
        }   
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结：
本题考察了string类中范围for的使用，通过计数排序的核心思想映射关系来解决。