【Java版oj】day18统计每个月兔子的总数、字符串通配符

心已赠人 2024-03-24 09:14 70阅读 0赞

**目录**

一、统计每个月兔子的总数

（1）原题再现

（2）问题分析

（3）完整代码

二、字符串通配符

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、统计每个月兔子的总数 ##
> 
> ### （1）原题再现 ###
> 
> [统计每个月兔子的总数\_牛客题霸\_牛客网][Link 1]
> 
> **描述**
> 
> 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
> 
> 例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
> 
> 一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
> 
> **输入描述：**
> 
> 输入一个int型整数表示第n个月
> 
> **输出描述：**
> 
> 输出对应的兔子总数
> 
> 示例1
> 
> 输入：
> 
> 3
> 
> 输出：
> 
> 2
> 
> ### （2）问题分析 ###
> 
> 我们把每个月兔子数列出来，分别是1、1、2、3、5、8、13、21.......到这里其实结果已经出来了，这是一个斐波那契数列，后面的数等于前面两个数相加，这也是最简单的动态规划。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     /*
>      * 统计每个月兔子的总数
>      */
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner (System.in);
>             int n = sc.nextInt();
>             int []countNum = new int [n + 1];
>             countNum[0] = 0;
>             countNum[1] = 1;
>             countNum[2] = 1;
>             for (int i = 3; i < n + 1; i++) {
>                 countNum[i] = countNum[i - 1] + countNum[i - 2];
>             }
>             System.out.println(countNum[n]);
>         }
>     }
> 
> ![ae8dd51a2a2640f2b1b82a38614f69ec.png][]

> ## 二、字符串通配符 ##
> 
> [字符串通配符\_牛客题霸\_牛客网][Link 2]
> 
> ### （1）原题再现 ###
> 
> **描述**
> 
> 问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。  
> 要求：  
> 实现如下2个通配符：  
> \*：匹配0个或以上的字符（注：能被\*和?匹配的字符仅由英文字母和数字0到9组成，下同）  
> ？：匹配1个字符
> 
> 注意：匹配时不区分大小写。
> 
> **输入：**  
> 通配符表达式；  
> 一组字符串。
> 
> **输出：**
> 
> 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
> 
> 数据范围：字符串长度：1\\le s\\le 100\\1≤s≤100
> 
> 进阶：时间复杂度：O(n^2)\\O(n2) ，空间复杂度：O(n)\\O(n)
> 
> **输入描述：**
> 
> 先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
> 
> **输出描述：**
> 
> 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
> 
> **示例1**
> 
> **输入：**
> 
> te?t\*.\*
> 
> txt12.xls
> 
> **输出：**
> 
> false
> 
> **示例2**
> 
> **输入：**
> 
> z
> 
> zz
> 
> **输出：**
> 
> false
> 
> **示例3**
> 
> **输入：**
> 
> pq
> 
> pppq
> 
> **输出：**
> 
> false
> 
> **示例4**
> 
> 输入：
> 
> \*\*Z
> 
> 0QZz
> 
> **输出：**
> 
> true
> 
> **示例5**
> 
> **输入：**
> 
> ?\*Bc\*?
> 
> abcd
> 
> **输出：**
> 
> true
> 
> **示例6**
> 
> **输入：**
> 
> h\*?\*a
> 
> h\#a
> 
> **输出：**
> 
> false
> 
> **说明：**
> 
> 根据题目描述可知能被\*和?匹配的字符仅由英文字母和数字0到9组成，所以?不能匹配\#，故输出false。
> 
> **示例7**
> 
> **输入：**
> 
> p\*p\*qp\*\*pq\*p\*\*p\*\*\*ppq  
> pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp
> 
> **输出：**
> 
> false
> 
> ### （2）问题分析 ###
> 
> 这道题有点困难，我选择的是DFS深度优先搜索算法，以递归的方式解决问题。根据通配符表达式，我们可以**把通配符分成三种**。第一种就是**普通字符**，一次只能匹配相同的一个字符；第二种是**？**，它与普通通配符差不多是一致的，一次也只能匹配一个字符；第三种是**\***，一次能匹配0个或多个字符。这里我们要分**三种情况**返回，第一种情况匹配0个字符：通配符字符串向后走一位，待匹配的不动；第二种情况匹配1个字符：两个字符串同时向后走一位；第三种情况匹配多个字符：通配符字符不动，普通字符串往后走多位，直到普通字符与通配字符的下一位的普通字符（不是\*）相等时返回。
> 
>  **返回条件：**当两个字符串同步走到尾短端，返回true。 只有两个字符串不是同步走到结尾的，返回false。两个普通字符但是不相等的时候，返回false。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     public class Main {
>         public static void main(String[] args) {
>             Scanner in = new Scanner(System.in);
>             while (in.hasNext()) {
>                 String str = in.nextLine().toLowerCase();
>                 String str1 = in.nextLine().toLowerCase();
>                 System.out.println(isBoolean(str, str1, 0, 0));
>             }
>         } static boolean isBoolean(String str, String str1, int n, int m) {
>             if (str.length() == n && str1.length() == m) {
>                 return true;
>             }
>             if (str.length() == n || str1.length() == m) {
>                 return false;
>             }
>             if (str.charAt(n) == str1.charAt(m)) {
>                 return isBoolean(str, str1, n + 1, m + 1);
>             }
>             if (str.charAt(n) == '*' && n + 1 != str.length() && str.charAt(n + 1) == '*') {
>                 return isBoolean(str, str1, n + 1, m);
>             }//有连续的*，走到最后一个*的位置
>             if (str.charAt(n) == '?' && ((str1.charAt(m) >= '0' && str1.charAt(m) <= '9') ||(str1.charAt(m) >= 'a' && str1.charAt(m) <= 'z'))) {
>                 return isBoolean(str, str1, n + 1, m + 1);
>             } else if (str.charAt(n) == '*' && ((str1.charAt(m) >= '0' &&str1.charAt(m) <= '9') || (str1.charAt(m) >= 'a' && str1.charAt(m) <= 'z'))) {
>                 return isBoolean(str, str1, n, m + 1) || isBoolean(str, str1, n + 1, m + 1) ||isBoolean(str, str1, n + 1, m);
>             } else {
>                 return false;
>             }
>         }
>     }
> 
> ### ![1949ad3630e84b2f93d67dbf410971ae.png][] ###

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

![c43635fbfc744fda849d6a4d91011c5e.png][]

[Link 1]: https://www.nowcoder.com/practice/1221ec77125d4370833fd3ad5ba72395
[ae8dd51a2a2640f2b1b82a38614f69ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/84019f596a944da0abf0779d26a67a15.png
[Link 2]: https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
[1949ad3630e84b2f93d67dbf410971ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/cad620d5d78a44dd9068aeccc979aefb.png
[c43635fbfc744fda849d6a4d91011c5e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/871107043a754711969c9353532270c3.png