上海倒闭工厂名单/河南网站建设优化技术

目录 

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

二、字符串通配符

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

  题目描述：

有一种兔子，从出生后第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() ，空间复杂度：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];//两个字符串都为空，初始化为0arr[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;}
}

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