今天是周日，看着身边的人都去踏青了，而我泡在实验室刷了将近 10 题回文数（串）相关的题目，这脑袋，也不知道被啥踢了。。但愿苦心人，天不负吧。。。
回文串的相关题目，变化还是不少的。本博客一点点呈现。题目包括：
（1）判断回文串（数）
（2）统计回文个数（将两个字符串混合）
（3）回文数猜想
（4）回文链表（三种方法）
（5）字符串的最长回文子串
1、什么是回文串（数）
回文串是正读和反读都一样的字符串。比如 level ，noon 等等。
2、判断一个字符串是回文串
判断方法就是字两端的字符是否相等。很简单，代码如下：
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str;
int flag = 1;
while (cin >> str)
{
for (int i = 0; i < str.size()/2; i++)
{
if (str[i] != str[str.size()-1 - i]) // 首尾相等
flag = 0;
}
}
if (flag == 0)
cout << "不是回文" << endl;
else
cout << "是回文" << endl;
return 0;
}
更方便的判断方法，利用 STL 的反转函数 reverse();
// 判断字符串是不是回文
int main()
{
string str;
cin >> str;
string temp_str = str;
reverse(temp_str.begin(),temp_str.end()); // 将拷贝后的字符串反转
if (str == temp_str) // 如果一个字符串和其反转后的字符串相等，说明是回文
{
cout << "是回文" << endl;
}
else
cout << "不是回文" << endl;
return 0;
}
【华中科技大学考研复试上机题】
给出一个长度不超过1000的字符串，判断它是不是回文(顺读，逆读均相同)的。
输入描述:
输入包括一行字符串，其长度不超过1000。
输出描述:
可能有多组测试数据，对于每组数据，如果是回文字符串则输出"Yes!”，否则输出"No!"。
示例1
输入
hellolleh
helloworld
输出
Yes!
No!
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void is_huiwen(string s)
{
int flag = 1;
for (int i = 0; i < s.size() / 2; i++)
{
if (s[i] != s[s.size() - 1 - i]) // 首尾相等
flag = 0;
}
if (flag == 0)
cout << "No!" << endl;
else
cout << "Yes!" << endl;
}
int main()
{
vector<string> v_str;
string str;
while (getline(cin, str))
{
v_str.push_back(str);
}
for (int i = 0; i < v_str.size(); i++)
// cout << v_str[i] << endl;
{
// 判断每一行字符串是不是回文
is_huiwen(v_str[i]);
}
}
3、统计回文（将两个字符串混合，能组成多少回文）【牛客网 2017校招真题】
题目描述:
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
例如：
A = “aba”，B = “b”。这里有4种把B插入A的办法：
* 在A的第一个字母之前: "baba" 不是回文
* 在第一个字母‘a’之后: "abba" 是回文
* 在字母‘b’之后: "abba" 是回文
* 在第二个字母'a'之后 "abab" 不是回文
所以满足条件的答案为2
输入描述:
每组输入数据共两行。
第一行为字符串A
第二行为字符串B
字符串长度均小于100且只包含小写字母
输出描述:
输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数
示例1
输入
aba
b
输出
2
代码：
#include<iostream>
#include<string>
using namespace std;
// 判断字符串是否为回文
bool is_huiwen(string s)
{
int flag = 1;
for (int i = 0; i < s.size() / 2; i++)
{
if (s[i] != s[s.size() - 1 - i]) // 首尾相等
flag = 0;
}
if (flag == 0)
//cout << "不是回文" << endl;
return false;
else
//cout << "是回文" << endl;
return true;
}
int main()
{
string A,B;
getline(cin,A);
getline(cin,B);
int sum = 0;
for(int i = 0;i <= A.size();i++) // 插入。可以插入 A.size() + 1 个位置
{
string temp = A; // 引入一个中间变量，不能改变 字符串 A
temp.insert(i,B);
if(is_huiwen(temp))
{
sum ++;
}
}
cout << sum;
return 0;
}
4、回文数猜想【ACM 题库训练】
题目描述：
题目描述
一个正整数，如果从左向右读（称之为正序数）和从右向左读（称之为倒序数）是一样的，这样的数就叫回文数。任取一个正整数，如果不是回文数，将该数与他的倒序数相加，若其和不是回文数，则重复上述步骤，一直到获得回文数为止。例如：68变成154（68+86），再变成605（154+451），最后变成1111（605+506），而1111是回文数。于是有数学家提出一个猜想：不论开始是什么正整数，在经过有限次正序数和倒序数相加的步骤后，都会得到一个回文数。至今为止还不知道这个猜想是对还是错。现在请你编程序验证之。
输入描述:
每行一个正整数。
特别说明：输入的数据保证中间结果小于2^31。
输出描述:
对应每个输入，输出两行，一行是变换的次数，一行是变换的过程。
示例1
输入
27228
37649
输出
3
27228--->109500--->115401--->219912
2
37649--->132322--->355553
代码：
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int reverse_num(int num)
{
int temp = 0;
while (num != 0)
{
temp = temp * 10 + num % 10;
num /= 10;
}
return temp;
}
bool is_huiwen(string s) // 判断字符串是不是回文
{
int flag = 1; // 假设是回文
for (int i = 0; i < s.size() / 2; i++)
{
if (s[i] != s[s.size() - 1 - i]) // 首尾相等
flag = 0;
}
if (flag == 0)
//cout << "不是回文" << endl;
return false;
else
//cout << "是回文" << endl;
return true;
}
int main()
{
int n;
//vector<int> v;
// while (cin >> n)
// {
// v.push_back();
// }
while (cin >> n)
{
string s;
int jishu = 0;
s = to_string(n);
//cout << s;
string s1 = s;
while (!is_huiwen(s1)) // 如果不是回文
{
jishu++;
int temp_s = stoi(s1); // 先将字符串 s 转换为 整型数字
int temp_i = reverse_num(temp_s); // 将整型数字逆序
s1 = to_string(temp_s + temp_i);
}
std::cout << jishu << endl; // 输出变换次数
while (!is_huiwen(s)) // 如果不是回文
{
std::cout << s;
std::cout << "--->";
int temp_s = stoi(s); // 先将字符串 s 转换为 整型数字
int temp_i = reverse_num(temp_s); // 将整型数字逆序
s = to_string(temp_s + temp_i);
}
std::cout << s << endl;
}
return 0;
}
分析：刚写的代码还是有点小问题的，但是牛客网上的编辑器给通过了。问题在于 while(cin >>n)，如果输入一行，以空格隔开，结果没问题。但是一行输入一个数字，就不行了。而且，统计转换的次数，我又进行了一次循环，这无疑增大了复杂度。我是这样改的。
#include<iostream>
#include<vector>
using namespace std;
int reverse_num(int num)
{
int temp = 0;
while (num != 0)
{
temp = temp * 10 + num % 10;
num /= 10;
}
return temp;
}
int main()
{
int n;
while (cin >> n)
{
vector<int> v;
while (n != reverse_num(n)) // 判断是不是回文数字
{
v.push_back(n);
n += reverse_num(n); // 如果不是回文数字，就将其本身和其反转后的数字相加
}
v.push_back(n); // 循环结束后，n 已经是回文了
cout << v.size() - 1 << endl; // 所以， n 之前的数字的个数就是进行转换的次数
int i;
for (i = 0; i<v.size() - 1; ++i)
cout << v[i] << "--->";
cout << v[i] << endl;
}
return 0;
}
5、回文链表
请编写一个函数，检查链表是否为回文。
给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。
测试样例：
{1,2,3,2,1}
返回：true
{1,2,3,2,3}
返回：false
代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
// 反转链表
ListNode* ReverseList(ListNode* pHead) {
if(pHead == NULL)
return pHead;
ListNode* pNode = pHead; //当前处理的结点
ListNode* preNode = NULL;
ListNode* reverseNode = NULL;
while(pNode != NULL)
{
ListNode* nextNode= pNode->next;
if(nextNode == NULL)
reverseNode = pNode;
pNode->next = preNode; // 调整链表的指向
preNode = pNode;
pNode = nextNode;
}
return reverseNode;
}
class Palindrome {
public:
bool isPalindrome(ListNode* pHead) {
// write code here
// 可以考虑现将链表进行反转
ListNode* qNode = ReverseList(pHead);
bool flag = true; // 假设是回文
while(pHead != NULL && qNode != NULL)
{
if(pHead->val != qNode->val)
flag = false;
pHead = pHead->next;
qNode = qNode->next;
}
return flag;
}
};
上面代码的思路是先反转链表，比较容易想。但是需要额外的空间。下面介绍不使用额外的空间，只对链表的后半部分进行反转。然后一个指针指向链表头，一个指针指向链表中间，比较值是否相等，不相等就返回false。代码如下：
class Palindrome {
public:
bool isPalindrome(ListNode* pHead) {
// write code here
int count=0;
ListNode* p=pHead;
while(p!=NULL){
p=p->next;
count++;
}
count=count%2==0?count/2:(count/2+1);
p=pHead;
for(int i=0;i<count;++i){
p=p->next;
}
ListNode* pre=NULL;
while(p!=NULL){
ListNode* temp=p->next;
p->next=pre;
pre=p;
p=temp;
}
ListNode* m=pHead;
while(pre!=NULL&&m!=NULL){
if(pre->val!=m->val)
return false;
pre=pre->next;
m=m->next;
}
return true;
}
};
还有两种方法供参考：
（5-2）、快慢指针法（该类方法是解决单链表问题常用的方法）
/*
* 1.利用快慢指针，可以找到链表中间位置
* 2.在快慢指针扫描的同时，将慢指针所指向的节点从原链表摘下，头插法插入一个新链表
* 3.最后只须继续扫描新链表和原链表，比较是否相同（稍微注意一下原链表长度为奇数或偶数的情况）
**/
bool isPalindrome(ListNode* pHead) {
// write code here
if (pHead==NULL)
return true;
ListNode* newHead = NULL;
ListNode* pSlow = pHead;
ListNode* pQuick = pHead;
// 当原链表长度为奇数时，快指针 pQuick 刚好扫到尾节点停止
// 当原链表长度为偶数时，快指针 pQuick 扫到尾节点前一节点停止
while (pQuick->next!=NULL && pQuick->next->next!=NULL) {
pQuick = pQuick->next->next; // 快指针前进两步
// 慢指针指向的节点从原链表删除，头插法插入新链表
pHead = pSlow->next;
pSlow->next = newHead;
newHead = pSlow;
pSlow = pHead;
}
pHead = pSlow->next;
if (pQuick->next!=NULL) {
pSlow->next = newHead;
newHead = pSlow;
}
ListNode* p = pHead;
ListNode* q = newHead;
while (p!=NULL && q!=NULL) {
if (p->val != q->val)
return false;
p = p->next;
q = q->next;
}
return true;
}
或者利用栈
public class Palindrome {
public boolean isPalindrome(ListNode pHead){
ListNode fast = pHead;
ListNode slow = pHead;
Stack<Integer> stack = new Stack<Integer>();
/**
* 将链表的前半部分元素装入栈中，当快速runner
*（移动的速度是慢速runner的两倍）
* 到底链表尾部时，则慢速runner已经处于链表中间位置
*/
while(fast != null && fast.next != null){
stack.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}
//当链表为奇数个时，跳过中间元素
if (fast != null) {
slow = slow.next;
}
while(slow != null){
//如果两者不相同，则该链表不是回文串
if (stack.pop() != slow.val) {
return false;
}
slow = slow.next;
}
return true;
}
}
（5-3）、递归
采用递归的方式，将p定义成static，每次传入一个新的链表，让p指向链表首节点。通过递归，pHead从后往前，p从前往后，同时比较。
class Palindrome {
public:
bool isPalindrome(ListNode* pHead) {
// write code here
if(pHead==NULL)
return true;
static ListNode* p=NULL;
if(p==NULL) p=pHead;
if(isPalindrome(pHead->next)&&(p->val==pHead->val))
{
p=p->next;
return true;
}
p=NULL;
return false;
}
};
6、字符串中是否存在回文子串
7、求字符串的最长回文子串 （O(n) 时间复杂度）
这一小部分参考了博客：https://www.felix021.com/blog/read.php?2040
我再把思想简要说一下：
代码如下：