如何使代码更快以适应时间限制？

Question

我正在尝试在 spoj https://www.spoj.com/problems/PALIN 上提交这段代码，它要求找到给定数字 n 的下一个最小回文，但是由于这段代码有效，它很慢，因为它超过了时间限制（ 2-9 秒）。有没有另一种方法可以更快地解决这个问题？

第一行包含整数t，测试用例的数量。在接下来的 t 行中给出了整数 K。

代码：

#include <bits/stdc++.h>
using namespace std;

 int main() {
    long long int t,k; string k2,k1;
    cin>>t;
    while(t--){
        cin>>k;k++;
        do{
            k1=to_string(k);
            k2=k1;
            reverse(k1.begin(), k1.end());
            if(k1==k2){cout<<k<<endl;}
            k++;
        }while(k1!=k2);
    }
    return 0;
}

示例输入：

2
808
2133

示例输出：

818
2222

Answer 1

最明显的做法是停止复制和反转字符串。相反，将第一个字符与最后一个字符进行比较，然后将第二个字符与倒数第二个字符进行比较，依此类推。

此外，您为什么要使用字符串？字符串复杂且昂贵。您正在执行的操作完全可以根据数字完成。

最后，考虑像“473X”这样的数字。 None 其中可以是回文。您不必测试全部 10 个。如果您要查看以“47”开头的四位数，那么只有一个是回文 - 那么您为什么要检查所有一百个？

在编写解决此类问题的代码之前，请仔细考虑您将要使用的算法，并确保您没有任何明显的浪费。

如何使代码更快以适应时间限制？

How to make code faster to fit it in time limit?

c++

performance

c++14

c++17