⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【汽水瓶】和【查找两个字符串a,b中的最长公共子串】，展示语言java。

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

⭐️汽水瓶⭐️

🔐题目详情

某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。

小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。

数据范围：输入的正整数满足 1≤n≤100

注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。

输入描述：

输入文件最多包含 10 组测试数据，每个数据占一行，仅包含一个正整数 n（ 1<=n<=100 ），表示小张手上的空汽水瓶数。n=0 表示输入结束，你的程序不应当处理这一行。

输出描述：

对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。

示例1

输入：

3
10
81
0

输出：

1
5
40

说明：

样例 1 解释：用三个空瓶换一瓶汽水，剩一个空瓶无法继续交换
样例 2 解释：用九个空瓶换三瓶汽水，剩四个空瓶再用三个空瓶换一瓶汽水，剩两个空瓶，向老板借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板    

题目链接：汽水瓶

💡解题思路

基本思路： 模拟题

解题思路：
不妨记空瓶数量为n，这n个空瓶能兑换的饮料数为cur，并且题目告诉我们可以借一个空瓶子，但是需要归还，在n为2的时候我们可以借用1个空瓶子，刚好能换一瓶饮料，并且换完的饮料喝完的空瓶子刚好还给老板。

根据题意，每3个空瓶子可以换一瓶饮料，则每轮的cur=n/3，喝完之后空瓶子数量n=cur + n % 3，如果n=2，可以借一个瓶子换一瓶新饮料，如果瓶子的数量小于2则无法再继续兑换饮料，循环往复将每一轮的饮料数加起来就是能够喝到的饮料。

🔑源代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n == 0) break;
            int ans = 0;
            
            while (n >= 2) {
                //当最后空瓶子只有两个需要借
                if (n == 2) {
                    ans += 1;
                    break;
                }
                int cur = n / 3;
                ans += cur;
                n = cur + n % 3;
            }
            System.out.println(ans);
        } 
    }   
}

🌱总结

本题为简单模拟题，掌握饮料与空瓶子的换算关系即可。

⭐️查找两个字符串a,b中的最长公共子串⭐️

🔐题目详情

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

数据范围：字符串长度1≤length≤300

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

输入描述：

输入两个字符串

输出描述：

返回重复出现的字符

示例1

输入：

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出：

jklmnop

题目链接：查找两个字符串a,b中的最长公共子串

💡解题思路

基本思路： 动态规划
解题思路：

假设第一字符串为a串，第二个字符串为b串。

题目需要我们输出最长的公共子串，如果长度相同则优先输出源字符串长度较小的那一个，所以我们在求最长公共子串之前，需要找到字符串较小的那一个字符串，这个很简单，我们让a串永远最短，如果a串比b串长，则交换。

本题的思路就是使用动态规划来计算最长公共子串长度，由于我们还需要输出具体的子串，所以我们在求最长长度的同时，不妨将该子串的起始下标记录下来，具体如何记录，我们定义状态以及推导出状态转移方程再来讨论。

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

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

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

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

综上所述：

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

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

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

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

在进行动态规划的同时，我们使用一个变量maxLen来更新最长的公共子串长度。

我们状态定义是：定义 $f[i][j]$为字符串 $a$以第 $i$个字符结尾与字符串 $b$以第 $j$个字符结尾的最长公共子串的长度。
所以我们在更新最长度maxLen的时候，得到的子串最后一个字符是字符串中的第i个字符，对应数组下标为i-1，因此我们可以求得子串起始下标 $start=i - 1 - maxLen + 1 = i - maxLen$。

最后我们截取较短字符串a中[start,start+maxLen)间的字符串输出即可。

🔑源代码

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();
        int n = a.length();
        int m = b.length();
        //永远让a字符串更短
        if (m < n) {
            String tmp = a;
            a = b;
            b = tmp;
        }
        char[] as = a.toCharArray();
        char[] bs = b.toCharArray();
        n = as.length;
        m = bs.length;
        //状态定义：f(i,j) a字符串中以第i个字符结尾，b字符串以第j个字符结尾，最长公共子串的长度
        int[][] f = new int[n + 1][m + 1];
        //确定初始状态 f[0][0] = 0
        //最长公共子串长度
        int maxLen = 0;
        //起始下标
        int st = 0;
        String ans  = "";
        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;
                }
                if (maxLen < f[i][j]) {
                    maxLen = f[i][j];
                    st = i - maxLen;
                }
            }
        }
        ans = a.substring(st, st + maxLen);
        System.out.println(ans);
    }
}

🌱总结

本题为动态规划应用题，重点就是能够定义出一个合理的状态，推导出合理的状态转移方程，同时由于题目需要输出在较短字符串上面的最长公共子串，在求最长公共子串长度的同时需要计算公共子串在较短字符串的开始下标或最后一个字符的下标，通过下标和长度在较短的字符串中截取最长公共子串并输出。