描述
当一个正整数正着读和倒着读都一样是,这个数被称为回文数。
现在给出一个正整数N,请求出N右边离它最近的那个回文数。N≤10的100000次方。
输入
第一行给出T(T≤30),表示有T组数据。
接下来的T行,每行有一个数字。
输出
每一行输出每一组数据的下一个回文数。
#include<stdio.h>
#include<math.h>
int main()
{
int t,i,j,flag,n;
scanf("%d",&t);//输入第一个组数
if(t==0||t>pow(10.0,100000))return 0;
for(j=0; j<t; j++)
{
flag=1;
scanf("%d",&n);
i=n+1;
while(flag){
if(nixu(i)==i){flag=0;printf("%d\n",i);}
else i++;
}
}
return 0;
}
int nixu(int n)
{
int m=0;
while(n)
{
m=m*10+n%10;
n=n/10;
}
//printf("回文 %d\n",m);
return m;
}
你i想问啥
首先,我们需要了解回文数的定义:即正着读和倒着读都是一样的数。我们需要找到一个大于给定正整数N的下一个回文数。
根据题目要求,我们的输入包含多组数据,请依次求解。因此,我们需要循环处理每一组数据。
对于每一组数据,我们可以通过以下步骤找到下一个回文数:
将给定的正整数N转换为字符串,方便处理数字。
定义一个函数isPalindrome,用于判断一个字符串是否是回文数。可以通过前后指针遍历字符串进行比较。
循环递增给定正整数N,直到找到下一个回文数为止。在每次循环中,将N递增1,并将其转换为字符串。
在每次递增N之后,调用isPalindrome函数判断新的字符串是否是回文数。如果是回文数,则返回该数作为下一个回文数。
如果没有找到下一个回文数,则继续递增N。
下面是具体的代码实现:
def isPalindrome(s):
if len(s) <= 1:
return True
left, right = 0, len(s)-1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def findNextPalindrome(N):
while True:
N += 1
if isPalindrome(str(N)):
return N
T = int(input()) # 输入组数
for _ in range(T):
N = int(input()) # 输入正整数N
nextPalindrome = findNextPalindrome(N) # 找到下一个回文数
print(nextPalindrome)
该解决方案的时间复杂度为O(nk),其中n表示给定正整数的位数,k表示每个数字是否为回文数的时间复杂度。
N ≤ 10的100000次方 ,这数得多大了?