LeetCode 刷题笔记： 273.整数的英语表示-灵析社区
时光小少年1. 原题链接
2. 题意
将非负整数 num 转换为其对应的英文表示。
3. 示例
示例 1：
输入：num = 123
输出："One Hundred Twenty Three"
示例 2：
输入：num = 12345
输出："Twelve Thousand Three Hundred Forty Five"
示例 3：
输入：num = 1234567
输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
4. 分析
4.1. 方法一：迭代法求解
使用迭代的方式得到每一组的英文表示。由于每一组最多有 333 位数，因此依次得到百位、十位、个位上的数字，生成该组的英文表示，注意只有非零位才会被添加到英文表示中。
4.1.1. 迭代法代码
class Solution {
//个位数定义 0 - 9
String[] singles = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
// 二位数定义 10 - 19
String[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
// 十位数定义 10、20、30 ······ 90
String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
// 百位数定义
String[] thousands = {"", "Thousand", "Million", "Billion"};
public String numberToWords(int num) {
if(num == 0){
return singles[0];
}
StringBuffer sb = new StringBuffer();
for (int i = 3, unit = 1000000000; i >= 0; i--, unit /= 1000) {
int curNum = num / unit;
if (curNum != 0) {
num -= curNum * unit;
sb.append(toEnglish(curNum)).append(thousands[i]).append(" ");
}
}
return sb.toString().trim();
}
public String toEnglish(int num) {
StringBuffer curr = new StringBuffer();
int hundred = num / 100;
num %= 100;
if (hundred != 0) {
curr.append(singles[hundred]).append(" Hundred ");
}
int ten = num / 10;
if (ten >= 2) {
curr.append(tens[ten]).append(" ");
num %= 10;
}
if (num > 0 && num < 10) {
curr.append(singles[num]).append(" ");
} else if (num >= 10) {
curr.append(teens[num - 10]).append(" ");
}
return curr.toString();
}
}
4.1.2. 复杂度分析
- 时间复杂度：O(1)
- 空间复杂度：O(1)
4.2. 方法二 : 递归分析
由于非负整数 num 的最大值为 的最大值为
，因此最多有 10 位数。将整数转换成英文表示中，将数字按照 3 位一组划分，将每一组的英文表示拼接之后即可得到整数 num 的英文表示。
每一组最多有 3 位数，可以使用递归的方式得到每一组的英文表示。根据数字所在的范围，具体做法如下：
- 小于 20 的数可以直接得到其英文表示；
- 大于等于 20 且小于 100 的数首先将十位转换成英文表示，然后对个位递归地转换成英文表示；
- 大于等于100 的数首先将百位转换成英文表示，，然后对其余部分（十位和个位）递归地转换成英文表示。
从高到低的每一组的单位依次是 ，每一组都有对应的表示单位的词，分别是
得到每一组的英文表示后，需要对每一组加上对应的表示单位的词，然后拼接得到整数 num 的英文表示。
具体实现中需要注意以下两点：
- 只有非零的组的英文表示才会拼接到整数 num 的英文表示中；
- 如果 num = 0,则不适用上述做法，而是直接返回 “Zero"。
4.2.1. 递归法代码
class Solution {
String[] singles = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
String[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
String[] thousands = {"", "Thousand", "Million", "Billion"};
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
StringBuffer sb = new StringBuffer();
for (int i = 3, unit = 1000000000; i >= 0; i--, unit /= 1000) {
int curNum = num / unit;
if (curNum != 0) {
num -= curNum * unit;
StringBuffer curr = new StringBuffer();
recursion(curr, curNum);
curr.append(thousands[i]).append(" ");
sb.append(curr);
}
}
return sb.toString().trim();
}
public void recursion(StringBuffer curr, int num) {
if (num == 0) {
return;
} else if (num < 10) {
curr.append(singles[num]).append(" ");
} else if (num < 20) {
curr.append(teens[num - 10]).append(" ");
} else if (num < 100) {
curr.append(tens[num / 10]).append(" ");
recursion(curr, num % 10);
} else {
curr.append(singles[num / 100]).append(" Hundred ");
recursion(curr, num % 100);
}
}
}
4.2.2. 复杂度分析
- 时间复杂度：O(1)。非负整数 nums 按照 3 位一组划分最多有 4 组，分别得到每一组的英文表示，然后拼接得到整数 num 的英文表示，时间复杂度是常数。
- 空间复杂度：O(1)。空间复杂度主要取决于存储英文表示的字符串和递归调用栈，英文表示的长度可以看成常数，递归调用栈不会超过 3 层。
阅读量：741
点赞量：0
收藏量:0