KK's blog

每天积累多一些

0%

LeetCode 273 Integer to English Words

Posted on Edited on Disqus:

LeetCode 273 Integer to English Words

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

Example 1:

**Input:** 123
**Output:** "One Hundred Twenty Three"

Example 2:

**Input:** 12345
**Output:** "Twelve Thousand Three Hundred Forty Five"

Example 3:

**Input:** 1234567
**Output:** "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

**Input:** 1234567891
**Output:** "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

题目大意：

这是将非负整数转化为其英文单词表示。给定输入确保小于 2 ^ 31 - 1

解题思路(推荐)：

第二种方法是按千位递归的。下面的方法是按20以下，100以下，百位，千位…递归，递归的颗粒度更小，程序更简单。

注意事项：

  1. 在入口方法中，若num为0，则返回Zero，要单独列出。
  2. 在递归中，num为0要单独列出，因为0表示此位不存在，可以记在dict中或返回空字符串。
  3. strip来去掉空格。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
NUM_DICT = {
    0: '',
    1: 'One',
    2: 'Two',
    3: 'Three',
    4: 'Four',
    5: 'Five',
    6: 'Six',
    7: 'Seven',
    8: 'Eight',
    9: 'Nine',
    10: 'Ten',
    11: 'Eleven',
    12: 'Twelve',
    13: 'Thirteen',
    14: 'Fourteen',
    15: 'Fifteen',
    16: 'Sixteen',
    17: 'Seventeen',
    18: 'Eighteen',
    19: 'Nineteen',
    20: 'Twenty',
    30: 'Thirty',
    40: 'Forty',
    50: 'Fifty',
    60: 'Sixty',
    70: 'Seventy',
    80: 'Eighty',
    90: 'Ninety',
}
class Solution(TestCases):

    def numberToWords(self, num: int) -> str:
        if num == 0:
            return 'Zero'
        return self.dfs(num)

    def dfs(self, num: int) -> str:
        if num < 20:
            return NUM_DICT[num]
        elif num < 100:
            return (NUM_DICT[num // 10 * 10] + ' ' + self.dfs(num % 10)).strip()
        elif num < 1000:
            return (NUM_DICT[num // 100] + ' Hundred ' + self.dfs(num % 100)).strip()
        elif num < 1000000:
            return (self.dfs(num // 1000) + ' Thousand ' + self.dfs(num % 1000)).strip()
        elif num < 1000000000:
            return (self.dfs(num // 1000000) + ' Million ' + self.dfs(num % 1000000)).strip()
        elif num < 1000000000000:
            return (self.dfs(num // 1000000000) + ' Billion ' + self.dfs(num % 1000000000)).strip()
        return ''

注意事项：

  1. 空格总加在新数前面，只需要加在有返回值的时候，也就是tens和lows中，其他如numberToWordsR(number/1000)
    可能返回空值，此时不在前面加空格。
  2. 在递归中，num为0要单独列出，因为0表示此位不存在，也就是无返回值。
  3. 在入口方法中，若num为0，则返回Zero，要单独列出。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String numberToWords(int number) {
	if (number == 0)
		return "Zero";
	
	return numberToWordsR(number).trim();
}

public String numberToWordsR(int number) {
	if(number == 0) {
		return "";
	} else if (number < 20) {
		return " " + lows[number];
	} else if (number < 100) {
		return " " + tens[number / 10] + numberToWordsR(number % 10);
	} else if (number < 1000) {
		return " " + lows[number / 100] + " Hundred" + numberToWordsR(number % 100);
	} else if (number < 1000000) {
		return numberToWordsR(number / 1000) + " Thousand" + numberToWordsR(number % 1000);
	} else if (number < 1000000000) {
		return numberToWordsR(number / 1000000) + " Million" + numberToWordsR(number % 1000000);
	} else {
		return numberToWordsR(number / 1000000000) + " Billion" + numberToWordsR(number % 1000000000);
	}
}

算法II每三位解题思路：

这是logical and maintainable的经典题。按照英语的习惯，每三位是一组，所以实现的时候，也是按千为分组，有一个方法去处理一千
内的数。一千以内也分为三种情况，20以内，几十，其他。20以内和几十都是特殊情况的单词，所以可以放入数组或HashMap，数组比较
好，因为可以直接用索引读出。大于一千的数，可以用递归来做，从人的习惯，从低位到高位，每三位加一个逗号分隔。所以同样，算法
也是从低位开始，若千位内的数大于0，加入Thousand, Million等，每三位调用千位方法，再递归。
group的引入作为递归的层次来决定Thousand还是Million。
由于从低位递归，所以倒着做，要reverse地加入到结果，最终结果再reverse回来。

注意事项：

  1. 空格总加在新数前面，也就是append前先加空格
  2. 低3位大于0才加Thousand, Million等词，也就是低三位在1-999之间，若为0如1 million。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public String[] lows = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
   "Eleven", "Twelve","Thirteen", "Fourteen","Fifteen","Sixteen","Seventeen","Eighteen", "Nineteen"};

public String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

public String numberToWords(int number) {
	if(number == 0) {
		return "Zero";	
	}

	StringBuilder result = new StringBuilder();

	translateThreeR(number, result, 0);
	return result.reverse().toString().trim();
}

public void translateThreeR(int number, StringBuilder result, int group) {
	int lower = number % 1000;
	int thousands = number / 1000;     

	if (group == 1 && lower > 0)
		result.append(reverse(" Thousand"));
	else if (group==2 && lower > 0)
		result.append(reverse(" Million"));
	else if (group==3 && lower > 0)
		result.append(reverse(" Billion"));
	
	if(lower>0)
		result.append(reverse(translateThree(lower)));
	
	if(thousands >= 1) {
		translateThreeR(thousands, result, ++group);
	}

}

public String translateThree(int number) {
	StringBuilder result = new StringBuilder();
	if(number > 99) {
		result.append(" "+lows[number / 100]);
		result.append(" Hundred");
		number = number % 100;
	}

	if(number > 19) {
		result.append(" ");
		result.append(tens[number/10]);
		number = number % 10;
	}

	// Remainder is under 20
	result.append(" "+lows[number]);
	return " "+result.toString().trim();
}

public String reverse(String s) {
	return (new StringBuilder()).append(s).reverse().toString();
}

算法分析：

n为位数，时间复杂度为O(n)，空间复杂度O(1)。

Follow-up：

integer, minus, decimals, internationlization(localization)。

Free mock interview