神刀安全网

一道很老的面试题,算法很纠结


1 题目

将人民币的数字金额转化成大写金额,例如:

input : 012000500.4 output : 壹仟贰佰万伍佰圆肆角

人民币数字金额转成大写金额是一道很老的面试题了,我就曾经遇到过,写过java和javascript的实现方法,但总是纠结于实现算法不够理想,象是算法里有好多补丁。这道题主要考察观察总结和算法的设计能力,细节和边界的处理能力等,看起来并不太难,但要很完美实现也不容易,尤其是在纸上编程,更要求思路清晰和明确。

2 算法分析

  1. 处理待转换的字符串,去掉开头空格,补齐结尾角分位,得到 1200050040
  2. 设计数字对应中文数组 {"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"}
  3. 设计中文单位数组 {"分","角","圆","拾","佰","仟","万","拾","佰","仟","亿","拾","佰","仟","万","拾","佰","仟"}
  4. 循环input,逐位转化成中文和单位组合,得到 壹仟贰佰零拾零万零仟伍佰零拾零圆肆角零分
  5. 利用正则表达式,去掉零仟、零佰、零拾、零角、零分
  6. 利用正则表达式,替换零亿、零万、零圆、亿万 为 亿、万、圆、亿
  7. 结尾,结尾加上

3 java实现

public static String toUpper(String num) {     String[] nums = {"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"};     String[] units = {"分","角","圆","拾","佰","仟","万","拾","佰","仟","亿","拾","佰","仟","万","拾","佰","仟"};     StringBuilder result = new StringBuilder();     num = num.replaceAll("^[0]+","");     num += "00";     if(num.contains(".")) {         int index = num.indexOf(".");         num = num.substring(0,index)+ num.substring(index+1,index+3);     }     int len = num.length();     if(len > 18) {         throw new RuntimeException("数字太大,无法处理!");     }     for(int i = 0; i < len; i++) {         int c = num.charAt(i);         if(c >47 && c <58) {             result.append(nums[c - 48] + units[len - i -1]);         }     }     String str = result.toString();     str = str.replaceAll("(零仟)|(零佰)|(零拾)|(零角)|(零分)","");     str = str.replace("零亿","亿");     str = str.replace("零万","万");     str = str.replace("零圆","圆");     str = str.replace("亿万","亿");     if(str.endsWith("圆")) {         str += "整";     }     return str; }

4 javascript实现

function toUpper(num) {     var nums = "零壹贰叁肆伍陆柒捌玖".split("");     var units = "分角圆拾佰仟万拾佰仟亿拾佰仟万拾佰仟".split("");     var result = "";     num = num.replace(/^[0]/,"");     num += "00";     var index = num.indexOf(".");     if(index > -1) {         var index = num.indexOf(".");         num = num.substring(0,index)+ num.substring(index+1,index+3);     }     var len = num.length;     for(var i = 0; i < len; i++) {         var c = num.charAt(i);         if(c >= 0 && c < 10) {             result += (nums[c] + units[len - i -1]);         }     }     result = result.replace(/零仟|零佰|零拾|零角|零分/g,"");     result = result.replace("零亿","亿");     result = result.replace("零万","万");     result = result.replace("零圆","圆");     result = result.replace("亿万","亿");     if(result.charAt(result.length-1) == '圆') {         result += "整";     }     return result; }

5 补充

本来想写C语言的实现算法,没有时间写了,抱歉,算法经过基本的测试验证,可以最高处理千万亿级别的转换。

另外,总是觉得算法的实现还可以优化,还是本人太纠结了?大家帮助提一下建议,也可以帮忙给出C语言及其它语言的实现方法。

提供WEB版的转换小工具,供大家报销发票的时候使用。

人民币转换小工具

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 一道很老的面试题,算法很纠结

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址