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

devtools/2024/11/6 14:55:39/

一、题目

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

示例 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.ppmy.cn/devtools/131788.html

相关文章

爬虫下载网页文夹

爬虫下载网页pdf文件 import os import requests from bs4 import BeautifulSoup from urllib.parse import urljoin from urllib.parse import urljoin, unquote from tqdm import tqdm # 设置网页的URL base_url "http://119/download/dzz/pdf/"# 创建保存文件的…

履带式排爆演习训练机器人技术详解

履带式排爆演习训练机器人是现代反恐、救援及危险环境处理领域中的重要工具。它们结合了先进的机械设计、智能感知、精确控制及高效算法&#xff0c;能够在复杂、危险的环境中执行排爆、侦察、取样等多种高风险任务&#xff0c;极大地保障了人员安全。 技术特点 1. 卓越的地面…

5G学习笔记三之物理层、数据链路层、RRC层协议

5G学习笔记三之物理层、数据链路层、RRC层协议 物理层位于无线接口协议栈的最底层&#xff0c;作用&#xff1a;提供了物理介质中比特流传输所需要的所有功能。 1.3.1 传输信道的类型 物理层为MAC层和更高层提供信息传输的服务&#xff0c;其中&#xff0c;物理层提供的服务…

Web Components 是什么

Web Components 是一套不同的 web 标准&#xff0c;它们允许开发者创建可重用的自定义元素&#xff08;通过封装 JavaScript 类来定义&#xff09;&#xff0c;这些元素封装了 HTML、CSS 和 JavaScript。 Web Components 主要包括以下几个部分&#xff1a; Custom Elements&am…

使用kettle同步数据流程

使用kettle同步数据流程 一&#xff0e;Kettle软件安装&#xff08;解压即可使用&#xff09; 1.windows安装解压 pdi-ce-8.2.0.0-342.zip&#xff0c;点Spoon.bat启动kettle 2.Linux安装 把data-integration目录所有文件上传到服务器 二&#xff0e;安装数据库驱动把需要的…

TCP建立连接之后怎么保持长连接(检测连接断没断)

在TCP连接建立后&#xff0c;保持长连接的主要方式是通过定期的心跳检测&#xff08;Keep-Alive&#xff09;和超时机制。以下是一些具体的方法和机制 1. TCP Keep-Alive TCP协议本身提供了一种Keep-Alive机制&#xff0c;可以通过以下步骤实现&#xff1a; 启用Keep-Alive&…

数据结构————链表

一、引言 1. 中间/头部的插入删除&#xff0c;时间复杂度为O(N) 2. 增容需要申请新空间&#xff0c;拷贝数据&#xff0c;释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长&#xff0c;势必会有一定的空间浪费。例如当前容量为100&#xff0c;满了以后增容到200&#x…

【JavaScript】axios 二次封装拦截器(接口、实例、全局)

学习 coderwhy 老师结合 ts 二次封装 axios 目录结构 config config\index.ts // export const BASE_URL "http://codercba.com:9002"; export const TIME_OUT 10000;// 1. 根据环境变量区分接口地址 // let BASE_URL: string; // if (process.env.NODE_ENV &qu…