Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123 Output: "One Hundred Twenty Three"
Example 2:
Input: num = 12345 Output: "Twelve Thousand Three Hundred Forty Five"
Example 3:
Input: num = 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Example 4:
Input: num = 1234567891 Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"
Constraints:
0 <= num <= 231 - 1
整数转换英文表示。
这个题目不涉及任何算法，是一道单纯的实现题。需要设计一个helper函数，判断如下几个条件
num是否等于0
num是否小于20
num是否小于100
num % 1000是否等于0 - 为什么是%1000是因为input最大只会有10个digit，最大的数字只会是到billion，是由1000表达法来的，这也是英文数字的特点，每三位就一定会有一个单词（hundred, thousand, million, billion）
细节方面，首先需要创建几个string array，以方便输出一些单词。接着判断这个数字num % 1000是否为0，这是因为英语里面数字的读法都是每三位一个单词，所以每次%1000就会知道到底是thousand、million还是billion（这是伴随着i++而记录的）。则输出里面一定包含thousand那一组里面的词，接着再除以1000，递归处理之后的数字；num被处理到小于1000之后，这里又分另外几种情况，
如果数字小于20，直接在less20里面找对应的数字
如果20 <= num < 100，在tens里面找num / 10然后helper递归找num % 10
如果num >= 100，在less20里面找一个单词跟hundred拼接，再递归找num % 100
跑一个例子，12345 -> "Twelve Thousand Three Hundred Forty Five"
首先在line13，12345 % 1000 = 345 != 0，则res = helper(num % 1000) + thousands[i] + " " + res; => res = helper(345) + "" + " " + res;
此时num = num / 1000 = 12, i = 1；此时掉入helper函数的递归，又因为num = 345所以是会掉入line 31的if语句，所以会在less20里面找到less20[345 / 100] = less20[3] = Three + " Hundred " + helper(345 % 100) => "Three Hundred " + helper(45) => "Three Hundred " + tens[45 / 10] + " " + helper(45 % 10) => "Three Hundred " + "Forty" + " " + helper(5) => "Three Hundred " + "Forty" + " " + "Five"。
完成了345的部分之后，helper函数会回溯，此时因为num = num / 1000 = 12, i = 1的关系所以helper函数判断会掉入27行得到前面的"Twelve Thousand"，再 + res得到最后的结果"Twelve Thousand Three Hundred Forty Five"。
时间O(n)
空间O(1) - 只有3个额外的数组
Java实现
1 class Solution { 2 String[] less20 = { "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", 3 "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" }; 4 String[] tens = { "", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" }; 5 String[] thousands = { "", "Thousand", "Million", "Billion" }; 6 7 public String numberToWords(int num) { 8 // corner case 9 if (num == 0) 10 return "Zero"; 11 String res = ""; 12 int i = 0; 13 while (num > 0) { 14 if (num % 1000 != 0) { 15 res = helper(num % 1000) + thousands[i] + " " + res; 16 } 17 num /= 1000; 18 i++; 19 } 20 return res.trim(); 21 } 22 23 public String helper(int num) { 24 if (num == 0) 25 return ""; 26 if (num < 20) { 27 return less20[num % 20] + " "; 28 } else if (num < 100) { 29 return tens[num / 10] + " " + helper(num % 10); 30 } else { 31 return less20[num / 100] + " Hundred " + helper(num % 100); 32 } 33 } 34 }