3月20日笔试题第二题

目录

1. 题目
2. 思路
   1. 预处理
   2. 深搜或动态规划
      1. 深搜
      2. 动态规划
3. 代码
   1. 深搜
   2. 动态规划
4. 测试

更新：

2020 年 3 月 21 日，最初代码的预处理有问题，字符串开始与结尾字母相同时，应该累加字符串长度。

题目

给出一组 n 个字符串。每个字符串都是小写字母组成，且 ascii 码非递减。

求使用这 n 个字符串，最大能拼接出长度为多少的非递减字符串。

1 <= n <= 10^6

思路

可以转化为有向图，然后求图上最大路径和。每一个字符串做点，两个可以拼接字符串之间连边（这里可以优化）。

预处理

1e6 个点，太多了，可以通过预处理，把点数控制到不超过 351 个。因为一共只有 26 个字母，比如对于 a 开头，b 结尾的字符串，只保留长度最大的即可，其他全都舍掉。如 ab， abbbb 和 abb，只保留最长的一个就可以。

定义 26 × 26 的数组 edges，edges[i][j] 代表 i 字母到 j 字母的最长的字符串，26*26 = 676，因为只可能有 a b，不能有 b a，所以数组有半是空的。最多有 351 个点。

构造边，两个字符串，只要 S2 的开头小于等于 S1 的结尾就认为有 S1 到 S2 的边

这里可以优化，比如 aaa，bbbb，efg， hij。这里 aaa 到了 bbb，就不用再看 aaa 直接到 efg 和 hij 了。因为 bbbb 也可以到他们，aaa 直接到他们，肯定不如经过 bbbb 长。

深搜或动态规划

深搜

直接深搜会超时，需使用 functools.lru_cache 装饰器，做记忆化搜索，实际上相当于动态规划。

使用 node_s_e 记录每一个点的 start 字母，和 end 字母

使用 s2node_list，s2node_list[i] 是所有以 i 开头的点的列表

动态规划

定义 dp 为长度 26 的数组，dp[i] 代表结尾字母小于等于 i 的串的最大长度。

代码

深搜

import functools

x = ['az', 'bcd', 'zzz', 'bcdef']
x = ['aaa', 'bcd', 'zzz', 'bcdef']

edges = [[0] *26 for _ in range(26)]
base = ord('a')
for s in x:
    if s[0] == s[-1]:
        edges[ord(s[0])-base][ord(s[-1])-base] += len(s)
    else:
        edges[ord(s[0])-base][ord(s[-1])-base] = max(len(s), edges[ord(s[0])-base][ord(s[-1])-base])
    
nodes = [0]
node_s_e = [0]
s2node_list = [[] for _ in range(26)]
for i in range(26):
    for j in range(26):
        if edges[i][j] > 0:
            nodes.append(edges[i][j])
            edges[i][j] = len(nodes)-1
            node_s_e.append((i, j))
            s2node_list[i].append(len(nodes)-1)
flag = [True] * len(nodes)

@functools.lru_cache(355)
def dfs(i):
    flag[i] = False
    s, e = node_s_e[i]
#     print(i, e)
    cur_max = 26
    ans = 0
    while e < cur_max:
        for j in s2node_list[e]:
            if not flag[j]: continue
            ans = max(ans, dfs(j))
            cur_max = min(cur_max, node_s_e[j][1])
        e += 1
    
    flag[i] = True
    return nodes[i] + ans
ans = 0

for i in range(1, len(nodes)):
    ans = max(ans, dfs(i))
print(ans)

动态规划

x = ['aaa', 'bcd', 'zzz', 'bcdef']

edges = [[0] *26 for _ in range(26)]
base = ord('a')
for s in x:
    if s[0] == s[-1]:
        edges[ord(s[0])-base][ord(s[-1])-base] += len(s)
    else:
        edges[ord(s[0])-base][ord(s[-1])-base] = max(len(s), edges[ord(s[0])-base][ord(s[-1])-base])
dp = [0] * 26

dp[0] = edges[0][0]

for i in range(1, 26):
    maxv = 0
    for j in range(0, i):
        maxv = max(maxv, dp[j] + edges[j][i])
    dp[i] = maxv + edges[i][i]
print(dp[-1])

测试

最极端情况 edges 数组是满的，所以生成随机数填充的 edges 数组做测试

import time
import random
import functools
bt = time.time() * 1000
edges = [[0] *26 for _ in range(26)]
for i in range(26):
    for j in range(i, 26):
        edges[i][j] = random.randint(1,99999)
dp = [0] * 26

dp[0] = edges[0][0]

for i in range(1, 26):
    maxv = 0
    for j in range(0, i):
        maxv = max(maxv, dp[j] + edges[j][i])
    dp[i] = maxv + edges[i][i]
print(dp[-1])
nodes = [0]
node_s_e = [0]
s2node_list = [[] for _ in range(26)]
for i in range(26):
    for j in range(26):
        if edges[i][j] > 0:
            nodes.append(edges[i][j])
            edges[i][j] = len(nodes)-1
            node_s_e.append((i, j))
            s2node_list[i].append(len(nodes)-1)
flag = [True] * len(nodes)

@functools.lru_cache(355)
def dfs(i):
    flag[i] = False
    s, e = node_s_e[i]
#     print(i, e)
    cur_max = 26
    ans = 0
    while e < cur_max:
        for j in s2node_list[e]:
            if not flag[j]: continue
            ans = max(ans, dfs(j))
            cur_max = min(cur_max, node_s_e[j][1])
        e += 1
    
    flag[i] = True
    return nodes[i] + ans
ans = 0
for i in range(1, len(nodes)):
    ans = max(ans, dfs(i))
print(ans)
time.time() * 1000 - btimport time
import random
import functools
bt = time.time() * 1000
edges = [[0] *26 for _ in range(26)]
for i in range(26):
    for j in range(i, 26):
        edges[i][j] = random.randint(1,99999)
dp = [0] * 26

dp[0] = edges[0][0]

for i in range(1, 26):
    maxv = 0
    for j in range(0, i):
        maxv = max(maxv, dp[j] + edges[j][i])
    dp[i] = maxv + edges[i][i]
print(dp[-1])
nodes = [0]
node_s_e = [0]
s2node_list = [[] for _ in range(26)]
for i in range(26):
    for j in range(26):
        if edges[i][j] > 0:
            nodes.append(edges[i][j])
            edges[i][j] = len(nodes)-1
            node_s_e.append((i, j))
            s2node_list[i].append(len(nodes)-1)
flag = [True] * len(nodes)

@functools.lru_cache(355)
def dfs(i):
    flag[i] = False
    s, e = node_s_e[i]
#     print(i, e)
    cur_max = 26
    ans = 0
    while e < cur_max:
        for j in s2node_list[e]:
            if not flag[j]: continue
            ans = max(ans, dfs(j))
            cur_max = min(cur_max, node_s_e[j][1])
        e += 1
    
    flag[i] = True
    return nodes[i] + ans
ans = 0
for i in range(1, len(nodes)):
    ans = max(ans, dfs(i))
print(ans)
time.time() * 1000 - bt

输出：

2424978
(3.804931640625, ‘ms’)

把 edges[i][j] = random.randint(1,99999) 换成 edges[i][j] = random.randint(1,99999) if random.random() > 0.3 else 0 可以生成随机数据。