斯诺登的密码 - 题目列表

题意

给出一句英文句子。先找出其中所有表示数字的单词，把每个数字平方后对 100 取模，得到若干个两位数。然后重新排列这些两位数，拼出尽可能小的密码。

思路

先用字典保存单词到数字的映射。每遇到一个合法数字单词，就计算：

text

1value * value % 100

题目要求把结果当作两位数，例如 1 要看成 01，4 要看成 04。在 Python 中可以写成：

python

1f"{x:02d}"

因为每一段长度都固定为两位，想让拼接后的整体最小，只需要把这些两位字符串升序排序，再拼起来。最后把整体前导零删除；如果删完为空，就输出 0。

这题不需要枚举排列，排序就是正解。历史目录中保留 C++ 暴力文件，本文不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：普通 dict 适合保存单词到数字的映射。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：parts.sort() 对等长字符串升序排序。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：split() 拆分单词，"".join(...) 拼接答案。
f"{x:02d}" 把整数格式化成至少两位，不足补前导零。

代码

python

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
37
38
39
40
41word_to_number = {
    "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,
    "a": 1,
    "both": 2,
    "another": 1,
    "first": 1,
    "second": 2,
    "third": 3,
}

words = input().strip().rstrip(".").lower().split()
parts = []

for word in words:
    if word in word_to_number:
        value = word_to_number[word]
        parts.append(f"{value * value % 100:02d}")

parts.sort()
password = "".join(parts).lstrip("0")
print(password if password else "0")

Pythonic 写法

字典映射 + 推导式生成平方末两位后排序拼接：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15word_to_number = {
    "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,
    "a": 1, "both": 2, "another": 1, "first": 1, "second": 2, "third": 3,
}

words = input().strip().rstrip(".").lower().split()
parts = sorted(
    f"{word_to_number[w] * word_to_number[w] % 100:02d}"
    for w in words
    if w in word_to_number
)
print("".join(parts).lstrip("0") or "0")

复杂度

句子只有 6 个单词，时间和空间都可视为 $O(1)$ 。若按单词数 m 计，排序复杂度是 $O(m\log m)$ 。

总结

这题表面像全排列，关键观察是每一块都是两位。等长块要拼出最小结果，直接升序排序即可。