Java题目训练——统计每个月兔子的总数和字符串通配符

待我称王封你为后i 2023-09-30 21:15 2阅读 0赞

**目录**

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

二、字符串通配符

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

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

题目描述：

> 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。 例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。 一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
> 
> 数据范围：1<=n<=31

输入描述：

> 输入一个int型整数表示第n个月

输出描述：

> 输出对应的兔子总数

示例

> 输入：3
> 
> 输出：2

**题目解析：**

> 找规律，就是一个斐波那契数列，这里采用递归的方式，如果是第1个数或者第2个数，返回1；否则返回这个位置的前两个数之和。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
    
            System.out.println(num(n));
    
        }
    
        public static int num(int n){
            if(n == 1 || n == 2){
                return 1;
            }
            return num(n - 1) + num(n - 2);
        }
    }

### 二、字符串通配符 ###

题目描述：

> 问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。 要求：
> 
> 实现如下2个通配符：
> 
> \*：匹配0个或以上的字符（注：能被\*和?匹配的字符仅由英文字母和数字0到9组成，下同）
> 
> ？：匹配1个字符 注意：匹配时不区分大小写。
> 
> 输入：
> 
> 通配符表达式；
> 
> 一组字符串。
> 
> 输出：
> 
> 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
> 
> 数据范围：字符串长度：1<=s<=100
> 
> 进阶：时间复杂度：O(![n^\{2\}][n_2]) ，空间复杂度：O(n)

输入描述：

> 先输入一个带有通配符的字符串，再输入一个需要匹配的字符串

输出描述：

> 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

示例

> 示例1
> 
> 输入：te?t\*.\*
> 
> txt12.xls
> 
> 输出：false

> 示例2
> 
> 输入：z
> 
> zz
> 
> 输出：false

> 示例3
> 
> 输入：pq
> 
> ppqq
> 
> 输出：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

**题目解析：**

> 本题采用动态规划的思想，一共有三种情况，一种是匹配"\*"，一种是匹配"?"，一种是自身对应匹配，其中匹配"?"和自身对应可以归为一种情况。
> 
> 将两个字符串s1（有通配符），s2全都转化为小写，并且创立一个boolean状态数组arr\[s1.length()+ 1\]\[s2.length()+ 1\]，+1是为了设立初始态，并且使下标对应。
> 
> 初始态为arr\[0\]\[0\] = true，s1为"\*\*..."，s2为空的话，字符串此位置为"\*"并且上一个状态为true时，此时状态为true；s1如果为空的话，直接默认为false。
> 
> 首先看匹配"\*"的情况，如果s1此时的字符是\*，并且s2此时的字符合法，那么有三种状态，第一种是如果\*匹配s2的上一个状态，那么这时的状态也是true；第二种是如果不匹配\*也true（即s1的上一个状态匹配这时的状态），那么true；第三种是如果\*匹配当前字符，状态为true。只要这三种可能有一种为true，就记此时的状态为true。
> 
> 其次就是匹配"?"和自身对应的两种情况，只要上一个状态为true，并且这两种情况成立一种就可以记为true。
> 
> 最后输出arr\[s1.length()\]\[s2.length()\]的状态即可。

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            String s1 = scanner.nextLine();
            String s2 = scanner.nextLine();
    
            //全部转成小写
            s1 = s1.toLowerCase();
            s2 = s2.toLowerCase();
    
            int n1 = s1.length();
            int n2 = s2.length();
    
            //建立状态存储数组
            boolean[][] arr = new boolean[n1 + 1][n2 + 1];
    
            //两个字符串都为空，初始化为0
            arr[0][0] = true;
    
            //s1为***...
            //s2为空
            //初始化
            for(int i = 1; i < n1 + 1; i++){
                arr[i][0] = s1.charAt(i - 1) == '*' && arr[i - 1][0];
            }
    
            //动态规划
            for(int i = 1; i < n1 + 1; i++){
                for (int j = 1; j < n2 + 1; j++) {
                    char ch1 = s1.charAt(i - 1);
                    char ch2 = s2.charAt(j - 1);
                    //为'*'的情况
                    if(ch1 == '*' && isTrue(ch2)){
                        //arr[i][j - 1] '*'匹配j - 1成功，所以匹配j也成功
                        //arr[i - 1][j] '*'匹配0次
                        //arr[i - 1][j - 1] '*'匹配当前字符
                        arr[i][j] = arr[i][j - 1] || arr[i - 1][j - 1] || arr[i - 1][j];
                    }else {
                        //为'?'的情况
                        //字符自身匹配相等的情况
                        //注意括号范围
                        arr[i][j] = arr[i - 1][j - 1] && (ch1 == ch2 ||(ch1 == '?' && isTrue(ch2)));
                    }
                }
            }
            System.out.println(arr[n1][n2]);
        }
    
        //字符是否符合范围
        public static boolean isTrue(char ch){
            if((ch >='0' && ch <='9')|| (ch >= 'a' && ch <= 'z')){
                return true;
            }
            return false;
        }
    }

如有建议或想法，欢迎一起讨论学习~

[n_2]: https://latex.csdn.net/eq?n%5E%7B2%7D