leetcode Valid Palindrome C++&python 题解
题目描写叙述
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
“A man, a plan, a canal: Panama” is a palindrome.
“race a car” is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
给定一个 字符串。推断是否是一个回文串,注:这道题中默认空串是回文串
思路分析
首先给出c++代码的思路。由于存在大写和小写的问题,所以须要统一把全部字母统一转为小写或者大写。所以这里使用到了STL中的transform()方法
以下简要记录一下transform()的使用方法。该算法用于容器元素的变换操作,有例如以下两个使用原型。一个将迭代器区间[first,last)中元素,运行一元函数对象op操作。交换后的结果放在[result,result+(last-first))区间中。
还有一个将迭代器区间[first1,last1)的元素*i。依次与[first2,first2+(last-first))的元素*j。运行二元函数操作binary_op(*i,*j)
函数原型
template < class InputIterator, class OutputIterator, class UnaryOperator >
OutputIterator transform ( InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperator op );
template < class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperator >
OutputIterator transform ( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperator binary_op );
參数解释:
irst1, last1
指出要进行元素变换的第一个迭代器区间 [first1,last1)。
first2
指出要进行元素变换的第二个迭代器区间的首个元素的迭代器位置。该区间的元素个数和第一个区间相等。
result
指出变换后的结果存放的迭代器区间的首个元素的迭代器位置
op
用一元函数对象op作为參数。运行其后返回一个结果值。
它能够是一个函数或对象内的类重载operator()。
binary_op
用二元函数对象binary_op作为參数,运行其后返回一个结果值。它能够是一个函数或对象内的类重载operator()。
给出一段演示样例代码
// transform algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::transform
#include <vector> // std::vector
#include <functional> // std::plus
int op_increase (int i) { return ++i; }
int main () {
std::vector<int> foo;
std::vector<int> bar;
// set some values:
for (int i=1; i<6; i++)
foo.push_back (i*10); // foo: 10 20 30 40 50
bar.resize(foo.size()); // allocate space
std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);
// bar: 11 21 31 41 51
// std::plus adds together its two arguments:
std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
// foo: 21 41 61 81 101
std::cout << "foo contains:";
for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
output:
foo contains: 21 41 61 81 101
以下描写叙述思路
统一转为大写和小写后,利用两个迭代器,一个指向开头。一个指向结尾,每次循环推断,假设不是数字或字母就跳过。假设两个迭代器指向的内容不一致则直接返回,假设相等则两个迭代器同一时候向中间走一步。直到两个指针相遇则推断是回文串
给出代码实现:
class Solution
{
public:
bool isPalindrome(string s)
{
transform(s.begin(),s.end(),s.begin(),::tolower);
string::iterator left=s.begin(),right=s.end();
while(left<right)
{
if (!::isalnum(*left))
left++;
else if(!::isalnum(*right))
right--;
else if((*left)!=(*right))
return false;
else
{left++,right--;}
}
return true;
}
};
注意这里域运算符::的使用方法,涉及到c++命名空间的问题。假设不加域运算符,会报找不到函数或者变量的错误。
python 解法
这道题用python的列表生成器和列表操作能够非常简洁的解决,思路是先用列表生成器去掉除数字和字母以外的字符得到一个新的字符串,然后直接推断该串和该串的逆序是否相等就可以。
代码实现例如以下
class Solution:
def isPalindrome(self, s):
newS=[i.lower() for i in s if i.isalnum()]
return newS==newS[::-1]
相关文章
- Python脚本扫描给定网段的MAC地址表(scapy或 python-nmap)
- 势头强劲的 Python PK 强大的 C++,究竟谁更胜一筹?
- 【华为OD机试真题 python】 组成最大时间【2022 Q4 | 100分】
- 24岁非计算机专业工科妹子裸辞转行Python程序员,自学Python三个月,零基础如何系统学习python,从入门到精通?
- 如何快速学习python,学好python?能通过Python赚到的第一笔钱,有哪些经验可以分享吗?
- 零基础小白如何学Python?这些方法你需要了解!
- MATLAB、C++、OpenCV、Python、Python-Numpy近似值(取整)求取函数总结【round()、ceil()、floor()、fix()】
- C#,入门教程(40)——主流编程语言C,C++,C#,Java, Go,Python的对比与建议
- 《精通Python网络爬虫:核心技术、框架与项目实战》——1.3 网络爬虫的组成
- Microsoft Visual C++ 14.0 is required Python
- Python实现微信自动回复(机器人版本)
- 大话游戏循环Game Loop——Python&C++
- 【python】+704个常用工具Python库
- Python find函数用法和概念
- 线性插值法的原理和python代码实现
- python脚本获取主机Mac地址
- 《Python数据可视化编程实战》——1.5 在Windows上安装matplotlib
- PyCodeGPT 我自己的预训练 AI 模型,以我的风格完成和生成 Python 代码
- Python NVIDIA Isaac机器人平台开发教程之 边缘 AI 的最佳工具是什么?Jetson Nano是什么
- 【python web开发知识点整理3】- 容器基础
- 【华为OD机试真题 java、python、c++】获取最大软件版本号(复盘思路)
- python之Oracle操作(cx_Oracle)
- Python学习书籍推荐(步步为营)
- 【Python】python扩展
- python 虚拟环境搭建自动化
- Python 基础 之 网络 socket 使用 tcp (SOCK_STREAM)实现简单的客户端、服务端(消息发送和接收)
- Python 基础 之 python 线程知识点整理,并实现一个简单多线程 udp 聊天应用
- 使用 Mypy 进行 Python 静态类型检查
- Python蓝桥杯训练:数组和字符串 Ⅲ
- [Python] 捕获异常