网站域名解析页面,太原网络广告公司,网站建设交接协议书,从网站开发到游戏编程2.2 亿彩票公布调查结果 昨天#xff0c;闹得沸沸扬扬的《10 万中 2.2 亿》的彩票事件#xff0c;迎来了官方公告。 简单来说#xff0c;调查结果就是#xff1a;一切正常#xff0c;合规合法。 关于福利彩票事件#xff0c;之前的推文我们已经分析过。 甚至在后面出现《… 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解释alexlovesleetcode 的所有排列都会被接受。 示例 2 输入words [catg,ctaagt,gcta,ttca,atgcatc]输出gctaagttcatgcatc 提示 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] 未被使用。 我们知道当所有的 时代表所有拼接方式长度均为 即不能通过产生重叠部分来缩短超级串的长度。 因此最小化超级串 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; }} 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(vectorstring ws) { int n ws.size(), mask 1 n; vectorvectorint g(n, vectorint(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; } } } } vectorvectorint f(mask, vectorint(n, 0)), p(mask, vectorint(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;} 时间复杂度将字符串 的最大长度记为 预处理复杂度为 状态数量为 DP 复杂度为 。构造答案复杂度为 。整体复杂度为 空间复杂度 我是宫水三叶每天都会分享算法知识并和大家聊聊近期的所见所闻。 欢迎关注明天见。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
