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;;
}
};
总结：
为了代码的可读性，设置多个功能独立的函数。编程思路采用先总后合，先概括实现目标进而设置实现方法。
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--;
}
swap( s[begin],s[end]);
begin++;
end--;
}
return s;
}
};
总结：
这考查了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 )
{
CountArray[(ch -'a')]++;
}
for( size_t i = 0; i < s.size(); ++i )
{
if( CountArray[s[i] - 'a'] == 1)
{
return i;
}
}
return -1;
}
};
总结：
本题考察了string类中范围for的使用，通过计数排序的核心思想映射关系来解决。
|