大厂运营岗
前天写了 最新大厂职级薪资一览表，不少同学表示很吃惊，尤其是一些几年没跳槽的小伙伴，直呼"现在研发这么值钱了吗？" 🤣🤣🤣
别急，不只是「大厂研发岗」，现在「大厂运营岗」也涨了不少。
我这边找了脉脉的运营同学，要到了最新的「大厂运营岗薪资地图」，大家可以看一眼：
还是很有意思的，尤其是将其和前天的「大厂研发岗」薪资图放到一起来看：
一般来说，我觉得同家公司中同职级的「运营岗」收入大概是「研发岗」的 0.5~0.8 会是比较正常。
但从最新的数据来看，并不是这么回事。
不少大厂如今的运营岗薪资基本和研发岗齐平，甚至有高于研发岗的（例如福报厂中高职级的运营岗，年收入是研发岗的两倍），由此可见，顶级运营人才要比技术人才要稀缺？（计算机天塌了
对此，你怎么看？大厂运营岗位的薪资统计图，有超出你的预期吗？欢迎评论区交流。
...
回归主题。
来一道和「社招」相关的算法题。
题目描述
平台：LeetCode
题号：522
给定字符串列表 strs，返回其中 最长的特殊序列。如果最长特殊序列不存在，返回 。
特殊序列定义如下：该序列为某字符串独有的子序列（即不能是其他字符串的子序列）。
s 的子序列可以通过删去字符串 s 中的某些字符实现。
例如， "abc"是"aebdc"的子序列，因为您可以删除"aebdc"中的下划线字符来得到"abc"。"aebdc"的子序列还包括"aebdc"、"aeb"和""(空字符串)。
示例 1：
输入: strs = ["aba","cdc","eae"]
输出: 3
示例 2:
输入: strs = ["aaa","aaa","aa"]
输出: -1
提示:
strs[i]只包含小写英文字母
LCS
记 strs 数组长度为 ，单个 的最大长度 。其中 数据范围为 ， 数据范围为 。
根据题意，我们可以枚举每个 ，检查其是否为其他 的子序列，这需要枚举所有点对，复杂度为 。同时记录遍历过程中的最大长度 ans，用于剪枝（对于字符串长度本身小于等于 ans 的 可直接跳过）。
我们可以实现一个 check 函数来检查 s1 是否为 s2 的子序列，该问题可转化为求 s1 和 s2 的最长公共子序列长度。若最长公共子序列长度为 s1 长度，说明 s1 为 s2 的子序列，此时 不满足条件，否则我们使用 的长度来更新 ans。check 函数的复杂度为 。
❝「不了解 LCS 的同学可以看前置 🧀 : LCS 模板题」
❞
因此总的计算量为 ，可以过。
Java 代码：
class Solution {
public int findLUSlength(String[] strs) {
int n = strs.length, ans = -1;
for (int i = 0; i < n; i++) {
if (strs[i].length() <= ans) continue;
boolean ok = true;
for (int j = 0; j < n && ok; j++) {
if (i == j) continue;
if (check(strs[i], strs[j])) ok = false;
}
if (ok) ans = strs[i].length();
}
return ans;
}
boolean check(String s1, String s2) {
int n = s1.length(), m = s2.length();
if (m < n) return false;
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = s1.charAt(i - 1) == s2.charAt(j - 1) ? f[i - 1][j - 1] + 1 : f[i - 1][j - 1];
f[i][j] = Math.max(f[i][j], f[i - 1][j]);
f[i][j] = Math.max(f[i][j], f[i][j - 1]);
if (f[i][j] == n) return true;
}
}
return false;
}
}
C++ 代码：
class Solution {
public:
int findLUSlength(vector<string>& strs) {
int n = strs.size(), ans = -1;
for (int i = 0; i < n; i++) {
if (static_cast<int>(strs[i].length()) <= ans) continue;
bool ok = true;
for (int j = 0; j < n && ok; j++) {
if (i == j) continue;
if (check(strs[i], strs[j])) ok = false;
}
if (ok) ans = strs[i].length();
}
return ans;
}
bool check(const string& s1, const string& s2) {
int n = s1.length(), m = s2.length();
if (m < n) return false;
vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = s1[i - 1] == s2[j - 1] ? f[i - 1][j - 1] + 1 : f[i - 1][j - 1];
f[i][j] = max(f[i][j], f[i - 1][j]);
f[i][j] = max(f[i][j], f[i][j - 1]);
if (f[i][j] == n) return true;
}
}
return false;
}
};
Python 代码：
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
n, ans = len(strs), -1
for i in range(n):
if len(strs[i]) <= ans:
continue
ok = True
for j in range(n):
if not ok:
break
if i == j:
continue
if self.check(strs[i], strs[j]):
ok = False
if ok:
ans = len(strs[i])
return ans
def check(self, s1, s2):
n, m = len(s1), len(s2)
if m < n:
return False
f = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
f[i][j] = f[i - 1][j - 1] + 1 if s1[i - 1] == s2[j - 1] else f[i - 1][j - 1]
f[i][j] = max(f[i][j], f[i - 1][j], f[i][j - 1])
if f[i][j] == n:
return True
return False
TypeScript 代码：
function check(s1: string, s2: string): boolean {
const n = s1.length, m = s2.length;
if (m < n) return false;
const f = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
f[i][j] = s1[i - 1] === s2[j - 1] ? f[i - 1][j - 1] + 1 : 0;
f[i][j] = Math.max(f[i][j], f[i - 1][j]);
f[i][j] = Math.max(f[i][j], f[i][j - 1]);
if (f[i][j] === n) return true;
}
}
return false;
}
function findLUSlength(strs: string[]): number {
let n = strs.length, ans = -1;
for (let i = 0; i < n; i++) {
if (strs[i].length <= ans) continue;
let ok = true;
for (let j = 0; j < n && ok; j++) {
if (i === j) continue;
if (check(strs[i], strs[j])) ok = false;
}
if (ok) ans = strs[i].length;
}
return ans;
};
时间复杂度：检查每个 是否符合要求，需要枚举所有的点对，复杂度为 ；求解 LCS 问题的复杂度为 。整体复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
