【5.8】指针算法-双指针验证回文串

一、题目

        给定一个字符串,验证它是否是回文串, 只考虑字母和数字字符 ,可以忽略字母的大小写。
说明: 本题中,我们将空字符串定义为有效的回文串。

示例 1:
输入: "A man , a plan , a canal : Panama "
输出: true


示例 2:
输入: "race a car"
输出: false

二、解题思路

        “回文串” 指的是正读和反读都相同的字符串,即其左右两边呈对称状态。要验证一个字符串是否为回文串,一种最简单的方式就是运用两个指针,一个从字符串前端开始,一个从后端开始,两个指针同时向中间移动。如果它们指向的字符不一样,那么这个字符串肯定不是回文字符串,直接返回 false 即可;如果这两个指针相遇了,那就直接返回 true。不过这道题只需要判断字母和数字,因为字符串中可能含有其他字符,对于这些其他字符我们只需跳过即可。下面画个图来看一下。

三、代码实现

#include <iostream>
#include <string>
#include <cctype>using namespace std;bool isPalindrome(string s) {int left = 0, right = s.length() - 1;while (left < right) {// left是左指针,如果不是字母和数字要过滤掉while (left < right && !isalnum(s[left]))left++;// right也一样,如果不是字母和数字也要过滤掉while (left < right && !isalnum(s[right]))right--;// 然后判断这两个字符是否相同,如果不相同直接返回false,这里是先把字符全部转化为小写if (tolower(s[left]) != tolower(s[right]))return false;// 如果left和right指向的字符忽略大小写相等的话,这两个指针要分别往中间移一步left++;right--;}// 如果都比较完了,说明是回文串,返回truereturn true;
}int main() {string s = "A man, a plan, a canal: Panama";bool result = isPalindrome(s);// 打印结果cout << "Input: \"" << s << "\"" << endl;cout << "Output: " << (result ? "true" : "false") << endl;return 0;
}
        我们还可以在比较之前字母全部转化为小写,最外层改为for 循环的方式

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>bool isPalindrome(std::string s) {// 先转为小写std::transform(s.begin(), s.end(), s.begin(), ::tolower);// 双指针法int i = 0, j = s.length() - 1;while (i < j) {// 跳过非字母和数字的字符while (i < j && !std::isalnum(s[i]))i++;while (i < j && !std::isalnum(s[j]))j--;// 比较字符if (s[i] != s[j])return false;// 移动指针i++;j--;}return true;
}int main() {std::string s = "A man, a plan, a canal: Panama";std::cout << std::boolalpha << isPalindrome(s) << std::endl;  // 输出: truereturn 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/6855.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

多功能 Web 应用渗透测试系统

系统简介 本项目命名为SecurityEye&#xff0c;是一款基于 Python-Django 的多功能 Web 应用渗透测试系统&#xff0c;包含漏洞检测、目录识别、端口扫描、指纹识别、域名探测、旁站探测、信息泄露检测、网站权重探测等功能。 项目功能 本系统通过旁站探测、域名探测、、域名…

libstdc++/so.6: version ‘GLIBCXX_3.4.29‘ not found (required by

matlab使用过程中提示库文件版图过低&#xff0c;如图 1. 网上或者其他eda的工具目录里面找一个libstdc.so.6.29文件&#xff0c;里面包含了glibcxx3.4.29 2. 复制文件到/usr/lib64目录下面 3. libstdc.so.6连接到新的库文件 unlink libstdc.so.6 ln -s libstdc.so.6.0.29 l…

有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 基础使用先平方&#xff0c;后排序的思想 class Solution {public int[] sortedSquares(int[] nums) {for(int i0;i<nums.length;i){nums…

flutter 专题七 Flutter面试之渲染流程

一、 简介 Flutter面试中必问的一个面试题就是渲染相关的话题。作为Google在2018年发布的一款跨平台UI框架&#xff0c;使用Dart作为其开发语言&#xff0c;底层使用Skia图形库进行视图渲染&#xff0c;渲染速度和用户体验堪比原生。 二、Flutter渲染流程 总的来说&#xff…

深入理解 TCP 的握手与挥手机制:为何握手 3 次,挥手 4 次?

在网络通信的世界里&#xff0c;TCP&#xff08;Transmission Control Protocol&#xff0c;传输控制协议&#xff09;是一种非常重要的协议&#xff0c;它确保了数据在网络中的可靠传输。而 TCP 的连接建立&#xff08;握手&#xff09;和连接断开&#xff08;挥手&#xff09…

Python-数据爬取(爬虫)

在数据驱动的时代&#xff0c;Python以其强大的数据处理能力和丰富的库资源&#xff0c;成为数据爬取的首选语言。通过Python&#xff0c;你可以轻松地从网页中抓取所需的数据&#xff0c;无论是价格信息、新闻内容还是用户评论&#xff0c;都能一一收入囊中。使用requests库发…

基于51单片机水位监测控制报警仿真设计

基于51单片机水位监测控制报警仿真设计 1. 主要功能&#xff1a;2. 讲解视频&#xff1a;3. 仿真4. 程序代码5. 设计报告6. 设计资料内容清单&&下载链接资料下载链接&#xff1a; 基于51单片机水位监测控制报警仿真设计( proteus仿真程序设计报告讲解视频&#xff09; …

JavaFX在Linux aarch64上运行

1.适配Jdk Linux开发项目安装在麒麟系统&#xff0c;无法安装&#xff0c;经查询因cpu架构不同导致无法运行 https://www.oracle.com/sg/java/technologies/downloads/#java21 该链接可下载jdk21,Linux aarch64版本。 2.适配Javafx模块 替换jdk之后&#xff0c;JavaFX仍无…

3D区块多重渐变围栏

这里主要用到的就是threejs的shader&#xff0c;至于其他知识点&#xff0c;可以参考json生成3d区域 下面的主要代码&#xff1a; import * as THREE from three; import { OrbitControls } from three/addons/controls/OrbitControls.js import { EffectComposer } from th…

【NLP】使用 SpaCy、ollama 创建用于命名实体识别的合成数据集

命名实体识别 (NER) 是自然语言处理 (NLP) 中的一项重要任务&#xff0c;用于自动识别和分类文本中的实体&#xff0c;例如人物、位置、组织等。尽管它很重要&#xff0c;但手动注释大型数据集以进行 NER 既耗时又费钱。受本文 ( https://huggingface.co/blog/synthetic-data-s…

Git代码托管(三)可视化工具操作(1)

常见的可视化操作工具有 一、官方网页 如码云、gitlab&#xff0c;自带了常见的git操作。 以码云为例&#xff1a; 1、创建分支&#xff1a; 进入分支目录&#xff0c;点击 新建分支 按钮&#xff0c; 在弹出框中输入新分支名称&#xff0c;点击确定即可一键创建分支&…

STL学习-无序容器-unordered set和unorderde multiset

1.定义及初始化 #include <unordered set> #include <iostream> using namespace std; //输出s中的所有元素 template<typename T> void Show(const T& s) { for(auto&x:s) cout << x<<" ";cout << endl; } int main()…

鸿蒙(Harmony)实现滑块验证码

在Android和ios两端已经使用的滑块验证码框架还未适配鸿蒙版&#xff0c;于是需要自己去实现类似如下的滑块验证码&#xff1a; 那么实现这样的验证码主要涉及到几个内容&#xff1a; 1、自定义弹窗 2、base64图片转换 3、滑动组件与滑块的联动&#xff0c;以及横移距离转换…

《华为工作法》读书摘记

无论做什么事情&#xff0c;首先要明确的就是做事的目标。目标是引导行动的关键&#xff0c;也是证明行动所具备的价值的前提&#xff0c;所以目标管理成了企业与个人管理的重要组成部分。 很多时候&#xff0c;勤奋、努力并不意味着就一定能把工作做好&#xff0c;也并不意味…

三维测量与建模笔记 - 3.3 张正友标定法

上图中&#xff0c;提到了世界坐标系在张正友标定法中的设计&#xff0c;可以理解为将世界坐标系的原点放到了棋盘格左上角点的位置&#xff0c;并且棋盘格平面上所有点的Z为0&#xff0c;将Z规定为0的话&#xff0c;可以简化掉一个维度&#xff08;列向量r3&#xff09;。去掉…

【课程总结】day34:多模态大模型之ViT模型、CLIP模型论文阅读理解

前言 在【课程总结】day31&#xff1a;多模态大模型初步了解一文中&#xff0c;我们对多模态大模型的基本原理有了初步了解&#xff0c;本章内容将通过论文阅读理解&#xff0c;更进一步理解多模态大模型中所涉及的 Vit 架构、Transformer在视觉应用的理念以及 Clip图像与文本…

国药准字生发产品有哪些?这几款不错

头秃不知道怎么选的朋友们看这&#xff0c;基本上市面上火的育发精华我都用了个遍了&#xff0c;陆陆续续也花了有大几w了&#xff0c;都是真金白银总结出来的&#xff0c;所以必须要给掉发人分享一些真正好用的育发产品&#xff0c;大家可以根据自己实际情况来选择。 1. 露卡菲…

golang分布式缓存项目 Day 1

注&#xff1a;该项目原作者&#xff1a;https://geektutu.com/post/geecache-day1.html。本文旨在记录本人做该项目时的一些疑惑解答以及部分的测试样例以便于本人复习。 LRU缓存淘汰策略 三种缓存淘汰策略 FIFO&#xff08;First In, First Out&#xff09;先进先出 原理&…

Android View事件分发

目录 1.什么是View事件分发&#xff1f; 2.事件的类型 3.事件的发生 4.事件分发的方法 4.1 dispatchTouchEvent() 4.2 onTouchEvent() 4.3 onInterceptTouchEvent() 5.滑动冲突 5.1 外部拦截法 5.2内部拦截法 6.onTouch的执行高于onClick 7. onTouch()和onTouchEve…

Elasticsearch常用接口_添加数据

插入es数据&#xff1a;_index/_type/ POST { "tabTitle": "森图表_test", "chtTabTitle": "森图表_test", "status": 0 } 注意&#xff1a;Elasticsearch 6.0.0及更高版本中&#xff0c;索引只能包含一个映射类型