likes
comments
collection
share

华为 OD 一面算法原题

作者站长头像
站长
· 阅读数 7

2.2 亿彩票公布调查结果

昨天，闹得沸沸扬扬的《10 万中 2.2 亿》的彩票事件，迎来了官方公告。

华为 OD 一面算法原题

简单来说，调查结果就是：一切正常，合规合法。

关于福利彩票事件，之前的推文我们已经分析过。

甚至在后面出现《双色球 6.8 亿》事件时，还用类似的逻辑分析写了回答发到过某乎：

华为 OD 一面算法原题

这次所谓调查通报，其实还是没有走出使用「公信力」来进行自证的圈子。

该说的都说过了，本次不再点评。

...

回归主线。

今天接着看「华为 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"

提示：

  • 1<=words.length<=121 <= words.length <= 121<=words.length<=12
  • 1<=words[i].length<=201 <= words[i].length <= 201<=words[i].length<=20
  • words[i] 由小写英文字母组成
  • words 中的所有字符串互不相同

状压 DP

为了方便，将 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] 未被使用。

我们知道，当所有的 g[i][j]=0g[i][j] = 0g[i][j]=0 时，代表所有拼接方式长度均为 ∑i=0n−1ws[i].length\sum_{i = 0}^{n - 1}ws[i].length∑i=0n−1​ws[i].length，即不能通过产生重叠部分来缩短超级串的长度。

因此，最小化超级串 ans 的长度等价于最大化重叠部分的长度。

定义 f[s][i]f[s][i]f[s][i] 代表当前状态为 s 且当前最后一个使用到的字符串为 ws[i] （当前超级串 ans 的结尾部分为 ws[i]）时的最大重合长度。

最终超级串的长度为所有字符串的总长度 ∑i=0n−1ws[i].length\sum_{i = 0}^{n - 1}ws[i].length∑i=0n−1​ws[i].length 减去最大重合长度 max⁡(f[2n−1][i])\max(f[2^n - 1][i])max(f[2n−1][i])。

不失一般性考虑 f[s][i]f[s][i]f[s][i] 可用于更新哪些状态，我们可枚举接在字符串 ws[i] 后面的字符串 ws[j] 为何值：

  1. 由于每个字符串只能使用一次，转移需要满足 s 的第 i 位为 111，s 的第 j 位为 000 的前提条件，含义为 ws[i] 已被使用，而 ws[j] 未被使用
  2. 满足前提条件 111，代表 ws[j] 可接在 ws[i] 后面，此时有状态转移方程：
    f[s∣(1<<j)][j]=f[s][i]+g[i][j] f[s | (1 << j)][j] = f[s][i] + g[i][j]f[s∣(1<<j)][j]=f[s][i]+g[i][j]

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

使用二维数组 p[s][i]p[s][i]p[s][i] 记录每个状态是由哪个前驱转移而来：若有 p[s][i]=jp[s][i] = jp[s][i]=j，代表取得最大重叠长度过程中，字符串 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 代表当前还有哪些字符串待拼接到，初始化为 2n−12^n - 12n−1，代表还没有任何字符串拼接到 ans 中
  • idx 代表当前处理到的字符串下标，初始化通过遍历所有的 f[2n−1][i]f[2^n - 1][i]f[2n−1][i] 找到合适的 iii 作为 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;
  }
}

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

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;
  }
};

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;
}
  • 时间复杂度：将字符串 ws[i]ws[i]ws[i] 的最大长度记为 C=20C = 20C=20，预处理复杂度为 O(n2×C)O(n^2 \times C)O(n2×C)；状态数量为 2n2^n2n，DP 复杂度为 O(2n×n2)O(2^n \times n^2)O(2n×n2)。构造答案复杂度为 O(n)O(n)O(n)。整体复杂度为 O(2n×n2)O(2^n\times n^2)O(2n×n2)
  • 空间复杂度：O(2n×n)O(2^n \times n)O(2n×n)

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

欢迎关注，明天见。

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

转载自:https://juejin.cn/post/7338689046569910309
评论
请登录