大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天在脉脉看到一位同学校招拿了仅低于人才计划的ssp offer，但是自认为水平很菜，面试全靠吹牛和自身不错的背景蒙混过关，对未来要做的方向了解比较少，团队还比较卷，担心入职后跟不上节奏，产出低背绩效。
评论区有相似经历的脉友表示当初校招他也是拿了这个档位的offer，没有多大区别，多请教多学习多沟通多对齐及时反馈比什么都重要。也有脉友表示跟面试有差距，面试官都是有心理预期的，体现出自己积极的学习态度和个人提升就可以。还有脉友开玩笑说放心，他们看中的就是你的吹牛技巧，如果进去你发现自己是最牛的，那才最绝望。大家有没有经历过这种入职前的焦虑？可以评论区分享一下。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道高频面试题「最长公共子序列」。
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如， "ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
举个例子：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
思路解析
本题是经典的二维动态规划问题，要找到解决动态规划问题的两个突破点：推导出状态转移公式和边界条件处理。
首先定义dp[i][j]为text1的[0, i)区间和text2的[0, j)区间的最长公共子序列。[0, i)区间的长度为i，[0, j)区间的长度为j。
接下来我们来看两种情况下的子问题分解：
text1[i-1] == text2[j-1]，这个时候text1的[0, i)区间和text2的[0, j)区间上的最长公共子序列就变成了text1的[0, i-1)区间和text2的[0, j-1)区间上的最长公共子序列加1。即dp[i][j] = dp[i-1][j-1] + 1。
text1[i-1] != text2[j-1]，这个时候text1的[0, i)区间和text2的[0, j)区间上的最长公共子序列就变成了text1的[0, i-1)区间和text2的[0, j)区间上的最长公共子序列 以及text1的[0, i)区间和text2的[0, j-1)区间上的最长公共子序列 中比较长的一个。即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
由于整个推导过程是自下而上的，在求dp[i][j]的时候dp[i-1][j-1]，dp[i][j-1]，dp[i-1][j]都是已经推出结果的。
所以状态转移公式为：
对于边界条件，很明显dp[i][0] = 0且dp[j][0] = 0。
text1 = "abcde"， text2 = "ace"的推导过程如下图：
最终dp[5][3] = 3，最长公共子序列的长度为3。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int text1_len = text1.length();
int text2_len = text2.length();
//定义二维dp数组，并初始化，dp[i][0]=0 dp[0][j]=0
vector<vector<int>> dp(text1_len + 1, vector<int>(text2_len + 1, 0));
for (int i = 0; i < text1_len; ++i) {
for (int j = 0; j < text2_len; ++j) {
//text1[i] == text2[j]
if (text1[i] == text2[j]) {
//状态转移公式
dp[i+1][j+1] = dp[i][j] + 1;
//text1[i] != text2[j]
} else {
//状态转移公式
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
}
}
}
return dp[text1_len][text2_len];
}
};
python代码
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
text1_len = len(text1)
text2_len = len(text2)
# 初始化一个二维dp数组，全部初始化为0
dp = [[0] * (text2_len + 1) for _ in range(text1_len + 1)]
# 填充dp数组
for i in range(text1_len):
for j in range(text2_len):
if text1[i] == text2[j]:
# 如果当前字符相等，那么dp[i+1][j+1]等于dp[i][j] + 1
dp[i+1][j+1] = dp[i][j] + 1
else:
# 如果当前字符不相等，取dp[i+1][j]和dp[i][j+1]的较大值
dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
# 返回dp[text1_len][text2_len]，即最长公共子序列的长度
return dp[text1_len][text2_len]
复杂度分析
时间复杂度： O(mn) ，其中m为text1的长度，n为text2的长度。
空间复杂度： O(mn) ，其中m为text1的长度，n为text2的长度。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
