笔试——Day30

第一题

题目

爱吃素

思路

模拟： 判断a * b是否为质数，开long long避免相乘溢出

代码

第二题

题目：

相差不超过k的最多数

思路

排序 + 滑动窗口

排完序后，判断左右边界的差值是否大于k，大于的话，左边界加加；

代码

第三题

题目：

最长公共子序列(一)

思路

动态规划

状态表示：dp[i][j]-> s1区间[0, i]和 s2区间[0, j]```的最长公共子序列

状态转移方程：
s1[i] == s2[j] -> dp[i][j] = dp[i - 1][j - 1] + 1;
s1[i] != s2[j] -> dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

代码