【c++笔试强训】（第三十一篇）

目录

最⻓回⽂⼦序列（动态规划-区间dp）

题目解析

讲解算法原理

编写代码

添加字符（字符串）

题目解析

讲解算法原理

编写代码

---

最⻓回⽂⼦序列（动态规划-区间dp）

题目解析

1.题目链接：最长回文子序列_牛客题霸_牛客网

2.题目描述

描述

给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。

注：回文序列是指这个序列无论从左读还是从右读都是一样的。

本题中子序列字符串任意位置删除k（len(s)>=k>=0）个字符后留下的子串。

数据范围：字符串长度满足 1 \le n \le 10001≤n≤1000

进阶：空间复杂度 O(n^2)O(n2) ， 时间复杂度 O(n^2)O(n2)

输入描述：

输入一个字符串

输出描述：

输出最长回文子序列

示例1

输入：

abccsb

输出：

4

说明：

分别选取第2、3、4、6位上的字符组成“bccb”子序列是最优解      

示例2

输入：

abcdewa

输出：

3

说明：

分别选取第一个和最后一个a，再取中间任意一个字符就是最优解   

讲解算法原理

解法：
算法思路：
基础的区间dp问题：
1. 状态表⽰： dp[i][j] 表⽰：字符串 [i, j] 范围内的最⻓回⽂⼦序列的⻓度；2. 状态转移⽅程：
◦ 当 i == j 的时候，只有⼀个字符，⻓度为1；
◦ 当 i < j 的时候，分情况讨论：
▪ s[i] == s[j]：dp[i][j] = dp[i + 1][j - 1];▪ s[i] != s[j]：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])；
3. 返回值： dp[0][n - 1] 。

编写代码

c++算法代码：

#include <iostream>
#include <string>
using namespace std;
int dp[1010][1010];
int main()
{string s;cin >> s;int n = s.size();for(int i = n - 1; i >= 0; i--){dp[i][i] = 1; for(int j = i + 1; j < n; j++) { if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); }}cout << dp[0][n - 1] << endl;return 0;
}

java算法代码：

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in); char[] s = in.next().toCharArray(); int n = s.length; int[][] dp = new int[n][n];for(int i = n - 1; i >= 0; i--){dp[i][i] = 1; for(int j = i + 1; j < n; j++) { if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); }}System.out.println(dp[0][n - 1]);}
}

添加字符（字符串）

题目解析

1.题目链接：添加字符_牛客笔试题_牛客网

2.题目描述

牛牛手里有一个字符串A，羊羊的手里有一个字符串B，B的长度大于等于A，所以牛牛想把A串变得和B串一样长，这样羊羊就愿意和牛牛一起玩了。
而且A的长度增加到和B串一样长的时候，对应的每一位相等的越多，羊羊就越喜欢。比如"abc"和"abd"对应相等的位数为2，为前两位。
牛牛可以在A的开头或者结尾添加任意字符，使得长度和B一样。现在问牛牛对A串添加完字符之后，不相等的位数最少有多少位？

输入描述:

第一行为字符串A，第二行为字符串B，A的场地小于等于B的长度，B的长度小于等于50.字符均为小写字母。输出描述:

输出一个整数表示A串添加完字符之后，不相等的位数最少有多少位？

示例1

输入

abe
cabc

输出

1

讲解算法原理

解法：
算法思路：
枚举所有字符串a与字符串b相对应的位置。

编写代码

c++算法代码：

#include <iostream>
#include <string>
using namespace std;
string a, b;
int main()
{cin >> a >> b;int m = a.size(), n = b.size(); int ret = m;for(int i = 0; i <= n - m; i++) // 枚举 b 的起始位置 {int tmp = 0; for(int j = 0; j < m; j++) { if(a[j] != b[i + j]) { tmp++; }}ret = min(tmp, ret);}cout << ret << endl;return 0;
}

java算法代码：

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in); char[] a = in.next().toCharArray(); char[] b = in.next().toCharArray(); int m = a.length, n = b.length; int ret = m;for(int i = 0; i <= n - m; i++) // 枚举 b 的起始位置 {int tmp = 0; for(int j = 0; j < m; j++) { if(a[j] != b[i + j]) { tmp++; }}ret = Math.min(ret, tmp);}System.out.println(ret);}
}