专栏首页vblogPAT 1023 Have Fun with Numbers (20分) 字符数组解决大整数存储溢出

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

题目

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1041 Be Unique (20分)利用数组找出只出现一次的数字

    Being unique is so important to people on Mars that even their lottery is design...

    vivi
  • PAT 1021 Deepest Root (25分) 从测试点3超时到满分再到代码优化

    A graph which is connected and acyclic can be considered a tree. The height of t...

    vivi
  • PAT1047 Student List for Course (25分)避免运行超时(内存溢出)

    Zhejiang University has 40,000 students and provides 2,500 courses. Now given th...

    vivi
  • 超像素经典算法SLIC的代码的深度优化和分析。

         现在这个社会发展的太快,到处都充斥着各种各样的资源,各种开源的平台,如github,codeproject,pudn等等,加上一些大型的官方的开源软件...

    用户1138785
  • P2661 信息传递

    题目描述 有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。 游戏...

    attack
  • 最长递减子序列(nlogn)(个人模版)

    最长递减子序列(nlogn): 1 int find(int n,int key) 2 { 3 int left=0; 4 int ri...

    Angel_Kitty
  • UVA Dividing coins

    题目链接: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page...

    ShenduCC
  • 背包九讲-问法的灵活变化

    要求的是“总价值最小”“总件数最小”,只需简单的将上面的状态转移方程中的max改成min即可。

    十四君
  • BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

    可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

    attack
  • 命名那个数字

    分析:此题本来有个极复杂的代码,后来看了某位大佬的stl解法,感觉极为简便自己写了一个,

    glm233

扫码关注云+社区

领取腾讯云代金券