【Java版oj】day19汽水瓶、查找两个字符串a,b中的最长公共子串

爱被打了一巴掌 2024-03-24 09:23 13阅读 0赞

**目录**

一、汽水瓶

（1）原题再现

（2）问题分析

（3）完整代码

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

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、汽水瓶 ##
> 
> ### （1）原题再现 ###
> 
> [汽水瓶\_牛客题霸\_牛客网][Link 1]
> 
> **描述**
> 
> 某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。
> 
> 注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。
> 
> **输入描述：**
> 
> 输入文件最多包含 10 组测试数据，每个数据占一行，仅包含一个正整数 n（ 1<=n<=100 ），表示小张手上的空汽水瓶数。n=0 表示输入结束，你的程序不应当处理这一行。
> 
> **输出描述：**
> 
> 对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。
> 
> **示例1**
> 
> 输入：
> 
> 3
> 
> 10
> 
> 81
> 
> 0
> 
> 输出：
> 
> 1
> 
> 5
> 
> 40
> 
> 说明：
> 
> 样例 1 解释：用三个空瓶换一瓶汽水，剩一个空瓶无法继续交换
> 
> 样例 2 解释：用九个空瓶换三瓶汽水，剩四个空瓶再用三个空瓶换一瓶汽水，剩两个空瓶，向老板借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板
> 
> ### （2）问题分析 ###
> 
> 本题其实不难，把逻辑分析一下就很容易写出代码。由题目可知三个空瓶换一瓶汽水，**剩下两瓶**，可以问老板**借一个空瓶**，但是得还给老板。如果剩下一个或者没有剩下就借不了空瓶。
> 
> 定义空瓶数emptyBottle、借的空瓶数borrow、换得的汽水数change。**循环的条件是emptyBottle>1**，如果空瓶大于等于三就可以不断换汽水，换得的汽水数等于空瓶数/3，空瓶数等于换得的汽水数+不够换的空瓶数；如果空瓶数等于2，代表可以向老板借空瓶数，空瓶数加一，汽水数加一。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     /*
>      * 汽水
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNextInt()) {
>                 int emptyBottle = sc.nextInt();
>                 if (emptyBottle != 0) {
>                     int ans = countBottle(emptyBottle);
>                     System.out.println(ans);
>                 }
>             }
>         }
>         public static int countBottle(int emptyBottle) {
>             int borrow = 0; //借空瓶数
>             int change = 0; //换汽水数
>             while (emptyBottle > 1) {
>                 if (emptyBottle >= 3) {
>                     change += emptyBottle / 3;
>                     emptyBottle = emptyBottle / 3 + emptyBottle % 3;
>                 }
>                 if (emptyBottle == 2) {
>                     borrow++;
>                     emptyBottle++;
>                 }
>             }
>             return change;
>         }
>     }
> 
> ![0a6c31be0a2a40f8b4c422360f1375e7.png][]

> ## 二、查找两个字符串a,b中的最长公共子串 ##
> 
> ### （1）原题再现 ###
> 
> [查找两个字符串a,b中的最长公共子串\_\_牛客网][a_b]
> 
> 查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
> 
> 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！
> 
> **输入描述:**
> 
> 输入两个字符串
> 
> **输出描述:**
> 
> 返回重复出现的字符
> 
> **示例1**
> 
> 输入
> 
> abcdefghijklmnop
> 
> abcsafjklmnopqrstuvw
> 
> 输出
> 
> jklmnop
> 
> ### （2）问题分析 ###
> 
> 本题其实不难，可以用两种放式，动态规划和遍历。因为题目要求输出在较短串中最先出现的那个，所以我们一开始可以处理一下这两个号字符串，str1为较短串，str2为较长串。
> 
>  **动态规划：**就和之前我讲解的那几篇解法一样。先找初始状态，再列出状态方程，最后返回目标位置。dp\[i\]\[j\]表示较短串在i位置，较长串在j位置时的子串长度。str1.charAt(i - 1) == str2.charAt(j - 1)如果该位置字符相等，则公共子串长度+1，在于最大公共子串长度比较，看是否要更新。 **注意：为什么是i-1和j-1，因为字符串下标是从0开始的，我定义的数组0行0列是初始值，第一个字符是从下标1开始的。**  
> 简单举个例子，字符串abc和字符串abd，dp\[i\]\[j\]存储的内容就如下表所示。
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td></td> 
>    <td>""</td> 
>    <td>"a"</td> 
>    <td>"ab"</td> 
>    <td>"abc"</td> 
>   </tr> 
>   <tr> 
>    <td>""</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>0</td> 
>    <td>0</td> 
>   </tr> 
>   <tr> 
>    <td>"a"</td> 
>    <td>0</td> 
>    <td>1</td> 
>    <td>1</td> 
>    <td>1</td> 
>   </tr> 
>   <tr> 
>    <td>"ab"</td> 
>    <td>0</td> 
>    <td>1</td> 
>    <td>2</td> 
>    <td>2</td> 
>   </tr> 
>   <tr> 
>    <td>"abd"</td> 
>    <td>0</td> 
>    <td>1</td> 
>    <td>2</td> 
>    <td>2</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> **遍历：**对较短串进行两层for循环，找出较短串中所有字符组合的可能，判断较长串是否包含这个子串，如果包含则与之前存下的最大值比较，看是否需要更新。  
> 题目要求返回的最大公共子串，所以定义一个start变量表示最长公共子串开始的下标位置。max表示最大公共子串的长度。返回值的下标就是start，start+max。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     
>     /*
>      查找两个字符串a,b中的最长公共子串
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNext()) {
>                 String str1 = sc.nextLine();
>                 String str2 = sc.nextLine();
>                 int len1 = str1.length(); //较短
>                 int len2 = str2.length(); //较长
>     
>                 //交换
>                 if (len1 > len2) {
>                     String tmp = str1;
>                     str1 = str2;
>                     str2 = tmp;
>                 }
>     //          System.out.println(solve(str1, str2));
>                 System.out.println(solve1(str1, str2));
>     
>             }
>         }
>         //动归
>         public static String solve(String str1, String str2) {
>             int [][]dp = new int[str1.length() + 1][str2.length() + 1];
>             int max = 0, start = 0;
>             for (int i = 1; i < str1.length() + 1; i++) {
>                 for (int j = 1; j < str2.length() + 1; j++) {
>                     if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
>                         dp[i][j] = dp[i - 1][j - 1] + 1;
>                         if (dp[i][j] > max) {
>                             max = dp[i][j];
>                             start = i - max;
>                         }
>                     }
>                 }
>             }
>             return str1.substring(start, start + max);
>         }
>     
>         //遍历
>         public static String solve1(String str1, String str2) {
>             int start = 0;
>             int max = 0;
>             for (int i = 0; i < str1.length(); i++) {
>                 for (int j = i + 1; j < str1.length(); j++) {
>                     if (str2.contains(str1.substring(i, j + 1))) {
>                         if (str1.substring(i, j + 1).length() > max) {
>                             max = str1.substring(i, j + 1).length();
>                             start = i;
>                         }
>                     }
>                 }
>             }
>             return str1.substring(start, start + max);
>         }
>     }
> 
> ![07589a4c22d041c29bdbfc8264e8103b.png][]

--------------------

![a630b45356694c68807979686f5a503a.png][]

[Link 1]: https://www.nowcoder.com/practice/fe298c55694f4ed39e256170ff2c205f
[0a6c31be0a2a40f8b4c422360f1375e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/0a9d52eb06cd4e1aa26b61d897535a94.png
[a_b]: https://www.nowcoder.com/questionTerminal/181a1a71c7574266ad07f9739f791506?toCommentId=15599609
[07589a4c22d041c29bdbfc8264e8103b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2343497336d547069a146c327e58000f.png
[a630b45356694c68807979686f5a503a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7b32704749d742a79b7d903096df74ad.png