PAT甲级1136A Delayed Palindrome

Posted on | | Visitors:
Words count in article: 698 字 | Reading time ≈ 3 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805345732378624

题解一

英语

  • notation

    标记法

  • palindromic

    回文的

  • palindrome

    回文

  • be paired with

    与……配对

思路、注意点和代码

  • 要实现回文数判断
  • 要实现字符串逆序
  • 整体思路就是题目描述的那样：判断是不是回文数，不是的话就逆序后和原数相加，重复这一过程直至得到回文数或者超过10次迭代

下面是我刚开始时写的代码，结果是Partially Accepted，得了14分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Problem: PAT Advanced 1136
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805345732378624
// Tags: String

#include <iostream>
#include <string>
using namespace std;

bool isPalindromic(string s){
    int len = s.length();
    for (int i = 0; i < len/2; i++)
        if(s[i] != s[len-1-i])
            return false;
    return true;
}

int main()
{
    string a_str, b_str, c_str;
    int a, b, c;
    cin >> a_str;
    int N = 10;
    while (N--){
        b_str = string(a_str.rbegin(), a_str.rend());
        c_str = to_string(stoi(a_str) + stoi(b_str));
        cout << a_str << " + " << b_str << " = " << c_str << endl;
        if (isPalindromic(c_str)){
            cout << c_str << " is a palindromic number.";
            return 0;
        }
        a_str = c_str;
    }
    cout << "Not found in 10 iterations.";
    return 0;
}

题解二

看了下柳婼的代码，和我写的题解一相比，她的代码有以下不同：

  • 她考虑了输入就是回文数的边界情况，我没有考虑，这个测试点占4分

  • 回文数的判断方法不同，她是判断逆序后是否相等，我是遍历判断

  • 她手动实现了字符串数字的加法，而我是将字符串转成数字进而相加，这里我忽略了数值范围，这个测试点占2分

    题目说不超过1000位，就算使用longlong也不行，所以必须手动实现字符串相加

基于我刚开始写的题解一和上面分析的内容，正确代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Problem: PAT Advanced 1136
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805345732378624
// Tags: String Palindrome

#include <iostream>
#include <string>
using namespace std;

bool isPalindromic(string s){
    int len = s.length();
    for (int i = 0; i < len/2; i++)
        if(s[i] != s[len-1-i])
            return false;
    return true;
}

string addString(string a, string b){
    int carry = 0;
    int sum;
    for (int i = a.length() - 1; i >= 0; i--) {
        sum = a[i] - '0' + b[i] - '0' + carry;  // 注意进位和'0'
        a[i] = sum % 10 + '0';  // 注意'0'
        carry = sum / 10;
    }
    if (carry == 1)
        a = "1" + a;
    return a;
}

int main()
{
    string a_str, b_str, c_str;
    cin >> a_str;
    if (isPalindromic(a_str)){
        cout << a_str << " is a palindromic number.";
        return 0;
    }

    int N = 10;
    while (N--){
        b_str = string(a_str.rbegin(), a_str.rend());
        c_str = addString(a_str, b_str);
        cout << a_str << " + " << b_str << " = " << c_str << endl;
        if (isPalindromic(c_str)){
            cout << c_str << " is a palindromic number.";
            return 0;
        }
        a_str = c_str;
    }
    cout << "Not found in 10 iterations.";
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!