刷题_18：统计每个月兔子的总数 and 字符串通配符

古城微笑少年丶 2023-09-30 20:58 43阅读 0赞

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

**题目链接：**

> [统计每个月兔子的总数][Link 1]

**题目描述：**

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

**输入描述：**

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

**输出描述：**

> **输出对应的兔子总数**

**示例1：**

> **输入：  
> 3  
> 输出：  
> 2**

**个人总结：**

> **非常非常正常的斐波那契数列。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int f1 = 1;
            int f2 = 1;
            for (int i = 3; i <= n; i++) {
        
                int tmp = f1 + f2;
                f1 = f2;
                f2 = tmp;
            }
            System.out.println(f2);
        }
    }

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

### 二.字符串通配符 ###

**题目链接：**

> [字符串通配符][Link 2]

**题目描述：**

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

**示例6：**

> **输入：  
> p\*p\*qp\*\*pq\*p\*\*p\*\*\*ppq  
> pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp  
> 输出：  
> false**

**个人总结：**

> **一个比较难的动态规划题目，个人想法附在代码注释里面了。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String p = sc.nextLine();
            String s = sc.nextLine();
            int lenS = s.length();
            int lenP = p.length();
            //dp[i][j]：长度为j的p子串能否匹配长度为i的s子串
            boolean[][] dp = new boolean[lenS + 1][lenP + 1];
            dp[0][0] = true;
            //初始化 考虑到""和“*****”匹配也是成功的
            for (int j = 1; j <= lenP; j++) {
        
                dp[0][j] = p.charAt(j - 1) == '*' && dp[0][j - 1];
            }
            for (int i = 1; i <= lenS; i++) {
        
                for (int j = 1; j <= lenP; j++) {
        
                    char c1 = p.charAt(j - 1);
                    char c2 = s.charAt(i - 1);
                    if (c1 == '*' && isOk(c2)) {
        
                        //dp[i][j - 1]：让'*'匹配0次
                        //dp[i - 1][j - 1]：让'*'匹配当前字符
                        //dp[i - 1][j]：若'*'匹配s的i - 1成功 则'*'匹配s的i也成功
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j];
                    } else {
        
                        //如果p对应下标不为'*' 则直接比较 考虑一下'?'情况即可
                        dp[i][j] = dp[i - 1][j - 1] && (c2 == c1 || c2 == (c1 ^ 32) || (c1 == '?' && isOk(c2)));
                    }
                }
            }
            System.out.println(dp[lenS][lenP]);
        }
    
        public static boolean isOk(char c) {
        
            if (c >= '0' && c <= '9' || c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z') {
        
                return true;
            }
            return false;
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/1221ec77125d4370833fd3ad5ba72395
[Link 2]: https://www.nowcoder.com/questionTerminal/43072d50a6eb44d2a6c816a283b02036?f=discussion