当前位置: 首页 > article >正文

LeetCode 125 验证回文串 简单

题目 - 点击直达

  • 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


http://www.kler.cn/a/109043.html

相关文章:

  • C 语言冒泡排序算法详解
  • FakeLocation 版本问题
  • @CrossOrigin打破同源策略
  • 数据结构-图的概念
  • Centos 7离线安装ntpd服务
  • TDengine 签约蘑菇物联,改造通用设备工业互联网平台
  • stream流—关于Collectors.toMap使用详解
  • Ubuntu服务器中java -jar 后台运行Spring Boot项目
  • 精通Nginx(01)-产品概览
  • 物联网数据采集网关连接设备与云平台的关键桥梁
  • calloc、malloc、realloc函数的区别及用法
  • 【力扣SQL】几个常见SQL题
  • 并发编程
  • uniapp开发小程序—根据生日日期计算年龄 周岁
  • 【自动驾驶】Free space与Ray casting
  • SpringBoot面试题8:运行 Spring Boot 有哪几种方式?Spring Boot 需要独立的容器运行吗?
  • ubuntu 18 更新git版本到 2.80.1
  • 深度学习之轻量级神经网络在TWS蓝牙音频处理器上的部署
  • 求二进制最低位1和最高位1的方法,以及反转二进制,复杂度O(1)
  • Python-easygui
  • 开发库介绍
  • 链游风暴再起?MBOX即将再度起飞
  • O(1) 时间插入、删除和获取随机元素
  • 你会处理 go 中的 nil 吗
  • ChatGPT 驱动软件开发:AI 在软件研发全流程中的革新与实践
  • 38基于matlab的期货预测,利用PSO优化SVM和未优化的SVM进行对比,得到实际输出和期望输出结果。