2.2 亿彩票公布调查结果

昨天，闹得沸沸扬扬的《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"

提示：

接下来，考虑如何构建具体方案。

使用二维数组 记录每个状态是由哪个前驱转移而来：若有 ，代表取得最大重叠长度过程中，字符串 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 代码：

classSolution{
publicStringshortestSuperstring(String[]ws){
intn=ws.length,mask=1<<n;
int[][]g=newint[n][n];
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
Stringa=ws[i],b=ws[j];
intl1=a.length(),l2=b.length(),len=Math.min(l1,l2);
for(intk=len;k>=1;k--){
if(a.substring(l1-k).equals(b.substring(0,k))){
g[i][j]=k;
break;
}
}
}
}
int[][]f=newint[mask][n],p=newint[mask][n];
for(ints=0;s<mask;s++){
for(inti=0;i<n;i++){
if(((s>>i)&1)==0)continue;
for(intj=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;
}
}
}
}
intmax=f[mask-1][0],idx=0,last=-1,status=mask-1;
for(inti=1;i<n;i++){
if(max<f[mask-1][i]){
max=f[mask-1][i];
idx=i;
}
}
Stringans="";
while(status!=0){
if(last==-1)ans=ws[idx];
elseans=ws[idx].substring(0,ws[idx].length()-g[idx][last])+ans;
last=idx;
idx=p[status][idx];
status^=(1<<last);
}
returnans;
}
}

Python 代码：

classSolution:
defshortestSuperstring(self,ws:List[str])->str:
n,mask=len(ws),1<<len(ws)
g=[[0for_inrange(n)]for_inrange(n)]
foriinrange(n):
forjinrange(n):
a,b=ws[i],ws[j]
l1,l2=len(a),len(b)
length=min(l1,l2)
forkinrange(length,0,-1):
ifa[l1-k:]==b[:k]:
g[i][j]=k
break
f=[[0for_inrange(n)]for_inrange(mask)]
p=[[0for_inrange(n)]for_inrange(mask)]
forsinrange(mask):
foriinrange(n):
if(s>>i)&1==0:
continue
forjinrange(n):
if(s>>j)&1==1:
continue
iff[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
foriinrange(1,n):
ifmax_val<f[mask-1][i]:
max_val=f[mask-1][i]
idx=i
ans=""
whilestatus!=0:
iflast==-1:
ans=ws[idx]
else:
ans=ws[idx][:len(ws[idx])-g[idx][last]]+ans
last=idx
idx=p[status][idx]
status^=1<<last
returnans

C++ 代码：

classSolution{
public:
stringshortestSuperstring(vector<string>&ws){
intn=ws.size(),mask=1<<n;
vector<vector<int>>g(n,vector<int>(n,0));
for(inti=0;i<n;i++){
for(intj=0;j<n;j++){
stringa=ws[i],b=ws[j];
intl1=a.length(),l2=b.length(),len=min(l1,l2);
for(intk=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(ints=0;s<mask;s++){
for(inti=0;i<n;i++){
if(((s>>i)&1)==0)continue;
for(intj=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;
}
}
}
}
intmax=f[mask-1][0],idx=0,last=-1,status=mask-1;
for(inti=1;i<n;i++){
if(max<f[mask-1][i]){
max=f[mask-1][i];
idx=i;
}
}
stringans="";
while(status!=0){
if(last==-1)ans=ws[idx];
elseans=ws[idx].substr(0,ws[idx].length()-g[idx][last])+ans;
last=idx;
idx=p[status][idx];
status^=(1<<last);
}
returnans;
}
};

TypeScript 代码：

functionshortestSuperstring(ws:string[]):string{
constn=ws.length,mask=1<<n;
constg=newArray(n).fill(0).map(()=>newArray(n).fill(0));
for(leti=0;i<n;i++){
for(letj=0;j<n;j++){
consta=ws[i],b=ws[j];
constl1=a.length,l2=b.length;
constlen=Math.min(l1,l2);
for(letk=len;k>=1;k--){
if(a.substring(l1-k)===b.substring(0,k)){
g[i][j]=k;
break;
}
}
}
}
constf=newArray(mask).fill(0).map(()=>newArray(n).fill(0));
constp=newArray(mask).fill(0).map(()=>newArray(n).fill(0));
for(lets=0;s<mask;s++){
for(leti=0;i<n;i++){
if(((s>>i)&1)===0)continue;
for(letj=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;
}
}
}
}
letmax=f[mask-1][0],idx=0,last=-1,status=mask-1;
for(leti=1;i<n;i++){
if(max<f[mask-1][i]){
max=f[mask-1][i];
idx=i;
}
}
letans="";
while(status!=0){
if(last===-1)ans=ws[idx];
elseans=ws[idx].substring(0,ws[idx].length-g[idx][last])+ans;
last=idx;
idx=p[status][idx];
status^=(1<<last);
}
returnans;
}
  • 时间复杂度：将字符串 的最大长度记为 ，预处理复杂度为 ；状态数量为 ， DP 复杂度为 。构造答案复杂度为 。整体复杂度为
  • 空间复杂度：

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地