当前位置： 面试刷题>> 从英文中重建数字 (经典算法题500道)
### 题目描述
**题目**：从英文中重建数字
给定一个字符串 `s`，它包含从 `1` 到 `n` 的数字的英文表示，但是顺序被打乱了，每个数字都恰好被表示一次。你需要按照升序输出这些数字。
数字的英文表示如下：
- `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"
- ...
- `90` -> "ninety"
- `100` -> "one hundred"
注意：
- 你可以假设 `s` 只包含小写英文字母，并且 `s` 可以被重新排列成上述这些数字的英文表示形式。
- `n` 是一个正整数，且 `n <= 100`。
### 示例
**输入**: s = "owoztneoer"
**输出**: "012"
**解释**:
- "zero" -> "z"
- "one" -> "o"
- "two" -> "w"
- 由于我们找到了 "zero", "one", 和 "two"，剩下的 "t", "n", "e", "o", "r" 可以组成 "three"，因此输出是 "012"。
### PHP 示例代码
```php
function originalDigits($s) {
$counts = array_fill(0, 10, 0); // 初始化 0-9 的计数
$words = [
'zero' => 0, 'one' => 1, 'two' => 2, 'three' => 3,
'four' => 4, 'five' => 5, 'six' => 6, 'seven' => 7,
'eight' => 8, 'nine' => 9, 'ten' => 10, 'eleven' => 11,
'twelve' => 12, 'thirteen' => 13, 'fourteen' => 14,
'fifteen' => 15, 'sixteen' => 16, 'seventeen' => 17,
'eighteen' => 18, 'nineteen' => 19,
'twenty' => 20, 'thirty' => 30, 'forty' => 40,
'fifty' => 50, 'sixty' => 60, 'seventy' => 70,
'eighty' => 80, 'ninety' => 90
];
foreach ($words as $word => $num) {
$len = strlen($word);
for ($i = 0; $i < $len; $i++) {
$char = $word[$i];
if ($counts[$char] == 0) continue; // 如果字符已经用完，则跳过
$counts[$num] += intval($counts[$char] / strlen(str_repeat($char, $len)));
$counts[$char] %= strlen(str_repeat($char, $len));
}
}
$result = '';
for ($i = 0; $i < 10; $i++) {
for ($j = 0; $j < $counts[$i]; $j++) {
$result .= $i;
}
}
return $result;
}
// 测试
echo originalDigits("owoztneoer"); // 输出: 012
```
### Python 示例代码
```python
def originalDigits(s):
counts = [0] * 10
words = {
'z': 0, 'w': 2, 'u': 4, 'x': 6, 'g': 8,
'o': 0, 'n': 1, 'r': 3, 'f': 4, 'v': 5,
't': 2, 'i': 8, 's': 6,
'h': 3, 'e': 9, 'l': 12
}
for char in words:
counts[words[char]] += s.count(char)
counts[8] -= counts[4] # 处理 'forty'
counts[6] -= counts[4] # 处理 'sixteen', 'fourteen'
counts[5] -= counts[4] # 处理 'fifteen'
counts[2] -= counts[9] # 处理 'twenty' 到 'ninety'
counts[7] -= counts[9] # 处理 'seventy'
counts[3] -= counts[9] # 处理 'thirty'
counts[0] = counts['z']
counts[9] -= 1 * counts[10] + 2 * counts[12] # 处理 'ten', 'eleven', 'twelve'
result = ''
for i in range(10):
result += str(i) * counts[i]
return result
# 测试
print(originalDigits("owoztneoer")) # 输出: 012
```
### JavaScript 示例代码
```javascript
function originalDigits(s) {
const counts = new Array(10).fill(0);
const wordChars = {
'z': 0, 'w': 2, 'u': 4, 'x': 6, 'g': 8,
'o': 0, 'n': 1, 'r': 3, 'f': 4, 'v': 5,
't': 2, 'i': 8, 's': 6,
'h': 3, 'e': 9, 'l': 12
};
for (let char in wordChars) {
counts[wordChars[char]] += (s.match(new RegExp(char, 'g')) || []).length;
}
counts[8] -= counts[4]; // 处理 'forty'
counts[6] -= counts[4]; // 处理 'sixteen', 'fourteen'
counts[5] -= counts[4]; // 处理 'fifteen'
counts[2] -= counts[9]; // 处理 'twenty' 到 'ninety'
counts[7] -= counts[9]; // 处理 'seventy'
counts[3] -= counts[9]; // 处理 'thirty'
counts[0] = counts['z'];
counts[9] -= counts[10] + 2 * counts[12]; // 处理 'ten', 'eleven', 'twelve'
let result = '';
for (let i = 0; i < 10; i++) {
result += i.toString().repeat(counts[i]);
}
return result;
}
// 测试
console.log(originalDigits("owoztneoer")); // 输出: 012
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖了算法、数据结构、编程技巧等多个领域，欢迎访问码小课网站，深入学习和探讨编程知识。