湖南网站seo营销多少费用,移动网站建设推荐,清洁设备网站模版,交互式网站设计题目 - 点击直达 1. 125 验证回文串 简单1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 1. 125 验证回文串 简单
1. 题目详情
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反… 题目 - 点击直达 1. 125 验证回文串 简单1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 1. 125 验证回文串 简单
1. 题目详情
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。 给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。
1. 原题链接
LeetCode 125 验证回文串 简单
2. 题目要求 示例 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 * 105 s 仅由可打印的 ASCII 字符组成 3. 基础框架
● Cpp代码框架
class Solution {
public:bool isPalindrome(string s) {}
};2. 解题思路
1. 思路分析 ( 1 ) (1) (1) 快排思想借助两个变量 l l l和 r r r ( 2 ) (2) (2) l l l从字符串起始0下标位置向后找到第一个字母字符; ( 3 ) (3) (3) r r r从字符串最后一个字符size-1下标位置开始向前找到第一个字母字符; ( 4 ) (4) (4) 对找到的两个字母字符分别进行判断如果是大写字母则变为小写字母; ( 5 ) (5) (5) 比较这两个字母字符相等就 l l l和 r r r就继续分别查找下一个字母字符直到 l l l和 r r r相遇说明所有须比较的字母字符都符合要求结束并返回true只有存在一对不相等的字母字符说明不是回文串直接返回false
2. 时间复杂度 O ( N ) O(N) O(N) l l l向后查找 r r r向前查找直到二者相遇时才结束查找共查找了 n n n次;
3. 代码实现
class Solution {
public:bool isPalindrome(string s) {int l 0, r s.size() - 1;while(l r){while(l s.size() !isalpha(s[l]) !isdigit(s[l])){l;}while(r 0 !isalpha(s[r]) !isdigit(s[r])){r--;}if(l r){if(isupper(s[l])) s[l] 32;if(isupper(s[r])) s[r] 32;if(s[l] ! s[r]) return false;l;r--;}}return true;}
};T h e The The e n d end end
