【算法刷题日记之本手篇】字符串反转与公共子串计算

举报
未见花闻 发表于 2022/08/31 21:40:02 2022/08/31
821 0 0
【摘要】 本篇文章介绍来自牛客试题广场的两道题题解,分别为【字符串反转】和【公共子串计算】,展示语言java。

⭐️前面的话⭐️

本篇文章介绍来自[牛客试题广场]的两道题题解,分别为【字符串反转】和【公共子串计算】,展示语言java。

📒博客主页:未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创!
📆首发时间:🌴2022年8月31日🌴
✉️坚持和努力一定能换来诗与远方!
💭参考书籍:📚《算法》,📚《算法导论》
💬参考在线编程网站:🌐牛客网🌐力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
🍭作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!

⭐️字符串反转⭐️

🔐题目详情

接受一个只包含小写字母的字符串,然后输出该字符串反转后的字符串。(字符串长度不超过1000)

输入描述:

输入一行,为一个只包含小写字母的字符串。

输出描述:

输出该字符串反转后的字符串。

示例1

输入:

abcd

输出:

dcba

题目来源:牛客网,注册才能刷题哦!
题目链接: 字符串反转

💡解题思路

基本思路: 模拟
解题思路:
思路1:使用一个左指针从第一个字符开始,向右走,使用一个右指针从最后一个字符开始,向左走。最终两指针在中间相遇,所以的字符就逆置了。
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串。

状态定义: 定义 f [ i ] [ j ] f[i][j] 为字符串 a a 以第 i i 个字符结尾与字符串 b b 以第 j j 个字符结尾的最长公共子串的长度。

确定初始状态: i = 0 j = 0 i=0或j=0 时,表示其中有一个字符串是空字符串,得到的最长公共子串一定为 0 0

状态转移方程:
情况1:如果 a a 字符串的第 i i 个字符与 b b 字符串的第 j j 个字符相等,则最长公共子串长度为 a a 字符串中以第 i 1 i-1 字符结尾的字符串与 b b 字符串中以第 j 1 j-1 个字符结尾到的字符串的最长公共子串长度加上 1 1
即: f [ i ] [ j ] = f [ i 1 ] [ j 1 ] + 1 f[i][j]=f[i-1][j-1]+1

情况2:如果 a a 字符串的第 i i 个字符与 b b 字符串的第 j j 个字符不相等,则最长公共子串长度就是 0 0 ,即 f [ i ] [ j ] = 0 f[i][j]=0

综上所述:

a a 字符串的第 i i 个字符与 b b 字符串的第 j j 个字符相等:

f [ i ] [ j ] = f [ i 1 ] [ j 1 ] + 1 ,其中 i > 0 , j > 0 f[i][j]=f[i-1][j-1]+1,其中i>0,j>0

如果 a a 字符串的第 i i 个字符与 b b 字符串的第 j j 个字符不相等:

f [ i ] [ j ] = 0 f[i][j]=0

🔑源代码

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);
    }
}

🌱总结

本题为字符串匹配类的动态规划问题,本题的关键就是抽象出状态的定义:定义 f [ i ] [ j ] f[i][j] 为字符串 a a 以第 i i 个字符结尾与字符串 b b 以第 j j 个字符结尾的最长公共子串的长度。然后跟该定义去推导状态转移方程。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。