从英文中重建数字

Posted on Edited on In Views: Waline: Symbols count in article: 280 Reading time ≈ 1 mins.

题解方法

  • 词频统计
  • 哈希

词频统计

  • 统计每个字母分别在哪些数字中出现：
字母 数字
e 0 1 3 5 7 8 9
f 4 5
g 8
h 3 8
i 5 6 8 9
n 1 7 9
o 0 1 2 4
r 0 3 4
s 6 7
t 2 3 8
u 4
v 5 7
w 2
x 6
z 0
  • 第一轮确定 0、2、4、6、8
  • 第二轮确定 3、5、7
  • 第三轮确定 1、9
  • n 在 9 中出现了 2 次，e 在 3 中出现了 3 次

哈希

  • 根据词频统计结果依次进行哈希查找

核心代码

词频统计

1
2
3
for (int i = 0; i < s.length(); i++) {
    cnt[s.charAt(i) - 'a']++;
}

哈希

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
int[] digits = new int[10];
// Z
digits[0] = cnt[25];
cnt[14] -= cnt[25];
// W
digits[2] = cnt[22];
cnt[14] -= cnt[22];
// U
digits[4] = cnt[20];
cnt[5] -= cnt[20];
cnt[14] -= cnt[20];
// X
digits[6] = cnt[23];
cnt[18] -= cnt[23];
cnt[8] -= cnt[23];
// G
digits[8] = cnt[6];
cnt[7] -= cnt[6];
cnt[8] -= cnt[6];
// H
digits[3] = cnt[7];
// F
digits[5] = cnt[5];
cnt[8] -= cnt[5];
// S
digits[7] = cnt[18];
// O
digits[1] = cnt[14];
// I
digits[9] = cnt[8];

题目来源

423. 从英文中重建数字 - 力扣（LeetCode） (leetcode-cn.com)