PAT 1023 Have Fun with Numbers (20分) 字符数组解决大整数存储溢出

Scroll Down

题目

Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!

Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.

Input Specification:
Each input contains one test case. Each case contains one positive integer with no more than 20 digits.

Output Specification:
For each test case, first print in a line "Yes" if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or "No" if not. Then in the next line, print the doubled number.

Sample Input:
1234567899
Sample Output:
Yes
2469135798

题目解读

给你一个正整数A,长度 <= 20,问,如果把它加倍,得到数字B,==问B是不是 仅仅是组成A的那些数字的另一种排列方式==。

比如 123456789 加倍后是 246913578,它只是这些数字换了个顺序,所以它是。
比如 123 加倍后 是 456 ,很明显不是
再比如 900 加倍后是 1800,长度都超出了,很明显不是

思路解析

  • 第一,我们怎么表示,以及判断这个所谓的排列?很简单,每一个位置都0-9,那么我只需要用一个大小为10的数组存储0-9每个数字出现的次数就可以,如果加倍后只是换了一种排列方式,那么0-9每个数字出现的次数肯定是不变的。
  • 第二,是否需要两个数组分别统计A0-9出现的次数,B0-9出现的次数?可以,但没必要,我们只需要一个数组book10],统计A时,0-9出现的次数++,统计B时,0-9出现的次数--,==最后遍历数组book,如果某个位置值不为0,B一定不只是A的另一种排列。==
  • 第三,怎么进行加倍操作?乘法怎么算的就怎么来呗,不就是从后往前==每个数字*2,当前位置对10取余,有进位就向前进位,循环这个过程呗==。因为我们用字符数组存储,所以还得注意将字符转为数字(+ '0',- '0')进行计算,计算完再转为字符存回去。
  • 第四,怎么判断B不是A的另一种排列
    1. book[10]某个位置不为0
    2. 加倍操作后,最后一次进位不为0,说明长度超出。

代码一(详细过程)

  1. 字符存储数字A
  2. 统计A中0-9分别出现多少次,book[i]++
  3. 加倍操作得到B,carry表示每次的进位
  4. 统计B中0-9分别出现多少次,book[i]--
  5. 遍历book,如果某个位置不为0,设置flag = true
  6. 如果 carry > 0 || flag == true,输出 "No",否则输出 "Yes"
  7. 输出B的字符串。(如果carry>0,那么要先输出carry,他是B的最高位,注意用数字输出,因为它本身就是0/1,int保存的,不存在字符转换问题,别跟我一样傻了吧唧的用%c输出,提交了三次都是答案错误。。。)
#include <iostream>
#include <cstring> 
using namespace std;

int main() {

    // 每一个位置上数字都是0-9,用一个数组保存0-9各出现了多少次
    // 不用为统计a创建一个数组,统计b再创建一个数组,只要用一个数组
    // 统计a时,对应位置++,统计b时,对应位置--,
    // 最后遍历数组,某个位置不为0,或者2a最高位有进位,说明2a不是a的另一种排列,输出"No"
    int book[10] = {0};

    // 十进制数字,最长20位,用int 和 long long都无法存储
    // 用字符存储
    char num[21]; // 
    scanf("%s", &num); 
    int len = strlen(num);
    // 统计原数各个位置 0-9各出现多少次
    for (int i = 0; i < len; ++i) {
        book[num[i] - '0']++;
    }
    // double原数,carry是进位,这个循环执行完后carry是原数字最高位的进制,若它不为0说明加倍后数字变长了肯定不合题意
    int carry = 0;
    for (int i = len - 1; i >= 0; --i) {
        int temp = 2 * (num[i] - '0') + carry;
        num[i] = temp % 10 + '0';
        carry = temp / 10;
    }
    // 统计double后,0-9各出现多少次
    for (int i = 0; i < len; ++i) {
        book[num[i] - '0']--;
    }
    // 判断加倍后的数字是否只是原数字的另一种排列
    bool flag = false;
    for (int i = 0; i < 10; ++i) {
        if (book[i] != 0) {
            flag = true;
            break;
        }
    }
    // 不要漏了最高位进位的情况
    printf("%s\n", flag || carry ? "No" : "Yes");
    // 输出加倍后的数字,如果最高位进位了也要输出
    if (carry) printf("%d", carry);
    for (int i = 0; i < len; ++i) 
        printf("%d", num[i]);
    return 0;
}

代码二(最简代码)

上面的代码我是为了把整个过程表示的清清楚楚,但其实 步骤 2 - 3 - 4可以合并到一个for循环完成,合并完那是相当的好看呐。

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

int main() {

    int book[10] = {0};
    // 十进制数字,最长20位,用int 和 long long都无法存储
    // 用字符存储
    char num[21]; // 
    scanf("%s", &num); 
    int len = strlen(num);
    // carry是进位,这个循环执行完后carry是原数字最高位的进制,若它不为0说明加倍后数字变长了肯定不合题意
    int carry = 0;
    for (int i = len - 1; i >= 0; --i) {
        // 统计 A 各个位置 0-9各出现多少次
        int temp = num[i] - '0';
        book[temp]++;
        // 加倍转换为B
        temp = temp * 2 + carry;
        // 当前位置保留对10取余
        num[i] = temp % 10 + '0';
        // 向前进位
        carry = temp / 10;
        // 统计 B 各个位置 0-9各出现多少次
        book[num[i] - '0']--;
    }
    // 判断加倍后的数字是否只是原数字的另一种排列
    bool flag = false;
    for (int i = 0; i < 10; ++i) {
        if (book[i] != 0) {
            flag = true;
            break;
        }
    }
    // 不要漏了最高位进位的情况
    printf("%s\n", flag || carry ? "No" : "Yes");
    // 输出加倍后的数字,如果最高位进位了也要输出
    if (carry) printf("%d", carry);
    printf("%s", num);
    return 0;
}