【算法刷题日记之本手篇】字符串反转与公共子串计算
【摘要】 本篇文章介绍来自牛客试题广场的两道题题解,分别为【字符串反转】和【公共子串计算】,展示语言java。
⭐️前面的话⭐️
本篇文章介绍来自[牛客试题广场]的两道题题解,分别为【字符串反转】和【公共子串计算】,展示语言java。
📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创!
📆首发时间:🌴2022年8月31日🌴
✉️坚持和努力一定能换来诗与远方!
💭参考书籍:📚《算法》,📚《算法导论》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
⭐️字符串反转⭐️
🔐题目详情
接受一个只包含小写字母的字符串,然后输出该字符串反转后的字符串。(字符串长度不超过1000)
输入描述:
输入一行,为一个只包含小写字母的字符串。
输出描述:
输出该字符串反转后的字符串。
示例1
输入:
abcd
输出:
dcba
题目来源:牛客网,注册才能刷题哦!
题目链接: 字符串反转
💡解题思路
基本思路: 模拟
解题思路:
思路1:使用一个左指针从第一个字符开始,向右走,使用一个右指针从最后一个字符开始,向左走。最终两指针在中间相遇,所以的字符就逆置了。
思路2:直接逆序输出字符串,就是从后往前遍历。
🔑源代码
思路1:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
char[] cs = str.toCharArray();
int right = cs.length - 1;
int left = 0;
while (left < right) {
char tmp = cs[left];
cs[left++] = cs[right];
cs[right--] = tmp;
}
for (int i = 0; i < cs.length; i++) {
System.out.print(cs[i]);
}
}
}
思路2:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
char[] cs = str.toCharArray();
for (int i = cs.length - 1; i >= 0; i--) {
System.out.print(cs[i]);
}
}
}
🌱总结
本题为字符串模拟题,难度不大。
⭐️公共子串计算⭐️
🔐题目详情
给定两个只包含小写字母的字符串,计算两个字符串的最大公共子串的长度。
注:子串的定义指一个字符串删掉其部分前缀和后缀(也可以不删)后形成的字符串。
数据范围:字符串长度:1≤s≤150
进阶:时间复杂度:O(n^3^) ,空间复杂度:O(n)
输入描述:
输入两个只包含小写字母的字符串
输出描述:
输出一个整数,代表最大公共子串的长度
示例1
输入:
asdfas
werasdfaswer
输出:
6
题目来源:牛客网,注册才能刷题哦!
题目链接:公共子串计算
💡解题思路
基本思路: 动态规划
解题思路:
假设第一字符串为a
串,第二个字符串为b
串。
状态定义: 定义 为字符串 以第 个字符结尾与字符串 以第 个字符结尾的最长公共子串的长度。
确定初始状态: 当 时,表示其中有一个字符串是空字符串,得到的最长公共子串一定为 。
状态转移方程:
情况1:如果
字符串的第
个字符与
字符串的第
个字符相等,则最长公共子串长度为
字符串中以第
字符结尾的字符串与
字符串中以第
个字符结尾到的字符串的最长公共子串长度加上
。
即:
情况2:如果 字符串的第 个字符与 字符串的第 个字符不相等,则最长公共子串长度就是 ,即 。
综上所述:
字符串的第 个字符与 字符串的第 个字符相等:
如果 字符串的第 个字符与 字符串的第 个字符不相等:
🔑源代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
String b = sc.nextLine();
char[] as = a.toCharArray();
char[] bs = b.toCharArray();
int n = as.length;
int m = bs.length;
//状态定义
int[][] f = new int[n + 1][m + 1];
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (as[i - 1] == bs[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
}
ans = f[i][j] > ans ? f[i][j] : ans;
}
}
System.out.println(ans);
}
}
🌱总结
本题为字符串匹配类的动态规划问题,本题的关键就是抽象出状态的定义:定义 为字符串 以第 个字符结尾与字符串 以第 个字符结尾的最长公共子串的长度。然后跟该定义去推导状态转移方程。
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)