阿里 9 月 29 笔试

目录

1. 第一题
2. 第二题

今天笔试不难。一共两道编程题。

第一题

给出一个只有 0 和 1 的字符串。要去把该串划分为 n 段。每段有且仅能有一个 0。

第一个输入为字符串长度，第二行是字符串。

输出为划分方案数，对1000000007取模。

特别主要仅有 1 的情况，答案是 0。比较坑的点是这一点题目中没有提到。。。因为题目中没有提到全 1 到底怎么算（我理解全1可能是一种非法情况，但实际上题目的测试数据中包含了全1，且答案是0，这个是我试出来的）所以说感觉比较坑。

我的思路是：首先有两个关键的地方，第一是这个字符串要划分成几段，第二是每段包含哪些字符。第一点是固定的，即有几个 0 就得划分成几段。因为每段有且只有 1 个 0。所以这里就先找出所有的 0 就知道可以划分成多少段了。然后再看1，1 只能依附于 0，而不能独立存在。就可以看每段里的 1 如何分配。如 0110。中间两个 1 可以全给左边的 0 即 011 | 0。可以左右各一个 01 | 10。也可以全给右边的 0 | 110。这样我们可以发现开头的所有 1 都只能依附于第一个 0。所以这些 1 的归属只有 1 中情况。所以可以直接把这些 1 去掉。同样的，最后面的 1 也可以去掉。任何处于两个 0 之间的 1，如果总数有 N 个，会产生 N + 1 中不同的情况。所以这时候只要找到所有0之间的连续 1 的个数，都加一，再相乘就是答案。

样例：

5
010100

输出：

4

AC代码：

n = int(input())
l = input()

c = 0
i = 0
ans = 1
while i < len(l) and l[i] == '1':
    i += 1
if len(l) == i:
    print(0)
else:
    while i < len(l):
        if l[i] == '1':
            c += 1
        elif l[i] == '0':
            if c > 0:
                ans = (ans * (c + 1)) % 1000000007
                c = 0
        i += 1
    print(ans)

第二题

一个英文联想输入法。词典有 n 个词。

输入时有两个方法：

1. 输入一个字母，消耗 1 个时间
2. 从词典中所有前缀为当前已输入字符的词，替换当前内容。耗时为当前匹配的所有词语的个数。即如果当前输入的字符有 m 个匹配，消耗 m 时间。

在给定字典的情况下，判断要输入的 q 个单词，每个单词最短耗时。

所有词长度不大于 10^6。

样例：

5 5
a
an
at
and
nowcoder
a
and
nowcoder
nowcoderovo
what

输出：

1
3
2
5
4

思路：可以用字典树。如果用递归，注意调整堆栈大小。

先把词典建成字典树。这步是比较清晰的，因为字典树就是用来快速的查找一个单词有没有出现过，且可以查找某个前缀对应了几个单词。

从 42 行开始的代码的思路是，每次输入一个词：

1. 如果这个词是字典树中的词，那么要么就是需要输入全部字母，要么就是输入一部分字母后通过自动补全输入，这就需要依次遍历这个单词的字母，找出一个最小操作数。这个遍历每个字母的操作在get_word_ans函数中。另外word_in用于查找一个单词是否在字典树中出现过。

2. 如果这个词不是字典树中的词，可以直接输入，或者使用自动补全输入当前单词的一个前缀，例如要输入’words’，词典里没有这个词，但是有 ‘word’，word 是 words 的前缀，所以可以先自动补全成 word，再输入 s，这里的最小值就是 要输入的单词长度 或者 输入前缀的单词的长度 + 前缀以后的长度。这就对应第48行代码，二者取最小值。所以 word_in 函数会通过一个全局变量 max_i 返回目标单词在词典中的最长前缀。（这里用最长前缀一定是最优的）

再说下字典树节点各属性的含义：’f’ 即 flag，是标志从根到当前节点是否是一个词语，如果 f 为 True 则代表有一个从根开始，到当前元素（字母）结束的单词。如果 f 为 False，则说明当前元素只是一个中间的字母。 ‘c’ 代表有多少个词以根到当前字母为前缀。’ch’ 则是到孩子节点的指针。

AC代码：

import sys
sys.setrecursionlimit(1000006)
tt = {'ch': {}, 'f': False, 'c': 0}

def add_wd(i, w, t):
    if i == len(w):
        t['f'] = True
        t['c'] += 1
        return

    if w[i] not in t['ch']:
        t['ch'][w[i]] = {'ch': {}, 'f': False, 'c': 0}
    t['c'] += 1
    add_wd(i+1, w, t['ch'][w[i]])

n, q = map(int, input().split())
for _ in range(n):
    add_wd(0, input(), tt)

max_i = [0]
def word_in(i, w, t):
    max_i[0] = i
    if i == len(w):
        return t['f']
    if w[i] not in t['ch']:
        return False
    return word_in(i+1, w, t['ch'][w[i]])

def get_word_ans(w):
    t = tt
    minc = len(w)
    i = 0
    while i < len(w):
        ch = w[i]
        if ch not in t['ch']:
            break
        minc = min(minc, i + t['c'])
        t = t['ch'][ch]
        i += 1
    return minc

for _ in range(q):
    w = input()
    if word_in(0, w, tt):
        print(get_word_ans(w))
    else:
        x1 = get_word_ans(w[:max_i[0]])
        print(min(x1 + len(w) - max_i[0], len(w)))
#         print('word', w[:max_i[0]], max_i[0])