偶位回文递归解决

冰清玉洁丸

我们将这样的数字定义为偶位回文数：

1.该数字的位数是偶数
2.该数字是一个回文数
例如：1221 就是一个偶位回文数，而 121 和 1234 都不是偶位回文数，前者不满足数字的位数是偶数，后者不满足回文数。

给定一个正整数 n，请你求出从小到大前 n 个偶位回文数的和是多少？

输入共一行，一个正整数 n
输出前 n 个偶位回文数的和。

我的代码：

#include <iostream>
#include <stack>
#include <cmath>
using namespace std;

stack<int> every;
int init(int n)
{
        int m = n;
        
        for (int i = 0; n != 0; i++)
        {
                every.push(n % 10);
                n /= 10;
        }
        int length = every.size();
        int a[length * 2];
        for (int i = 0; !every.empty(); i++)
        {
                a[i] = every.top();
                every.pop();
        }
        for (int i = length, j = 1; i < length * 2; i++, j += 2)
        {
                a[i] = a[i - j];
        }
        int sum = 0;
        for (int i = 0, j; i < length; i++)
        {
                j = pow(10, length - 1 - i);
                sum += a[i] * j;
        }
        
        if (m == 0)
        {
                return sum;
        }
        else
        {
                return (sum + init(--m));
        }
}

int main()
{
        int n;
        cin>>n;
        
        cout<<init(n);
        
        return 0;
}

目测无错误，递交后5WA，1RE
求挑错

傻眼貓咪

#include <iostream>
#include <string.h>

// 判断字符串是否回文
bool isPalindrome(char str[]){
        int i = 0;
        int n = strlen(str) - 1;
        while (n > i){if (str[i++] != str[n--]) return false;}
        return true;
}

// 判断字符串长度是否偶数
bool isEven(char str[]){return !(strlen(str)%2);}

int main()
{
    int sum = 0, n;
    std::cin >> n;
    for(int i = 0; i < n; i++){
        std::string a = std::to_string(i); // 将整数转换成字符串
        char b[a.length() + 1]; // 定义字符数组
        strcpy(b, a.c_str()); // 将字符串储存进字符数组里
        if(isEven(b) && isPalindrome(b)){ // 开始判断条件
            sum += i;
        }
    }
    std::cout << sum << std::endl;
    return 0;
}

傻眼貓咪

5WA，1RE 表示 5 题错，1 题执行时错误

冰清玉洁丸

傻眼貓咪 发表于 2021-11-14 13:20

不对，你这样直接所有测试点全错

傻眼貓咪

冰清玉洁丸 发表于 2021-11-14 17:23
不对，你这样直接所有测试点全错

抱歉，我误会你的题目，代码已经修改：

#include <iostream>
#include <string.h>

// 判断字符串是否回文
bool isPalindrome(char str[]){
        int i = 0;
        int n = strlen(str) - 1;
        while (n > i){if (str[i++] != str[n--]) return false;}
        return true;
}

// 判断字符串长度是否偶数
bool isEven(char str[]){return !(strlen(str)%2);}

int main()
{
    long long sum = 0;
    int n;
    std::cin >> n;
    for(int i = 0; n; i++){
        std::string a = std::to_string(i); // 将整数转换成字符串
        char b[a.length() + 1]; // 定义字符数组
        strcpy(b, a.c_str()); // 将字符串储存进字符数组里
        if(isEven(b) && isPalindrome(b)){ // 开始判断条件
            sum += i;
            n--;
        }
    }
    std::cout << sum << std::endl;
    return 0;
}

冰清玉洁丸

傻眼貓咪 发表于 2021-11-14 17:49
抱歉，我误会你的题目，代码已经修改：

两个正确，三个超时

傻眼貓咪

冰清玉洁丸 发表于 2021-11-14 17:57
两个正确，三个超时

请问题目范例参数边界多少？

傻眼貓咪

最大参数极限是多少？

冰清玉洁丸

1≤n≤10^5

冰清玉洁丸

傻眼貓咪 发表于 2021-11-14 18:02
最大参数极限是多少？

1≤n≤10^5

傻眼貓咪

太大了，我用的是数组列表肯定超时，建议用 vector 向量数组（哈希 hash）

冰清玉洁丸

傻眼貓咪 发表于 2021-11-14 18:07
太大了，我用的是数组列表肯定超时，建议用 vector 向量数组（哈希 hash）

好的自己试试

傻眼貓咪

冰清玉洁丸 发表于 2021-11-14 18:07
好的自己试试

#include <iostream>
#include <string.h>
#include <vector>

// 判断字符串是否回文
bool isPalindrome(std::vector<char> &str){
        int i = 0;
        int n = str.size() - 1;
        while (n > i){if (str[i++] != str[n--]) return false;}
        return true;
}

// 判断字符串长度是否偶数
bool isEven(std::vector<char> &str){return !(str.size()%2);}

int main()
{
    long long sum = 0;
    int n;
    std::cin >> n;
    for(int i = 0; n; i++){
        std::string a = std::to_string(i); // 将整数转换成字符串
        std::vector<char> b(a.begin(), a.end());
        if(isEven(b) && isPalindrome(b)){ // 开始判断条件
            sum += i;
            n--;
        }
    }
    std::cout << sum << std::endl;
    return 0;
}

冰清玉洁丸

傻眼貓咪 发表于 2021-11-14 18:26

感谢，但还是有3个超时，我自己写吧

傻眼貓咪

哈哈