一道很老的面试题了,总是对这道题的算法很纠结

Posted on 2017-04-12 by 毛三胖

摘要

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


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版的转换小工具,供大家报销发票的时候使用。

人民币转换小工具