刷题_19：汽水瓶 and 查找两个字符串a,b中的最长公共子串

拼搏现实的明天。 2023-09-30 21:07 7阅读 0赞

### 一.汽水瓶 ###

**题目链接：**

> [汽水瓶][Link 1]

**题目描述：**

> **某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。  
> 小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。  
> 数据范围：输入的正整数满足 1≤n≤100  
> 注意：本题存在多组输入。输入的 0 表示输入结束，并不用输出结果。**

**输入描述：**

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

**输出描述：**

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

**示例1：**

> **输入：  
> 3  
> 10  
> 81  
> 0  
> 输出：  
> 1  
> 5  
> 40  
> 说明：  
> 样例 1 解释：用三个空瓶换一瓶汽水，剩一个空瓶无法继续交换  
> 样例 2 解释：用九个空瓶换三瓶汽水，剩四个空瓶再用三个空瓶换一瓶汽水，剩两个空瓶，向老板借一个空瓶再用三个空瓶换一瓶汽水喝完得一个空瓶还给老板**

**个人总结：**

> **模拟兑换过程即可，题干中说到可以向老板借瓶子，但必须归还，考虑到最后我们剩余的瓶子只有0个、1个、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) {
        
                    System.out.println(calc(n));
                }
            }
        }
    
        //计算最多可以喝多少汽水
        public static int calc(int n) {
        
            int res = 0;
            while (n >= 3) {
        
                int buy = n / 3;
                res += buy;
                n = buy + n % 3;
            }
            if (n == 2) {
        
                res += 1;
            }
            return res;
        }
    }

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

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

**题目链接：**

> [查找两个字符串a,b中的最长公共子串][a_b]

**题目描述：**

> **查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。  
> 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！  
> 数据范围：字符串长度1≤length≤300  
> 进阶：时间复杂度：O(n^3) ，空间复杂度：O(n)**

**输入描述：**

> **输入两个字符串**

**输出描述：**

> **返回重复出现的字符**

**示例1：**

> **输入：  
> abcdefghijklmnop  
> abcsafjklmnopqrstuvw  
> 输出：  
> jklmnop**

**个人总结：**

> **本题是一个动态规划题，我们定义一个dp\[i\]\[j\]：以i为结尾的s子串和以j为结尾的p子串的最长公共子串，如果i下标对应的字符等于j下标对应的字符（`s.charAt(i - 1) == p.charAt(j - 1)`），则`dp[i][j] = dp[i - 1][j - 1] + 1;`并且在此时我们更新一下最大长度max和最大长度的起始下标，若i下标对应的字符不等于j下标对应的字符（`s.charAt(i - 1) ！= p.charAt(j - 1)`），那我们令`dp[i][j] = 0;`至于为什么？可以回想我们对dp\[i\]\[j\]的定义，如果二者不相等，那以它为结尾的子串怎么会有公共长度呢？还有一点是题目要求我们若有多个长度相等的子串，则输出最短的串中最先出现的，所以我默认s是最短串，如果s不是 ，就交换二者。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            String p = sc.nextLine();
            //因为题目要求我们若有多个长度相等的子串 则输出最短的串中最先出现的
            //所以我默认s是最短串 方便后续写 如果s不是 就交换二者
            if (s.length() > p.length()) {
        
                String tmp = s;
                s = p;
                p = tmp;
            }
            System.out.println(getMaxlenString(s, p));
        }
    
        //获得最长公共子串
        public static String getMaxlenString(String s, String p) {
        
            int lenS = s.length();
            int lenP = p.length();
            //dp[i][j]：以i为结尾的s子串和以j为结尾的p子串的最长公共子串
            int[][] dp = new int[lenS + 1][lenP + 1];
            //最长公共子串的起始下标及长度
            int startIdx = -1;
            int max = 0;
            for (int i = 1; i <= lenS; i++) {
        
                for (int j = 1; j <= lenP; j++) {
        
                    if (s.charAt(i - 1) == p.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        if (dp[i][j] > max) {
        
                            max = dp[i][j];
                            startIdx = i - dp[i][j];
                        }
                    } else {
        
                        dp[i][j] = 0;
                    }
                }
            }
            return s.substring(startIdx, startIdx + max);
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/fe298c55694f4ed39e256170ff2c205f
[a_b]: https://www.nowcoder.com/questionTerminal/181a1a71c7574266ad07f9739f791506