偶位回文递归解决

冰清玉洁丸

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

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

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

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

我的代码：

1. #include <iostream>
   
2. #include <stack>
   
3. #include <cmath>
   
4. using namespace std;
   
5. 
   
6. stack<int> every;
   
7. int init(int n)
   
8. {
   
9.         int m = n;
   
10.        
    
11.         for (int i = 0; n != 0; i++)
    
12.         {
    
13.                 every.push(n % 10);
    
14.                 n /= 10;
    
15.         }
    
16.         int length = every.size();
    
17.         int a[length * 2];
    
18.         for (int i = 0; !every.empty(); i++)
    
19.         {
    
20.                 a[i] = every.top();
    
21.                 every.pop();
    
22.         }
    
23.         for (int i = length, j = 1; i < length * 2; i++, j += 2)
    
24.         {
    
25.                 a[i] = a[i - j];
    
26.         }
    
27.         int sum = 0;
    
28.         for (int i = 0, j; i < length; i++)
    
29.         {
    
30.                 j = pow(10, length - 1 - i);
    
31.                 sum += a[i] * j;
    
32.         }
    
33.        
    
34.         if (m == 0)
    
35.         {
    
36.                 return sum;
    
37.         }
    
38.         else
    
39.         {
    
40.                 return (sum + init(--m));
    
41.         }
    
42. }
    
43. 
    
44. int main()
    
45. {
    
46.         int n;
    
47.         cin>>n;
    
48.        
    
49.         cout<<init(n);
    
50.        
    
51.         return 0;
    
52. }

复制代码

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

傻眼貓咪

1. #include <iostream>
   
2. #include <string.h>
   
3. 
   
4. // 判断字符串是否回文
   
5. bool isPalindrome(char str[]){
   
6.         int i = 0;
   
7.         int n = strlen(str) - 1;
   
8.         while (n > i){if (str[i++] != str[n--]) return false;}
   
9.         return true;
   
10. }
    
11. 
    
12. // 判断字符串长度是否偶数
    
13. bool isEven(char str[]){return !(strlen(str)%2);}
    
14. 
    
15. int main()
    
16. {
    
17.     int sum = 0, n;
    
18.     std::cin >> n;
    
19.     for(int i = 0; i < n; i++){
    
20.         std::string a = std::to_string(i); // 将整数转换成字符串
    
21.         char b[a.length() + 1]; // 定义字符数组
    
22.         strcpy(b, a.c_str()); // 将字符串储存进字符数组里
    
23.         if(isEven(b) && isPalindrome(b)){ // 开始判断条件
    
24.             sum += i;
    
25.         }
    
26.     }
    
27.     std::cout << sum << std::endl;
    
28.     return 0;
    
29. }

复制代码

傻眼貓咪

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

冰清玉洁丸

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

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

傻眼貓咪

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

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

1. #include <iostream>
   
2. #include <string.h>
   
3. 
   
4. // 判断字符串是否回文
   
5. bool isPalindrome(char str[]){
   
6.         int i = 0;
   
7.         int n = strlen(str) - 1;
   
8.         while (n > i){if (str[i++] != str[n--]) return false;}
   
9.         return true;
   
10. }
    
11. 
    
12. // 判断字符串长度是否偶数
    
13. bool isEven(char str[]){return !(strlen(str)%2);}
    
14. 
    
15. int main()
    
16. {
    
17.     long long sum = 0;
    
18.     int n;
    
19.     std::cin >> n;
    
20.     for(int i = 0; n; i++){
    
21.         std::string a = std::to_string(i); // 将整数转换成字符串
    
22.         char b[a.length() + 1]; // 定义字符数组
    
23.         strcpy(b, a.c_str()); // 将字符串储存进字符数组里
    
24.         if(isEven(b) && isPalindrome(b)){ // 开始判断条件
    
25.             sum += i;
    
26.             n--;
    
27.         }
    
28.     }
    
29.     std::cout << sum << std::endl;
    
30.     return 0;
    
31. }

复制代码

冰清玉洁丸

傻眼貓咪 发表于 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
好的自己试试

1. #include <iostream>
   
2. #include <string.h>
   
3. #include <vector>
   
4. 
   
5. // 判断字符串是否回文
   
6. bool isPalindrome(std::vector<char> &str){
   
7.         int i = 0;
   
8.         int n = str.size() - 1;
   
9.         while (n > i){if (str[i++] != str[n--]) return false;}
   
10.         return true;
    
11. }
    
12. 
    
13. // 判断字符串长度是否偶数
    
14. bool isEven(std::vector<char> &str){return !(str.size()%2);}
    
15. 
    
16. int main()
    
17. {
    
18.     long long sum = 0;
    
19.     int n;
    
20.     std::cin >> n;
    
21.     for(int i = 0; n; i++){
    
22.         std::string a = std::to_string(i); // 将整数转换成字符串
    
23.         std::vector<char> b(a.begin(), a.end());
    
24.         if(isEven(b) && isPalindrome(b)){ // 开始判断条件
    
25.             sum += i;
    
26.             n--;
    
27.         }
    
28.     }
    
29.     std::cout << sum << std::endl;
    
30.     return 0;
    
31. }

复制代码

冰清玉洁丸

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

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

傻眼貓咪

哈哈