leetcode
leetcode 351 ~ 400
从英文中重建数字

从英文中重建数字

难度:

标签:

题目描述

给你一个字符串 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'等字母来首先确定数字的个数,它们有什么特殊性吗?
选择'z', 'w', 'u', 'x', 'g'等字母来首先确定数字的个数是因为这些字母在英文单词中表示数字的拼写中是唯一的。例如,'z'只在'zero'中出现,'w'只在'two'中出现,这样的特性使得它们可以直接确定对应数字的个数,无需考虑其他数字的影响。这种方法提高了算法的效率和准确性。
🦆
在步骤中减去其他数字的数量(例如'nums[7] = s.count('s') - nums[6]'),这样的操作是否总是准确的?存在误差的可能性吗?
这样的操作是准确的,不存在误差的可能性。这是因为在确定某些数字的数量时,考虑到一些字母可能同时出现在多个数字的拼写中。例如,'s'既出现在'seven'也出现在'six'中,因此在计算'nums[7]'时需要减去已经确定的'nums[6]'(即'six'的数量)。这种方法确保了每个数字只被计算一次,避免了重复计算。
🦆
如何保证在减法操作后得到的数字个数(例如'nums[1] = s.count('o') - nums[0] - nums[2] - nums[4]')不会是负数?
在实际操作中,减法操作后得到的数字个数不会是负数,因为在执行减法前,已经保证了减数(即'nums[0]', 'nums[2]', 'nums[4]'等)是准确无误的。这些数字的个数是基于独特字母的统计得出的,因此在从总数中减去这些数字的个数时,剩余的数量必然是非负的,这保证了计算的逻辑正确性。
🦆
对于计算数字9的个数,为何要减去'nums[5]', 'nums[6]', 和 'nums[8]'?这是基于哪些字母的共同出现考虑的?
计算数字9的个数时需要减去'nums[5]', 'nums[6]', 'nums[8]',因为字母'i'出现在'five', 'six', 'eight'和'nine'的拼写中。已经确定的'five', 'six', 和 'eight'的数量中包含了一部分'i'的使用,所以在计算'nine'的数量时,必须减去这些数字中包含的'i'的数量,以确保得到准确的'nine'的个数。这种方法是基于字母'i'在多个数字拼写中共同出现的情况考虑的。

相关问题