1023 Have Fun with Numbers

题目大意

一个大整数加倍后是够由原来的那些数字构成

核心思路

方法一：

1. 使用map<int,int> mp存储每一个数字和出现次数，原始串s，结果串s2

2. 遍历字符串s的每一个字符，把该字符转换成数字，统计该数字的出现次数

3. 从原始串的length()-1位开始遍历到第0位，模拟将每一位字符转换成对应数字并加倍的过程，将该数字的出现次数减1，同时生成结果串s；如果第0位还有进位，把该进位也放入结果串

4. 遍历mp的每一对键值对，如果发现有值不为0的键值对，说明不满足题目条件，直接退出遍历

5. 输出
   方法二：
   只有第三步不同：将结果串和原始串重新排序(数字字符从小到大排列)，如果排序后两个字符串还相等，满足题目条件；否则不满足题目条件

代码

方法一：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
    
map<int,int> mp;//键为数字，值为该数字出现的次数

int main(){
    //读入原始字符串
    string s;
    cin>>s;
    //遍历字符串s的每一个字符，统计每个字符的出现次数
    for(int i=0;i<s.length();i++){
        mp[int(s[i])-48]++;
    }
    //模拟将每一位字符加倍的过程，更新该字符的哈希值，同时生成结果串
    string s2="";//结果字符串s2
    int ans=0;//进位数字
    int temp;//当前位数字
    for(int i=s.length()-1;i>=0;i--){
        temp=(((int)s[i]-48)*2+ans)%10;
        ans=(((int)s[i]-48)*2+ans)/10;
        mp[temp]--;
        s2=to_string(temp)+s2;
    }
    if(ans!=0){
        s2=to_string(ans)+s2;
        mp[ans]--;
    }
    //判断当前字符串和结果串是否由相同的数字字符组成(如果相同，每一个哈希值都应该是0)
    bool flag=true;
    for(auto it=mp.begin();it!=mp.end();it++){
        if(it->second!=0){
            flag=false;
            break;
        }
    }
    //输出
    if(flag){
        cout<<"Yes"<<endl;
        cout<<s2<<endl;
    }else{
        cout<<"No"<<endl;
        cout<<s2<<endl;
    }
    return 0;
}

方法二：

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

int main(){
    //读入原始字符串
    string s;
    cin>>s;
    //处理加倍后的数字字符串的每一个字符
    string s2="";//结果字符串s2
    int ans=0;//进位数字
    int temp;//当前位的最终数字
    for(int i=s.length()-1;i>=0;i--){
        temp=(((int)s[i]-48)*2+ans)%10;
        ans=(((int)s[i]-48)*2+ans)/10;
        s2=to_string(temp)+s2;
    }
    if(ans!=0){//说明整个数字进了一位
        s2=to_string(ans)+s2;
    }
    //判断当前字符串和结果串是否由相同的数字字符组成(如果相同，排序后的字符串s3应该和s相同)
    string s3=s2;
    sort(s.begin(),s.end());
    sort(s3.begin(),s3.end());
    //做出相应输出
    if(s==s3){
        cout<<"Yes"<<endl;
        cout<<s2<<endl;
    }else{
        cout<<"No"<<endl;
        cout<<s2<<endl;
    }
}