共计 1195 个字符,预计需要花费 3 分钟才能阅读完成。
题目粗心:
给出一个长度不超过 20 的整数,问这个整数乘以 2 当前的数位是否为原数数位的一个排列
算法思路:
因为长度有可能达到 20 位,超过了 long long 的存储范畴,所以这里采纳 string 存储输出的整数。该题只须要解决两个问题,第一个就是如何判断 2 个整数的互为排列,第二个就是如何计算一个字符串与 2 的乘法。解决第一个问题的思路就是利用 hash 映射的思维,利用 countOfS
存储 0~9 数字呈现的次数,在输出的时候做加法,对于输出的数字 s 的每一位 s[i]
,++countOfS[s[i]-'0']
, 在做完乘法后失去数字 r, 而后对 r 的每一个数字 r[k] 做减法,--countOfS[r[k]-'0'];
如果减完后呈现小于 0 的状况就阐明这两个不是互为排列并且应用 isTrue
记录下来。第二个问题的解决思路就是应用指针 j 对 s 从后向前扫描,并且应用 carry
记录上一位的进位,对于每一位数字 s[j]
,都乘以 2 而后加上进位carry
,(s[j]-'0')*2 + carry
,该后果应用multi
保留,而后计算进位 multi/10,并将本位应用 r 保留,r += to_string(multi%10);
最初依据 isTrue
是否为 true
输入 Yes
和No
,而后再输入逆置后的 r 即可。
留神点:
1、在进行乘法运算的时候,最高位如果有进位的化,也就是 carry 在退出循环后不为 0 得再增加到 r 中,测试点 2 和测试点 7 考查。
提交后果:
AC 代码:
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
string s;
cin>>s;
int countOfS[11] = {};// 统计 s 中每一个数字呈现的次数
for (int i = 0; i < s.size(); ++i) {++countOfS[s[i]-'0'];
}
// 将 s 乘以 2
string r;
int carry = 0;
int multi;// 局部乘积
for (int j = s.size()-1; j >=0 ; --j) {multi = (s[j]-'0')*2 + carry;
carry = multi/10;
r += to_string(multi%10);
}
// 最高位还有进位
if(carry!=0){r += to_string(carry);
}
reverse(r.begin(),r.end());
bool isTrue = true;
for (int k = 0; k < r.size(); ++k) {--countOfS[r[k]-'0'];
if(countOfS[r[k]-'0']<0){
isTrue = false;
break;
}
}
if(isTrue){printf("Yes\n");
} else {printf("No\n");
}
printf("%s",r.c_str());
return 0;
}