2023荣耀校招机试(java&python&C++)饭店楼层公共子序列
题目描述
华华酒店因许多重复的饭店同时出现在一响装修美观,现需对1.2层的饭店进行管理。需找到两层之间都出现过,且出现顺序都一致的饭馆的个数。 例管理规则每一层用一个字符串表示。每间饭店用 (a-z”) 任意个字母表示,同层饭店的字母可能重复出现,不同层字母顺序不一致。现需找到两层之间都出现过,且出现顺序都一致的饭店的个数。例如:第一层拥有的饭店为“abcbdab”,为7间饭店,第二层拥有的饭店为“bcdbda”,为6间饭店。找到的结果应该为“bcbda”5间饭店。
输入描述
两个字符串,字符串长度均小于等于20
输出描述
最长的共有饭店的个数
用例
输入 | abcbdab bcdbda |
输出 | 5 |
思路
这是一个求解最长公共子序列(LCS)的问题,可以使用动态规划求解。
我们设 dp[i][j] 表示第一个字符串前 i 个字符和第二个字符串前 j 个字符的最长公共子序列长度,则有以下状态转移方程:
其中 s1和 s2 分别为两个字符串。
最终的答案即为 dp[m][n],其中 m 和 n 分别为两个字符串的长度。
时间复杂度为 O(mn),空间复杂度为 O(mn)。
题解代码
python
s1 = input().strip()
s2 = input().strip()
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[m][n])
# abcbdab
# bcdbda
C++
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 读入两个字符串
string s1, s2;
getline(cin, s1);
getline(cin, s2);
// 计算两个字符串的长度
int m = s1.length();
int n = s2.length();
// 初始化二维数组 dp,其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列长度
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// 动态规划计算最长公共子序列长度
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1]) { // 如果两个字符相同,那么当前字符可以加入公共子序列中
dp[i][j] = dp[i-1][j-1] + 1; // 公共子序列长度加 1
} else { // 如果两个字符不同,那么当前字符不可能同时出现在公共子序列中,需要考虑哪个字符串中的字符应该被舍弃
dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // 取 s1 的前 i-1 个字符和 s2 的前 j 个字符的最长公共子序列长度,
// 和 s1 的前 i 个字符和 s2 的前 j-1 个字符的最长公共子序列长度的较大值
}
}
}
// 输出最长公共子序列长度
cout << dp[m][n] << endl;
return 0;
}
java
import java.util.*;
public class t1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s1 = scanner.nextLine();
String s2 = scanner.nextLine();
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
System.out.println(dp[m][n]);
}
}