题目描述
你被给定一个整数 n，执行以下步骤：
- 将
n 的每个数位转换为它的小写英文单词（例如 4 → "four", 1 → "one"）。
- 将那些单词按照 原始数字顺序 连接 起来形成一个字符串
s。
返回字符串 s 中出现 奇数 次的 不同 字符的数量。
示例 1：
输入：n = 41
输出：5
解释：
41 → "fourone"
出现奇数次的字母：'f'，'u'，'r'，'n'，'e'。因此，答案为 5。
示例 2：
输入：n = 20
输出：5
解释：
20 → "twozero"
出现奇数次的字母：'t'，'w'，'z'，'e'，'r'。因此，答案为 5。
提示：
解法
方法一：模拟 + 位运算
我们可以将每个数字转换为对应的英文单词，然后统计每个字母出现的次数。由于字母的数量有限，我们可以使用一个整数 \(\textit{mask}\) 来表示每个字母的出现情况。具体地，我们可以将字母映射到整数的二进制位上，如果某个字母出现了奇数次，则对应的二进制位为 1，否则为 0。最后，我们只需要统计 \(\textit{mask}\) 中为 1 的位数，即为答案。
时间复杂度 \(O(\log n)\)，其中 \(n\) 是输入的整数。空间复杂度 \(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | d = {
0: "zero",
1: "one",
2: "two",
3: "three",
4: "four",
5: "five",
6: "six",
7: "seven",
8: "eight",
9: "nine",
}
class Solution:
def countOddLetters(self, n: int) -> int:
mask = 0
while n:
x = n % 10
n //= 10
for c in d[x]:
mask ^= 1 << (ord(c) - ord("a"))
return mask.bit_count()
|
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 | class Solution {
private static final Map<Integer, String> d = new HashMap<>();
static {
d.put(0, "zero");
d.put(1, "one");
d.put(2, "two");
d.put(3, "three");
d.put(4, "four");
d.put(5, "five");
d.put(6, "six");
d.put(7, "seven");
d.put(8, "eight");
d.put(9, "nine");
}
public int countOddLetters(int n) {
int mask = 0;
while (n > 0) {
int x = n % 10;
n /= 10;
for (char c : d.get(x).toCharArray()) {
mask ^= 1 << (c - 'a');
}
}
return Integer.bitCount(mask);
}
}
|
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 | class Solution {
public:
int countOddLetters(int n) {
static const unordered_map<int, string> d = {
{0, "zero"},
{1, "one"},
{2, "two"},
{3, "three"},
{4, "four"},
{5, "five"},
{6, "six"},
{7, "seven"},
{8, "eight"},
{9, "nine"}};
int mask = 0;
while (n > 0) {
int x = n % 10;
n /= 10;
for (char c : d.at(x)) {
mask ^= 1 << (c - 'a');
}
}
return __builtin_popcount(mask);
}
};
|
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 | func countOddLetters(n int) int {
d := map[int]string{
0: "zero",
1: "one",
2: "two",
3: "three",
4: "four",
5: "five",
6: "six",
7: "seven",
8: "eight",
9: "nine",
}
mask := 0
for n > 0 {
x := n % 10
n /= 10
for _, c := range d[x] {
mask ^= 1 << (c - 'a')
}
}
return bits.OnesCount32(uint32(mask))
}
|
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
31
32
33
34 | function countOddLetters(n: number): number {
const d: Record<number, string> = {
0: 'zero',
1: 'one',
2: 'two',
3: 'three',
4: 'four',
5: 'five',
6: 'six',
7: 'seven',
8: 'eight',
9: 'nine',
};
let mask = 0;
while (n > 0) {
const x = n % 10;
n = Math.floor(n / 10);
for (const c of d[x]) {
mask ^= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
}
return bitCount(mask);
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
|
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
31
32
33
34
35
36 | impl Solution {
pub fn count_odd_letters(mut n: i32) -> i32 {
use std::collections::HashMap;
let d: HashMap<i32, &str> = [
(0, "zero"),
(1, "one"),
(2, "two"),
(3, "three"),
(4, "four"),
(5, "five"),
(6, "six"),
(7, "seven"),
(8, "eight"),
(9, "nine"),
]
.iter()
.cloned()
.collect();
let mut mask: u32 = 0;
while n > 0 {
let x = n % 10;
n /= 10;
if let Some(word) = d.get(&x) {
for c in word.chars() {
let bit = 1 << (c as u8 - b'a');
mask ^= bit as u32;
}
}
}
mask.count_ones() as i32
}
}
|