c++ - 如何让我的程序运行得更快？

Question

我尝试运行这段代码，但它显示在少数情况下超过了时间限制，我该如何缩短时间？

我需要了解我在我的程序中使用了哪些时间花费了很多时间，比如一些功能等。我知道通过改进迭代和复杂性我可以减少执行时间但它没有多大帮助。请帮助

程序很简单，我取a点和b点，计算所有回文数的个数。

#include<stdio.h>
int ifpalin(int g)
{
    int rev=0;
    int tmp=g;
    while(tmp>0)
    {
        rev=rev*10+(tmp%10);
        tmp=tmp/10;
    }
    if(rev==g)
        return 1;
    else
        return 0;
}
int findpalin(int a1,int b1)
{
    int sm=0;
    for(int i=a1;i<=b1;i++)
    {
      if  (ifpalin(i)==1)
        sm++;
    }
    printf("%d",sm);
    printf("\n");
    return 0;
}
int main()
{
int a,b,n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a);
        scanf("%d",&b);
        findpalin(a,b);
    }
    return 0;
}

Answer 1

您的代码已经非常高效(作为算法的实现，这是可以改进的地方)。这些挑战希望您找到一种“非显而易见”但更有效的算法。也就是说，在这种特殊情况下，您不应该检查 a 和 b 之间的每个数字。

这里还有另一种解决方案，即您可以直接“知道”回文的数量。像这样想一想:

一个数字有10个回文[0, ..., 9],

对于两位数，有9个回文[11, ..., 99]。

对于三位数字，有 9 种可能性，其中第一位和最后一位数字相等 [1, ..., 9]。对于可行的回文，中间部分也必须是回文。由于中间有一个数字，我们知道这里有 10 种回文的可能性，因此我们有 9 * 10 = 90 3 个数字的回文。

对于四位数，我们得到 9 * 10(两位回文，现在也允许使用 00)，对于五位数 9 * 100(三位数 p，允许从 0 开始)。

因此，您可以推导出 n 位数字的公式。然后，您可以直接推导 a 和 b 之间的大条纹的数字，只需要担心哪些数字是相关的以及由于 a 和 b 不是 10^ 而在开始和结束时丢失了多少数字 ^ (n-1) 和 10^n - 1