广安网站制作设计,阜蒙县建设学校官网网站,如何在yy做电影网站,衡阳退休职工做面膜网站特斯拉裁员 10% 昨天#xff0c;特斯拉发全员信#xff0c;宣布全球裁员超 10%。 在内部信中#xff0c;特斯拉 CEO 埃隆马斯克表示#xff1a;多年来#xff0c;我们发展迅速#xff0c;在全球范围内开设了多家工厂。随着增长#xff0c;某些部门出现了角色和工作… 特斯拉裁员 10% 昨天特斯拉发全员信宣布全球裁员超 10%。 在内部信中特斯拉 CEO 埃隆·马斯克表示多年来我们发展迅速在全球范围内开设了多家工厂。随着增长某些部门出现了角色和工作职能的重复。当我们为公司下一阶段的增长做好准备时聚焦各方面以降本增效是极其重要的。 这几乎就是上周写的 亚马逊裁员,涉及中国区 的翻版。 马斯克还表示道裁员是艰难的决定没有什么比这更让我讨厌的了但又必须这么做”。 嗯怎么说就怎么听吧但至少是收购推特后大面积裁员时没说过的。 根据特斯拉的财报截止 2023 年 12 月底特斯拉全球拥有员工约 14W本次裁员 10%即涉及 1.4W 人。 ... 今天来做一道和之前读者投稿的「米哈游」一面算法题相关性较大的题目。 题目描述 平台LeetCode 题号583 给定两个单词 s1 和 s2找到使得 s1 和 s2 相同所需的最小步数每步可以删除任意一个字符串中的一个字符。 示例 输入: sea, eat输出: 2解释: 第一步将sea变为ea第二步将eat变为ea 提示 给定单词的长度不超过 。 给定单词中的字符只含有小写字母。 转换为 LCS 问题 首先给定两字符 s1 和 s2求经过多少次删除操作可使得两个相等字符串。 该问题等价于求解两字符的「最长公共子序列」若两者长度分别为 和 而最长公共子序列长度为 则 即为答案。 对「最长公共子序列LCS」不熟悉的同学可以看 (题解) 1143. 最长公共子序列。 「 代表考虑 的前 个字符、考虑 的前 个字符但最长公共子序列中不一定包含 或者 时形成的「最长公共子序列LCS」长度。」 当有了「状态定义」之后基本上「转移方程」就是呼之欲出 s1[i]s2[j] : 。代表 「必然使用 与 时」 LCS 的长度。 s1[i]!s2[j] : 。代表 「必然不使用 但可能使用 时」 和 「必然不使用 但可能使用 时」 LCS 的长度。 可以发现上述两种讨论已经包含了「不使用 和 」、「仅使用 」、「仅使用 」和「使用 和 」四种情况。 虽然「不使用 和 」会被 和 重复包含但对于求最值问题重复比较并不想影响答案正确性。 因此最终的 为上述两种讨论中的最大值。 一些编码细节 通常会习惯性往字符串头部追加一个空格以减少边界判断使下标从 1 开始并很容易构造出可滚动的「有效值」。但实现上不用真的往字符串中最佳空格只需在初始化动规值时假定存在首部空格以及对最后的 LCS 长度进行减一操作即可。 Java 代码 class Solution { public int minDistance(String s1, String s2) { char[] cs1 s1.toCharArray(), cs2 s2.toCharArray(); int n s1.length(), m s2.length(); int[][] f new int[n 1][m 1]; // 假定存在哨兵空格初始化 f[0][x] 和 f[x][0] for (int i 0; i n; i) f[i][0] 1; for (int j 0; j m; j) f[0][j] 1; for (int i 1; i n; i) { for (int j 1; j m; j) { f[i][j] Math.max(f[i - 1][j], f[i][j - 1]); if (cs1[i - 1] cs2[j - 1]) f[i][j] Math.max(f[i][j], f[i - 1][j - 1] 1); } } int max f[n][m] - 1; // 减去哨兵空格 return n - max m - max; }} C 代码 class Solution {public: int minDistance(string s1, string s2) { int n s1.size(), m s2.size(); vectorvectorint f(n 1, vectorint(m 1)); for (int i 0; i n; i) f[i][0] 1; for (int j 0; j m; j) f[0][j] 1; for (int i 1; i n; i) { for (int j 1; j m; j) { f[i][j] max(f[i - 1][j], f[i][j - 1]); if (s1[i - 1] s2[j - 1]) f[i][j] max(f[i][j], f[i - 1][j - 1] 1); } } int max f[n][m] - 1; return n - max m - max; }}; Python 代码 class Solution: def minDistance(self, s1: str, s2: str) - int: n, m len(s1), len(s2) f [[1]* (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): f[i][j] max(f[i - 1][j], f[i][j - 1]) if s1[i - 1] s2[j - 1]: f[i][j] max(f[i][j], f[i - 1][j - 1] 1) max_val f[n][m] - 1 return n - max_val m - max_val TypeScript 代码 function minDistance(s1: string, s2: string): number { const n s1.length, m s2.length; const f: number[][] Array(n 1).fill(0).map(() Array(m 1).fill(1)); for (let i 1; i n; i) { for (let j 1; j m; j) { f[i][j] Math.max(f[i - 1][j], f[i][j - 1]); if (s1[i - 1] s2[j - 1]) { f[i][j] Math.max(f[i][j], f[i - 1][j - 1] 1); } } } const max f[n][m] - 1; return n - max m - max; }; 时间复杂度 空间复杂度 序列 DP 上述解决方案是套用了「最长公共子序列LCS」进行求解最后再根据 LCS 长度计算答案。 而更加契合题意的状态定义是根据「最长公共子序列LCS」的原始状态定义进行微调「定义 代表考虑 的前 个字符、考虑 的前 个字符最终字符串不一定包含 或 时形成相同字符串的最小删除次数。」 同理不失一般性的考虑 该如何计算 s1[i]s2[j] 代表可以不用必然删掉 和 形成相同字符串 s1[i]!s2[j] 代表至少一个删除 和 中的其中一个。 为上述方案中的最小值最终答案为 。 Java 代码 class Solution { public int minDistance(String s1, String s2) { char[] cs1 s1.toCharArray(), cs2 s2.toCharArray(); int n s1.length(), m s2.length(); int[][] f new int[n 1][m 1]; for (int i 0; i n; i) f[i][0] i; for (int j 0; j m; j) f[0][j] j; for (int i 1; i n; i) { for (int j 1; j m; j) { f[i][j] Math.min(f[i - 1][j] 1, f[i][j - 1] 1); if (cs1[i - 1] cs2[j - 1]) f[i][j] Math.min(f[i][j], f[i - 1][j - 1]); } } return f[n][m]; }} C 代码 class Solution {public: int minDistance(string s1, string s2) { int n s1.size(), m s2.size(); vectorvectorint f(n 1, vectorint(m 1)); for(int i 0; i n; i) f[i][0] i; for(int j 0; j m; j) f[0][j] j; for (int i 1; i n; i) { for (int j 1; j m; j) { f[i][j] min(f[i - 1][j] 1, f[i][j - 1] 1); if (s1[i - 1] s2[j - 1]) f[i][j] min(f[i][j], f[i - 1][j - 1]); } } return f[n][m]; }}; Python 代码 class Solution: def minDistance(self, s1: str, s2: str) - int: n, m len(s1), len(s2) f [[0]* (m 1) for _ in range(n 1)] for i in range(n 1): f[i][0] i for i in range(m 1): f[0][i] i for i in range(1, n 1): for j in range(1, m 1): f[i][j] min(f[i - 1][j] 1, f[i][j - 1] 1) if s1[i - 1] s2[j - 1]: f[i][j] min(f[i][j], f[i - 1][j - 1]) return f[n][m] TypeScript 代码 function minDistance(s1: string, s2: string): number { const n s1.length, m s2.length; const f: number[][] Array.from({length: n 1}, () Array(m 1).fill(0)); for(let i 0; i n; i) f[i][0] i; for(let i 0; i m; i) f[0][i] i; for (let i 1; i n; i) { for (let j 1; j m; j) { f[i][j] Math.min(f[i - 1][j] 1, f[i][j - 1] 1); if (s1.charAt(i - 1) s2.charAt(j - 1)) f[i][j] Math.min(f[i][j], f[i - 1][j - 1]); } } return f[n][m];}; 时间复杂度 空间复杂度 最后 给大伙通知一下 全网最低价 LeetCode 会员目前仍可用 年度会员有效期加赠两个月; 季度会员有效期加赠两周 年度会员获 66.66 现金红包; 季度会员获 22.22 现金红包 年度会员参与当月丰厚专属实物抽奖中奖率 30%) 专属链接leetcode.cn/premium/?promoChannelacoier 我是宫水三叶每天都会分享算法知识并和大家聊聊近期的所见所闻。 欢迎关注明天见。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
