将阿拉伯数字转换成大写中文

https://www.notion.so/images/page-cover/rijksmuseum_claesz_1628.jpg

今天同事分享了一个有意思的算法题,感觉挺有意思的。题目来自浙大PAT考试 A1082 Read Number in Chinese。以下是原题:

Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output Fu first if it is negative. For example, -123456789 is read as Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu. Note: zero (ling) must be handled correctly according to the Chinese tradition. For example, 100800 is yi Shi Wan ling ba Bai

给定一个不超过9位的整数,按照汉语阅读的习惯,将其转换成对应的中文。比如输入100800,输出一十万零八百

先试着来分析一下解题思路。首先,看到这个题目的第一反应是,我们需要提前枚举出对应的中文汉字。

'零','一','二','三','四','五','六','七','八','九','十','百','千', '万', '亿'

虽然数字很大,但是上述的这些汉字已经足够覆盖所有9位数以内的场景了。从两位数的数字开始,数字对应的表达就是“个位数字”+”计数单位”的组合。比如80是八十,102是一百零二,8080是八千零八十,123456是一十二万三千四百五十六。

a4d05b1e27690988

因此我们可以推测,这道题中应该与每四位一次的循环操作有关。

分割法

按照四位一轮转换的思路来尝试,先考虑第一种方法:从最后一位开始,每四位数字切隔一次,将数字分成小组,每个小组转换之后再反向合并起来。下面的例子实现的是加上“万”,“亿”,并不是完整代码。

function transform(num) { num = num + ''; let units = ['十', '百', '千', '万', '亿']; let group = []; // const transGroup = (g) => {...} for(let i = num.length - 1; i >= 0; i = i -4) { // 反向分割 group.push(num.slice(Math.max(i-4, 0), i + 1)); } return group.map((item, idx) => { // 转换每一组 // transGroup(item); if (idx >= 1) { // 超过四位之后开始加上“万”、“亿” return item + units[idx + 2]; } return item; }).reverse(); } transform(4003); => ['4003'] transform(403); => ['403'] transform(4300); => ['4300'] transform(103000); => ['10万', '3000'] transform(100303000); => ['1亿', '0030万', '3000'] transform(1303101000); => ['13亿', '0310万', '1000']

到这一步其实题目已经解决一半了,接下来要做的事情就是实现四位数字的汉字转换,也就是代码中对应的transGroup方法。

... const trans = (str) => { let result = ''; let len = str.length; for(let i = 0; i <= len - 1; i++) { result+= nums[str[i]]; // 数字转换 if (i < len -1) { // 最后一位是每一组的各位,之前的每一位都要加上对应的计数单位 +result += units[len - i - 2] || ''; } } return result; } ...

补充了具体的函数实现后调试可以得出一下结果:

transform(4003); => ['四千零百零十三'] transform(403); => ['四百零十三'] transform(4300); => ['四千三百零十零'] transform(103000); => ['一十零万', '三千零百零十零'] transform(100303000); => ['一亿', '零千零百三十零万', '三千零百零十零'] transform(1303101000); => ['一十三亿', '零千三百一十零万', '一千零百零十零']

可以看到,输出的结果与目标更加接近了。我们再将一些边界case处理好,就能实现数字对中文的转换。

... const trans = (str) => { let result = ''; let len = str.length; let zeroFlag = false; for(let i = 0; i <= len - 1; i++) { if (parseInt(str[i], 10) === 0) { // 如果数字为0,标记0,进入下一轮循环 zeroFlag = true; } else { if (zeroFlag) { // 如果本轮数字不为0,上轮标记为0,则转换数字,重置标记 +result += nums[0]; +zeroFlag = false; } result+= nums[str[i]]; // 数字转换 if (i < len -1) { // 最后一位是每一组的个位,之前的每一位都要加上对应的计数单位 +result += units[len - i - 2] || ''; } } } return result; } ...

再看一下输出的结果

transform(4003); => ['四千零三'] transform(403); => ['四百零三'] transform(4300); => ['四千三百'] transform(103000); => ['一十万', '三千'] transform(100303000); => ['一亿', '零三十万', '三千'] transform(1303101000); => ['一十三亿', '零三百一十万', '一千']

最后将数组输出为字符串即可。

双指针法

比较推荐的解法是双指针解法,网上C语言版本的实现比较多。具体实现如下:

#include<iostream> #include<string> #include<algorithm> using namespace std; /* 题意:将一个整数按照中文读法,输出其拼音 如: 输入 -123456789 输出 Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu 刚开始看是真的没思路,不晓得咋么去模拟,后面看算法笔记才晓得每个整数可以 从低位开始每四个一组(每组称为节,即个节,万节,亿节),大单位分别是"个(实际不说出来)"、 “万”、“亿”,每组内的数字又有小单位“千”、“百”、“十”、“个(实际不说出来)”。 明确了输出的规则如下: 1、如果数字的某节(例如个节,万节,亿节) 中,某个非零位(千位除外)的高位是零,那么在 需要在该非零位的发音前额外输出一个零。例如8080(ba qian ling ba shi)、8008(ba qian ling ba) 、10808(yi wan ling ba bai ling ba) 2、每节的末尾需要输出万或者亿(个节除外) 注意: 需要注意特判输入是0的时候直接输出ling */ string num[10]={"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"}; string wei[3]={"Shi","Bai","Qian"}; string jie[2]={"Wan","Yi"}; int main(){ string str; cin>>str; int len=str.size(); int left=0,right=len-1; if(str[left]=='-'){ printf("Fu"); left++; } //前导零 while(str[left]=='0'&&left<len){ left++; } //特判输入是0的情况 if(left==len){ cout<<"ling"<<endl; return 0; } while(left+4<=right){//将left和right分别指向第一节的最高位和最低位 right-=4; } while(left<len){//依次判断每一节中(四位或者小于四位) bool isZero=false,isPrint=false;//isZero==false表示没有零 ,isPrint表示该节没有输出过其他的位(则相应不需要输出Wan或者Yi) while(left<=right){//遍历每一节中的每一位 if(str[left]=='0') isZero=true; else{//当前位不为0 if(isZero){//高位存在0 cout<<" ling"; isZero=false; } if(left>0)cout<<" ";//只要不是首位,后面每一位输出之前都要输出空格 cout<<num[str[left]-'0'];//输出当前位的数字 isPrint=true;//说明本节至少输出过一位 if(left!=right){ //除本节的个位以外,都需要输出十百千 cout<<" "<<wei[right-left-1]; } } left++; } if(isPrint&&right!=len-1){//只要不是个节,则相应输出Wan或者Yi cout<<" "<<jie[(len-1-right)/4-1]; } right+=4;//输出下一节 } return 0; }

按照这个思路,我用JavaScript也实现了一遍。

function transform(num) { let nums = ['零','一','二','三','四','五','六','七','八','九'] let units = ['十','百','千', '万', '亿']; let result = ''; num = (num + ''); let len = num.length; let left = 0; let right = len - 1; if (num[0] === '-1') { result += '负'; left++; } while (left + 4 <= right) { right -= 4; } while (left < len) { let zeroFlag = false; let isPrint = false; while(left <= right) { if (left > 0 && num[left] == 0) { // 遇到0时,设置zeroFlag 为true,指针往后移动一位 zeroFlag = true; } else { if (zeroFlag) { result += nums[0]; //补零 zeroFlag = false; } result += nums[num[left]]; isPrint = true; // 每一组中存在至少一个不为0的数字 if (left !== right) { // 补充每一位的单位 result += units[right - left - 1]; } } left++; } // 一轮结束时,如果存在至少一个不为0的数字 添加单位 if (isPrint && right !== len -1) { result += units[(len - 1 - right) / 4 + 2]; } right += 4; } console.log('result: ', result); return 0; } // 4003 四千零三 // 403 四百零三 // 4300 四千三百 // 103000 十万零三千 // 100303000 一亿零三十万三千 // 1303101000 十三亿零三百一十万一千 transform(4003); transform(403); transform(4300); transform(103000); transform(100303000); transform(1303101000);

一行实现

同事何米酥甚至用一行代码就搞定了

const trans = (str) => String(str).split(/(?=(?:\d{4})+(?!\d))/g).map((chunk, i, chunkArr) => chunk.split('').reduce(([flag, isPrint, print], c, ii, singleArr) => [!!i && (c === '0'), !!(isPrint || (c - '0')), c === '0' ? print : print + (flag ? '零' : '') + ['零', '一', '二', '三', '四', '五', '六', '七', '八', '九'][c] + ['', '十', '百', '千'][singleArr.length - 1 - ii]], [false, false, ''])[2] + (i !== chunkArr.length - 1 ? ['千', '万', '亿'][chunkArr.length - 1 - i] : '')).join('')

结束语

这个题目的关键在于找到数字转换的规律,按照四位一组的方式处理。