2889 回文大数字
大约 1 分钟
2889 回文大数字
【算法】 双指针
【C++】 string、双指针
【难度】 入门
一、题目简述
给定一个非负整数字符串(可能非常大),判断它是否是回文数(正着读和反着读一样)。单个数字也算回文数。
数据范围:字符串长度 可能很大,无法用整型变量存储,因此必须用字符串处理。
二、解题思路
本题无法将输入转为整数(数字太大),直接用字符串判断即可。
双指针法:设左指针 ,右指针 ,同时向中间移动。每次比较 s[l] 和 s[r],如果发现不相等,说明不是回文,直接输出 "No" 并结束程序。如果所有字符都匹配成功,输出 "Yes"。
为什么不用反转字符串?反转需要额外 空间,双指针就地比较更优,而且可以提前退出。
手动模拟 "12321"(n=5):
| 步骤 | l | r | s[l] | s[r] | 相等? |
|---|---|---|---|---|---|
| 初始 | 0 | 4 | '1' | '1' | 是 |
| 移动 | 1 | 3 | '2' | '2' | 是 |
| 移动 | 2 | 2 | l >= r,循环结束 |
全部匹配,是回文。
手动模拟 "12345"(n=5):
| 步骤 | l | r | s[l] | s[r] | 相等? |
|---|---|---|---|---|---|
| 初始 | 0 | 4 | '1' | '5' | 否,直接输出 "No" |
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int l = 0, r = s.length() - 1;
while (l < r) {
if (s[l] != s[r]) {
cout << "No" << endl;
return 0;
}
l++;
r--;
}
cout << "Yes" << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,最多遍历字符串一次(实际上最坏情况遍历一半,常数 省略)。
- 空间复杂度:,只用了两个指针变量,没有额外数组。
