赞
踩
昨天,闹得沸沸扬扬的《10 万中 2.2 亿》的彩票事件,迎来了官方公告。
简单来说,调查结果就是:一切正常,合规合法。
关于福利彩票事件,之前的推文我们已经分析过。
甚至在后面出现《双色球 6.8 亿》事件时,还用类似的逻辑分析写了回答发到过某乎:
这次所谓调查通报,其实还是没有走出使用「公信力」来进行自证的圈子。
该说的都说过了,本次不再点评。
...
回归主线。
今天接着看「华为 OD」一面算法原题。
昨天分享了一道「子序列」相关的「华为 OD」一面算法原题,很多网友表示不可思议。
那道题在 LeetCode 中是 Hard,现在连 OD 都这么卷了吗?
是的,OD 都开始卷了。
这其实不难理解。
算法在笔试面试中出现,主要是起到一个「过滤」的作用。
以前面试算法题难度普遍没有很高,是因为出到普通难度,也足以产生过滤作用,再难可能就没有候选人做出来,反而起不到过滤效果。
现如今,随着互联网大厂的各种裁员,加上应届大学生毕业人数屡创新高,连华为 OD 岗位都供远大于求了,因此算法题难度也上来了。
平台:LeetCode
题号:943
给定一个字符串数组 words
,找到以 words
中每个字符串作为子字符串的最短字符串。
如果有多个有效最短字符串满足题目条件,返回其中任意一个即可。
我们可以假设 words
中没有字符串是 words
中另一个字符串的子字符串。
示例 1:
输入:words = ["alex","loves","leetcode"]
输出:"alexlovesleetcode"
解释:"alex","loves","leetcode" 的所有排列都会被接受。
示例 2:
输入:words = ["catg","ctaagt","gcta","ttca","atgcatc"]
输出:"gctaagttcatgcatc"
提示:
words[i]
由小写英文字母组成
words
中的所有字符串互不相同
为了方便,将 words
记为 ws
。
预处理二维数组 g
来表示字符串 ws[i]
和 ws[j]
的重叠部分的长度:若 g[i][j] = len
代表字符串 ws[i]
长度为 len
的后缀与字符串 ws[j]
长度为 len
的前缀相同。
另外用一个二进制数 status
来代表当前超级串 ans
对 ws
的使用(覆盖)情况:若 status
的第 i
位为 1
代表字符串 ws[i]
已被使用(即 ws[i]
已是 ans
的子串),若 status
的第 i
位为 0
代表 ws[i]
未被使用。
我们知道,当所有的 时,代表所有拼接方式长度均为 ,即不能通过产生重叠部分来缩短超级串的长度。
因此,最小化超级串 ans
的长度等价于最大化重叠部分的长度。
定义
代表当前状态为 s
且当前最后一个使用到的字符串为 ws[i]
(当前超级串 ans
的结尾部分为 ws[i]
)时的最大重合长度。
最终超级串的长度为所有字符串的总长度 减去最大重合长度 。
不失一般性考虑
可用于更新哪些状态,我们可枚举接在字符串 ws[i]
后面的字符串 ws[j]
为何值:
s
的第
i
位为
,
s
的第
j
位为
的前提条件,含义为
ws[i]
已被使用,而
ws[j]
未被使用
ws[j]
可接在
ws[i]
后面,此时有状态转移方程:
接下来,考虑如何构建具体方案。
使用二维数组
记录每个状态是由哪个前驱转移而来:若有
,代表取得最大重叠长度过程中,字符串 ws[j]
接在 ws[i]
后面。
我们从后往前对 ans
进行构造,若 ans = ws[0] + ws[1] + ... + ws[k - 1] + ws[k]
,我们是先找 ws[k]
,再通过 ws[k]
找 ws[k - 1]
,直到将整个 ans
构建出来。
构造过程中使用变量解释如下:
ans
为具体的超级串
status
代表当前还有哪些字符串待拼接到,初始化为
,代表还没有任何字符串拼接到
ans
中
idx
代表当前处理到的字符串下标,初始化通过遍历所有的
找到合适的
作为
idx
last
代表前一个处理到字符串下标,初始化为
-1
一些细节:当 last
不为初始值 -1
时,需要跳过 ws[idx]
与 ws[last]
的重复部分进行拼接。
Java 代码:
class Solution {
public String shortestSuperstring(String[] ws) {
int n = ws.length, mask = 1 << n;
int[][] g = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
String a = ws[i], b = ws[j];
int l1 = a.length(), l2 = b.length(), len = Math.min(l1, l2);
for (int k = len; k >= 1; k--) {
if (a.substring(l1 - k).equals(b.substring(0, k))) {
g[i][j] = k;
break;
}
}
}
}
int[][] f = new int[mask][n], p = new int[mask][n];
for (int s = 0; s < mask; s++) {
for (int i = 0; i < n; i++) {
if (((s >> i) & 1) == 0) continue;
for (int j = 0; j < n; j++) {
if (((s >> j) & 1) == 1) continue;
if (f[s | (1 << j)][j] <= f[s][i] + g[i][j]) {
f[s | (1 << j)][j] = f[s][i] + g[i][j];
p[s | (1 << j)][j] = i;
}
}
}
}
int max = f[mask - 1][0], idx = 0, last = -1, status = mask - 1;
for (int i = 1; i < n; i++) {
if (max < f[mask - 1][i]) {
max = f[mask - 1][i];
idx = i;
}
}
String ans = "";
while (status != 0) {
if (last == -1) ans = ws[idx];
else ans = ws[idx].substring(0, ws[idx].length() - g[idx][last]) + ans;
last = idx;
idx = p[status][idx];
status ^= (1 << last);
}
return ans;
}
}
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
Python 代码:
class Solution:
def shortestSuperstring(self, ws: List[str]) -> str:
n, mask = len(ws), 1 << len(ws)
g = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
a, b = ws[i], ws[j]
l1, l2 = len(a), len(b)
length = min(l1, l2)
for k in range(length, 0, -1):
if a[l1 - k:] == b[:k]:
g[i][j] = k
break
f = [[0 for _ in range(n)] for _ in range(mask)]
p = [[0 for _ in range(n)] for _ in range(mask)]
for s in range(mask):
for i in range(n):
if (s >> i) & 1 == 0:
continue
for j in range(n):
if (s >> j) & 1 == 1:
continue
if f[s | (1 << j)][j] <= f[s][i] + g[i][j]:
f[s | (1 << j)][j] = f[s][i] + g[i][j]
p[s | (1 << j)][j] = i
max_val = f[mask - 1][0]
idx, last, status = 0, -1, mask - 1
for i in range(1, n):
if max_val < f[mask - 1][i]:
max_val = f[mask - 1][i]
idx = i
ans = ""
while status != 0:
if last == -1:
ans = ws[idx]
else:
ans = ws[idx][:len(ws[idx]) - g[idx][last]] + ans
last = idx
idx = p[status][idx]
status ^= 1 << last
return ans
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
C++ 代码:
class Solution {
public:
string shortestSuperstring(vector<string>& ws) {
int n = ws.size(), mask = 1 << n;
vector<vector<int>> g(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
string a = ws[i], b = ws[j];
int l1 = a.length(), l2 = b.length(), len = min(l1, l2);
for (int k = len; k >= 1; k--) {
if (a.substr(l1 - k) == b.substr(0, k)) {
g[i][j] = k;
break;
}
}
}
}
vector<vector<int>> f(mask, vector<int>(n, 0)), p(mask, vector<int>(n, 0));
for (int s = 0; s < mask; s++) {
for (int i = 0; i < n; i++) {
if (((s >> i) & 1) == 0) continue;
for (int j = 0; j < n; j++) {
if (((s >> j) & 1) == 1) continue;
if (f[s | (1 << j)][j] <= f[s][i] + g[i][j]) {
f[s | (1 << j)][j] = f[s][i] + g[i][j];
p[s | (1 << j)][j] = i;
}
}
}
}
int max = f[mask - 1][0], idx = 0, last = -1, status = mask - 1;
for (int i = 1; i < n; i++) {
if (max < f[mask - 1][i]) {
max = f[mask - 1][i];
idx = i;
}
}
string ans = "";
while (status != 0) {
if (last == -1) ans = ws[idx];
else ans = ws[idx].substr(0, ws[idx].length() - g[idx][last]) + ans;
last = idx;
idx = p[status][idx];
status ^= (1 << last);
}
return ans;
}
};
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
TypeScript 代码:
function shortestSuperstring(ws: string[]): string {
const n = ws.length, mask = 1 << n;
const g = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const a = ws[i], b = ws[j];
const l1 = a.length, l2 = b.length;
const len = Math.min(l1, l2);
for (let k = len; k >= 1; k--) {
if (a.substring(l1 - k) === b.substring(0, k)) {
g[i][j] = k;
break;
}
}
}
}
const f = new Array(mask).fill(0).map(() => new Array(n).fill(0));
const p = new Array(mask).fill(0).map(() => new Array(n).fill(0));
for (let s = 0; s < mask; s++) {
for (let i = 0; i < n; i++) {
if (((s >> i) & 1) === 0) continue;
for (let j = 0; j < n; j++) {
if (((s >> j) & 1) === 1) continue;
if (f[s | (1 << j)][j] <= f[s][i] + g[i][j]) {
f[s | (1 << j)][j] = f[s][i] + g[i][j];
p[s | (1 << j)][j] = i;
}
}
}
}
let max = f[mask - 1][0], idx = 0, last = -1, status = mask - 1;
for (let i = 1; i < n; i++) {
if (max < f[mask - 1][i]) {
max = f[mask - 1][i];
idx = i;
}
}
let ans = "";
while (status != 0) {
if (last === -1) ans = ws[idx];
else ans = ws[idx].substring(0, ws[idx].length - g[idx][last]) + ans;
last = idx;
idx = p[status][idx];
status ^= (1 << last);
}
return ans;
}
![](https://csdnimg.cn/release/blogv2/dist/pc/img/newCodeMoreWhite.png)
DP
复杂度为
。构造答案复杂度为
。整体复杂度为
我是宫水三叶,每天都会分享算法知识,并和大家聊聊近期的所见所闻。
欢迎关注,明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。