美文网首页
273. Integer to English Words

273. Integer to English Words

作者: RobotBerry | 来源:发表于2017-05-08 10:59 被阅读0次

    问题

    Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

    例子

    123 -> "One Hundred Twenty Three"
    12345 -> "Twelve Thousand Three Hundred Forty Five"
    1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

    分析

    int的最大值为2147483647,所以一个int最多可以被表示成X Billion X Million X Thousand X,其中X部分又可以被表示成Y Hundred Z. 所以解决问题的关键是把数字切割成若干部分,每一部分都可以被简单地表示出来。

    要点

    • 映射表
    • 分类讨论

    时间复杂度

    O(n), n为数字位数

    空间复杂度

    O(1)

    代码

    class Solution {
    public:
        string numberToWords(int num) {
            if (num == 0) return string("Zero");
            string res;
            for (int i = 3; i >= 0; i--) {
                int div = pow(1000, i);
                int n = (num - num % div) / div;
                if (n != 0) {
                    res += toStr000(n) + " ";
                    if (num >= 1000)
                        res += str00[i] + " ";
                }
                num %= div;
            }
            res.pop_back();
            return res;
        }
    
    private:
        string toStr000(int num) {
            string res;
            int n = num / 100;
            if (n != 0)
                res += str1[n] + " " + str00[0] + " ";
            num %= 100;
            n = num / 10;
            int d = num % 10;
            if (n != 0) {
                if (n == 1) res += str1x[d] + " ";
                else res += strx0[n - 2] + " ";
            }
            if (n != 1 && d != 0)
                res += str1[d] + " ";
            res.pop_back();
            return res;
        }
    
        vector<string> str1{ "Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" };
        vector<string> str1x{ "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" };
        vector<string> strx0{ "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };
        vector<string> str00{ "Hundred", "Thousand", "Million", "Billion" };
    };
    

    more concise

    class Solution {
     public:
        string digits[20] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        string tens[10] = {"Zero", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
        string int2string(int n) {
            if (n >= 1000000000) {
                return int2string(n / 1000000000) + " Billion" + int2string(n % 1000000000);
            } else if (n >= 1000000) {
                return int2string(n / 1000000) + " Million" + int2string(n % 1000000);
            } else if (n >= 1000) {
                return int2string(n / 1000) + " Thousand" + int2string(n % 1000);
            } else if (n >= 100) {
                return int2string(n / 100) + " Hundred" + int2string(n % 100);
            } else if (n >= 20) {
                return  " " + tens[n / 10] + int2string(n % 10);
            } else if (n >= 1) {
                return " " + digits[n];
            } else {
                return "";
            }
        }
    
        string numberToWords(int num) {
            if (num == 0) {
                return "Zero";
            } else {
                string ret = int2string(num);
                return std::move(ret.begin()+1, ret.end(), std::back_inserter(result));
            }
        }
    };
    

    相关文章

      网友评论

          本文标题:273. Integer to English Words

          本文链接:https://www.haomeiwen.com/subject/hpdmtxtx.html