X

Leetcode 273. Integer to English Words 解题思路分析

题目描述:

整数转换英文表示

将非负整数转换为其对应的英文表示。可以保证给定输入小于 231 – 1 。

示例 1:

输入: 123
输出: "One Hundred Twenty Three"

示例 2:

输入: 12345
输出: "Twelve Thousand Three Hundred Forty Five"

示例 3:

输入: 1234567
输出: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

示例 4:

输入: 1234567891
输出: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=273

解题思路分析:

这道题难度不大,关键是要把数字分成几种来看,

  1. 数字小于等于20
  2. 所有整十的数字,比如20,30,90
  3. 千,百万和十亿

因为英文单词的规律,20以下的单词都是固定无规律的。然后就是整十的数字,虽然有一定规律,但是有一些个别的奇葩导致无法用程序统一。最后就是注意一下英文的数字单位,英文不像中文,个十百千万单位那么全,英文中只有百,千,百万和十亿,除去百这个单位,其他的都是每三位数字一个单位,这样问题就变得稍微简单一些,如果我们能把数字从个位开始每三位翻译一下,然后再根据这三位所在的位置加上千,百万和十亿这些单位就可以了。

另外需要注意几个细节:

第一,分割数字时可以先把数字转成字符串再分割,但效率不高,因此不推荐。我们的原则是,能用int解决的问题尽量不要麻烦String。那具体怎么实现呢?

while (num > 0) {
    // 当前数字与1000的余数,就是数字的最后三位
 int index3 = num % 1000;
    // 将当前数字除以1000继续循环,可以得到之前三位
 num = num / 1000;
}

第二,是否需要添加 千,百万 这些单位时需要留意。如果该单位的数值是0的话则不需要添加。比如100万整,我们不能写成One Million Thousand

第三,关于空格也要注意,这在代码中详细解释。

第四,关于小于20,整十和单位级的英文单词我们可以写到一个数组或是Map中,但是查询效率会影响代码执行速度,所以推荐使用常量。

最后看看完整代码:

public String numberToWords(int num) {
    // 数字0直接返回"Zero"
    if (num == 0) {
        return "Zero";
    }
    // 定义一个返回结果
    String res = "";
    // 这个level是定义单位级的,包括千,百万和十亿
    int level = 0;
    // 将数字从末尾每三位分成一组来翻译
    while (num > 0) {
        // 取得数字后三位
        int index3 = num % 1000;
        // 取得这三位的英文翻译
        String temp = getStringFromNum(index3);
        // 当单位级的位数是3,6,9时,并且当前三位不为0时,添加单位
        if (level > 0 && level % 3 == 0 && index3 > 0) {
            temp = temp + " " + getLevelString(level);
        }
        // 如果当前三位的英文翻译不为空,那么我们将其加入返回结果
        if (!"".equals(temp)) {
            // 这里需要注意一下空格问题,如果返回结果res不为空
            // 那么当前三位的英文翻译要与之前的res之间添加一个空格
            res = temp + ("".equals(res) ? "" : " " + res);
        }
        // 当前数字除以1000继续循环
        num = num / 1000;
        // 单位级加3
        level += 3;
    }
    return res;
}
// 这个方法是取得3位或3位以下数字的英文翻译
private String getStringFromNum(int n) {
    if (n <= 20) {
        // 当n小于20时,直接返回该数字对应的英文常量
        return getStringUnder100(n);
    } else if (n < 100) {
        // 当n大于20并小于100时,index1代表该数字的个位
        int index1 = n % 10;
        // index2代表该数字的十位加上一个0,比如30,40,90
        int index2 = n - index1;
        // 取得index2对应的英文常量 加上 个位index1对应的英文常量
        // 这里同样要注意空格问题,如果个位为0,那么十位与各位之间不要加空格
        return getStringUnder100(index2) + (index1 == 0 ? "" : " " + getStringUnder100(index1));
    } else if (n < 1000) {
        // 当n大于等于100并小于1000时,index2代表该数字的十位与个位两位数
        int index2 = n % 100;
        // index3 为百位数
        int index3 = n / 100;
        // 返回结果为百位数对应的英文常量加上" Hundred"再加上空格和后两位的英文翻译
        // 这里同样需要注意空格问题,后两位可能会为空
        // 获取后两位的英文翻译时用到了递归方法
        return getStringUnder100(index3) + " Hundred" + (index2 == 0 ? "" : " " + getStringFromNum(index2));
    }
    return "";
}
// 单位级对应的英文单词常量
private String getLevelString(int l) {
    switch (l) {
    case 3:
        return "Thousand";
    case 6:
        return "Million";
    case 9:
        return "Billion";
    }
    return "";
}
// 小于20以及整十数字对应的英文单词常量
private String getStringUnder100(int n) {
    switch (n) {
    case 1:
        return "One";
    case 2:
        return "Two";
    case 3:
        return "Three";
    case 4:
        return "Four";
    case 5:
        return "Five";
    case 6:
        return "Six";
    case 7:
        return "Seven";
    case 8:
        return "Eight";
    case 9:
        return "Nine";
    case 10:
        return "Ten";
    case 11:
        return "Eleven";
    case 12:
        return "Twelve";
    case 13:
        return "Thirteen";
    case 14:
        return "Fourteen";
    case 15:
        return "Fifteen";
    case 16:
        return "Sixteen";
    case 17:
        return "Seventeen";
    case 18:
        return "Eighteen";
    case 19:
        return "Nineteen";
    case 20:
        return "Twenty";
    case 30:
        return "Thirty";
    case 40:
        return "Forty";
    case 50:
        return "Fifty";
    case 60:
        return "Sixty";
    case 70:
        return "Seventy";
    case 80:
        return "Eighty";
    case 90:
        return "Ninety";
    }
    return "";
}

本解法的程序执行时间为1ms

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-273-integer-to-english-words-解题思路分析/
Categories: leetcode
admin: