回文数系列题目(经典算法)

偏执的太偏执、 2022-08-27 11:41 155阅读 0赞

## 回文数 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 0

描述

请寻找并输出1至1000000之间的数m，它满足m、m^2和m^3均为回文数。回文数大家都知道吧，就是各位数字左右对称的整数，例如121、676、123321等。满足上述条件的数如m=11，m^2=121,m^3=1331皆为回文数。

输入

没有输入

输出

输出1至1000000之间满足要求的全部回文数，每两个数之间用空格隔开，每行输出五个数

解析：这道题直接模拟就好了，算是回文数中最简单的题了，直接写个判断回文数的函数，将整数num逆转，逆转的方法就是利用求余%和/的思想，此题总有一个常错的地方，就是m的平方和立方可能会超范围所以一定要用long long 或者\_int64即可。

贴一下自己的代码

#include <iostream>
    using std::endl;
    using std::cin;
    using std::cout;
    bool isHuiWenNumber(long long num)
    {
    	long long sum=0,temp=num;
    	//将整数num逆转
    	while(num)
    	{
    		sum=sum*10+num%10;
    		num/=10;
    	}
    	if(temp==sum)
    		return 1;
    	else
    		return 0;
    }
    int main()
    {
    #ifdef LOCAL
    	freopen("input.txt" , "r" , stdin);
    	freopen("output.txt" , "w" , stdout);
    #endif
    	int count = 0;
    	for(long long i=1; i<=1000000; ++i)
    	{
    		long long b=i*i;
    		long long c = b*i;
    		if(isHuiWenNumber(i) && isHuiWenNumber(b) && isHuiWenNumber(c))
    		{
    			count++;
    			cout << i;
    			if(count < 5)
    				cout << " ";
    			else
    			{
    				count = 0;
    				cout << endl;
    			}
    		}
    	}
    	return 0;
    }

## 最长回文子串 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 4

描述

输入一个字符串，求出其中最长的回文子串。子串的含义是：在原串连续出现的字符串片段。回文的含义是：正着看和倒着看是相同的，如abba和abbebba。在判断是要求忽略所有的标点和空格，且忽略大小写，但输出时按原样输出（首尾不要输出多余的字符串）。输入字符串长度大于等于1小于等于5000，且单独占一行(如果有多组答案，输出第一组)。

输入

输入一个测试数据n（1<=n<=10）；  
随后有n行，每行有一个字符串。

输出

输出所要求的回文子串。

样例输入

1
    Confuciuss say:Madam,I'm Adam.

样例输出

Madam,I'm Adam

解析：求最长的回文字符串，必须有个数组来专门记录去掉符号后每个字符在原字符串中的位置，这样才能在输出的时候输出原来的地方，另外，就是在判断回文串时，如果去枚举串，字符太多，肯定超时，所以应该去枚举回文串的中间位置，分奇数回文串和偶数回文串。

贴一下自己的代码

#include <iostream>
    #include <stdlib.h>
    #include <string>
    #include <ctype.h>
    #include <stdio.h>
    using std::endl;
    using std::cin;
    using std::cout;
    using std::getline;
    using std::string;
    const int MAXN = 5000;
    int p[MAXN];
    char tempStr[MAXN];
    int main()
    {
    #ifdef LOCAL
    	freopen("input.txt" , "r" , stdin);
    	freopen("output.txt" , "w" , stdout);
    #endif
    	int n;
    	cin >> n;
    	//将输入n后的回车符给吃掉
    	getchar();
    	while(n--)
    	{
    		string str;
    		int m = 0;
    		//从cin读入一行字符
    		getline(cin,str);
    		for(int i=0; i<str.length(); ++i)
    		{
    			if(isalpha(str[i]))
    			{
    				p[m] = i;
    				//忽略大小写，全部转换为大写
    				tempStr[m++] = toupper(str[i]);
    			}
    		}
    		//i为回文串中间的位置，为了提高效率枚举所有可能回文串的中间位置
    		//max保存回文串最大的长度
    		int maxlegth = 0;
    		//保存最长回文串在原str中的起始和终止的位置
    		int beg , end;
    		for(int i=0; i<m; ++i)
    		{
    			//j为回文串中离中间位置i的距离
    			//回文串是奇数
    			for(int j=0 ; j<=i && i+j <m; ++j)
    			{
    				if(tempStr[i-j] != tempStr[i+j])
    					break;
    				if(2*j+1 > maxlegth)
    				{
    					maxlegth = 2*j+1;
    					//记录当前回文串的起始和终止位置在原字符串str中的位置
    					beg = p[i-j];
    					end = p[i+j];
    				}
    			}
    			//回文串是偶数
    			for(int j=0; j<=i && i+j+1<m; ++j)
    			{
    				if(tempStr[i-j] != tempStr[i+j+1])
    					break;
    				if(2*j+2 > maxlegth)
    				{
    					maxlegth = 2*j+2;
    					//记录当前回文串的起始和终止位置在原字符串str中的位置
    					beg = p[i-j];
    					end = p[i+j+1];
    				}
    			}
    		}
    		//输出最长的回文字串
    		for(int i=beg; i<=end; ++i)
    			cout << str[i];
    		cout << endl;
    	}
    	return 0;
    }

## 少年 DXH ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 2

描述

大家都知道,DXH 幼时性格怪癖,小朋友都不喜欢和他玩,这种情况一直到 DXH 的少年时期也没有改变。  
少年时期的 DXH 迷上了"回文串",“回文串”是指正着读倒着读都一样的字符串。DXH一个人的时候喜欢在地上随便写一个字符串 S,然后在这个字符串的右边添加尽量少的字符(可以不添加,就是 0 个),使得这个字符串变成“回文串”。但玩的时间长了,DXH 的手也酸了,聪明的你能帮他写一个程序,算出这个添加最少字符形成的回文串吗?  
一个字符串 S\[1..L\]被称为回文串,当且仅当 S\[i\] = S\[L - i + 1\] (1 <= i <= L)。

输入

第一行,一个 T (T <= 100),表示有 T 个字符串需要你判断  
之后 T 行,每行一个字符串 S。  
S 的长度|S|满足 1 <= |S| <= 50,且 S 只由小写字母'a' -'z'组成。

输出

对于每个字符串,输出一行,每行一个字符串 S', 是在 S 右侧添加最少的字符形成的回文串。

样例输入

5
    add
    cigartragic
    dxhisgirl
    acaba
    abczyxyz

样例输出

adda
    cigartragic
    dxhisgirlrigsihxd
    acabaca
    abczyxyzcba

来源

[山东大学 ACM/ICPC 校赛高年级组试题 2012][ACM_ICPC _ 2012]

解析：这道题纠结了很久，最后没想到那么简单。

错误的想法：先开始是还是按照上题最长回文字串的思想来模拟回文串的中心位置，由于只能在字符串的最右边插入字符，所以我判断回文串的中心位置应该在偏右侧，也就是中心位置右边的字符数应该大于或者等于左边，然后还有当有匹配长度变大时更新，因为尽量找到偏右侧的回文串的中心位置，所以中心位置的枚举应该倒着来，从后向前枚举，但是当回文串是偶数的时候还是会出现问题，当为偶数的时候还需要判断回文串中心的位置在最右侧还是在中间，因为这都影响着最后填充字符的数量，反正感觉最后纠结的自己都写不下去了，开始思路挺清晰的，但是提交了几次wa，想了多组测试数据才发现自己代码漏洞太多，果然最后还是放弃了哈！

正解：很简单，既然说添加最少的字符，如果需要添加字符的话肯定是对称着字符串最左边添加的，所以可以枚举添加字符的数量从少到多，当是回文串的时候就可以停止了，此时当然就是添加最少的字符数量了哈！

感悟：这是太笨了，感觉自己受题目的影响，老想不到正确的地方，自己做的题也不少，提升感觉不大，也不知道为什么，还是从基础学起，打好基础再说哈！

贴一下ac的代码哈

#include <iostream>
    #include <string>
    using std::endl;
    using std::cin;
    using std::cout;
    using std::string;
    //判断是否为回文串
    int is_HuiWenStr(string s)
    {
    	int j = s.length() - 1;
    	for(int i=0; i<j; ++i , --j)
    	{
    		if(s[i] != s[j])
    		{
    			return 0;
    		}
    	}
    	return 1;
    }
    int main()
    {
    #ifdef LOCAL
    	freopen("input.txt" , "r" , stdin);
    	freopen("output.txt" , "w" , stdout);
    #endif
    	int N;
    	cin >> N;
    	while(N--)
    	{
    		string str , result;
    		cin >>str;
    		if(is_HuiWenStr(str))
    		{
    			cout << str << endl;
    		}else{
    			int length = str.length();
    			//枚举添加的字符数量
    			for(int i=0;i<length; ++i)
    			{
    				result = str;
    				for(int j=i;j>=0;--j)
    				{
    					result+= str[j];
    				}
    				if(is_HuiWenStr(result))
    				{
    					cout << result << endl;
    					break;
    				}
    			}
    		}
    	}
    }

[ACM_ICPC _ 2012]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%E5%B1%B1%E4%B8%9C%E5%A4%A7%E5%AD%A6+ACM%2FICPC+%E6%A0%A1%E8%B5%9B%E9%AB%98%E5%B9%B4%E7%BA%A7%E7%BB%84%E8%AF%95%E9%A2%98+2012