PAT（甲级）1024 Palindromic Number (25point(s))-蒲公英云

PAT（甲级）1024 Palindromic Number (25point(s))

悠悠 2024-05-08 06:00 197阅读 0赞

题目

题目链接

思路

题目大意：判断一个字符串是不是回文串，如果不是可以翻转后相加在判断是不是回文串；
本质是大数相加问题，大数相加需要先把数字翻转一下，将个位数字放到数组的第0号位，优点是相加的时候进位方便；

代码

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 120;
char s[15];
vector<int> a, b;
//判断是不是回文串
bool judge(vector<int> v1){
     vector<int> v2 = v1;
     reverse(v2.begin(), v2.end());
     if(v1 == v2) return true;
     else return false;
}
int main()
{
     scanf("%s", s);
     int k;
     scanf("%d", &k);
     //字符转化为数字
     for(int i = 0; i < strlen(s); i ++) a.push_back(s[i] - '0');
     int step = 0;
     reverse(a.begin(), a.end());
     while(judge(a) == false && step < k){
          b = a;
          reverse(b.begin(), b.end());
          int carry = 0, temp;
          //整数相加
          for(int i = 0; i < a.size(); i ++){
               temp = a[i] + b[i] + carry;
               a[i] = temp % 10;
               carry = temp / 10;
          }
          if(carry != 0) a.push_back(carry);//注意最后可能进一位
          step ++;
     }
     for(int i = a.size() - 1; i >= 0; i --) printf("%d", a[i]);
     printf("\n%d\n", step);
     system("pause");
     return 0;
}