从英文中重建数字
难度:
标签:
题目描述
给你一个字符串 s
,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9
)。按 升序 返回原始的数字。
示例 1:
输入:s = "owoztneoer" 输出:"012"
示例 2:
输入:s = "fviefuro" 输出:"45"
提示:
1 <= s.length <= 105
s[i]
为["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]
这些字符之一s
保证是一个符合题目要求的字符串
代码结果
运行时间: 34 ms, 内存: 16.2 MB
/*
题目思路:
1. 使用一个int数组count,大小为26,用于记录每个字母的频率。
2. 通过流操作对字符进行计数。
3. 按顺序处理数字的英文单词,从0到9。
- 每个数字的英文单词都有一个唯一的字符,例如'z'在'zero'中唯一出现,因此可以根据'z'的个数确定'zero'的数量。
- 每确定一个数字的数量后,减去相应数量的字符。
4. 根据找到的数字按升序输出。
*/
import java.util.stream.*;
public class Solution {
public String originalDigits(String s) {
int[] count = s.chars().map(c -> c - 'a').collect(() -> new int[26], (arr, i) -> arr[i]++, (arr1, arr2) -> {
for (int i = 0; i < arr1.length; i++) arr1[i] += arr2[i];
});
int[] numCount = new int[10];
numCount[0] = count['z' - 'a']; // zero
numCount[2] = count['w' - 'a']; // two
numCount[4] = count['u' - 'a']; // four
numCount[6] = count['x' - 'a']; // six
numCount[8] = count['g' - 'a']; // eight
numCount[1] = count['o' - 'a'] - numCount[0] - numCount[2] - numCount[4]; // one
numCount[3] = count['h' - 'a'] - numCount[8]; // three
numCount[5] = count['f' - 'a'] - numCount[4]; // five
numCount[7] = count['s' - 'a'] - numCount[6]; // seven
numCount[9] = count['i' - 'a'] - numCount[5] - numCount[6] - numCount[8]; // nine
return IntStream.range(0, 10)
.mapToObj(i -> String.valueOf(i).repeat(numCount[i]))
.collect(Collectors.joining());
}
}
解释
方法:
这个题解的思路是统计字符串中某些独特字母的出现次数,从而推断出对应数字的个数。具体来说:
1. 统计 'z' 的出现次数,推断出 'zero' 即数字 0 的个数
2. 统计 'w' 的出现次数,推断出 'two' 即数字 2 的个数
3. 统计 'u' 的出现次数,推断出 'four' 即数字 4 的个数
4. 统计 'x' 的出现次数,推断出 'six' 即数字 6 的个数
5. 统计 'g' 的出现次数,推断出 'eight' 即数字 8 的个数
6. 统计 's' 的出现次数,减去 'x'('six') 的个数,得到 'seven' 即数字 7 的个数
7. 统计 'f' 的出现次数,减去 'u'('four') 的个数,得到 'five' 即数字 5 的个数
8. 统计 'h' 的出现次数,减去 'g'('eight') 的个数,得到 'three' 即数字 3 的个数
9. 统计 'o' 的出现次数,减去 'z'('zero')、'w'('two')、'u'('four') 的个数,得到 'one' 即数字 1 的个数
10. 统计 'i' 的出现次数,减去 'f'('five')、'x'('six')、'g'('eight') 的个数,得到 'nine' 即数字 9 的个数
最后,按照数字从小到大的顺序,把统计得到的各个数字的个数转化为相应数量的数字字符,拼接成结果字符串返回。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择'z', 'w', 'u', 'x', 'g'等字母来首先确定数字的个数,它们有什么特殊性吗?
▷🦆
在步骤中减去其他数字的数量(例如'nums[7] = s.count('s') - nums[6]'),这样的操作是否总是准确的?存在误差的可能性吗?
▷🦆
如何保证在减法操作后得到的数字个数(例如'nums[1] = s.count('o') - nums[0] - nums[2] - nums[4]')不会是负数?
▷🦆
对于计算数字9的个数,为何要减去'nums[5]', 'nums[6]', 和 'nums[8]'?这是基于哪些字母的共同出现考虑的?
▷