前言：
- 大家好，我是良辰丫，第十八篇,牛客网选择题+编程题统计每个月兔子的总数+字符串通配符.💞💞💞
- 每天早上醒来时，我们可以有两个简单的选择：回头去睡，继续做梦。或者，起身去追逐梦想。
🧑个人主页：良辰针不戳
📖所属专栏：百日冲大厂
🍎励志语句：生活也许会让我们遍体鳞伤，但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连，关注，点赞，收藏。
💌作者能力有限，可能也会出错，欢迎大家指正。
💞愿与君为伴，共探Java汪洋大海。
目录
- 1. 选择题
- 2. 编程题
- 2.1 统计每个月兔子的总数
- 2.2 36895-字符串通配符
1. 选择题
- count返回行数,只能返回数值.
- t1没有数据,或者t1的数据都是null,那么max返回null
- comcat是字符串拼接函数,数据库中字符串不能使用加号进行拼接,如果拼接的一个字符串是null,那么最终结果就是null.
- 外键可以关联另一张表.
- 默认创建的外键是严格模式(必须在主表中,关联的键有该数据),其它模式下外键值可以为空.
- 候选键,可以标识数据唯一性的最小集.
- A选项关联的数据可以共享,在逻辑和物理上独立性高.
- B选项冗余度低.
- C选项,数据库要具有安全性才能进行使用(数据是非常重要的)
- D选项,数据能实现共享.
top是sql server的关键字,用于求前n条数据,如果要查从m到n条,要写子查询.
select top n查询字段 from…
- 一个下划线匹配一个字符
- %号匹配多个字符
avg表示平均
使用%号作为通配符匹配0个以上的字符,包含0.
持续性也叫作持久性.
2. 编程题
2.1 统计每个月兔子的总数
做题链接:
链接: 统计每个月兔子的总数
题目描述:
题目分析:
- 这道题第一眼看是一个数学问题,没错就是一个数学问题.
- 找到了规律问题就迎刃而解了,有人可能会说这不是废话嘛,怎么找规律呢?
- 我们先列举几组数字,第一个月1只兔子,第二个月2只兔子,第三个月3只兔子,第四个月5只兔子.
- 我们会惊奇的发现这不是斐波那契数列嘛,我们可以使用递归去解决,但是递归很容易超时,于是乎,我们使用动态规划.
- 我们还需要培养一种思想,斐波那契是我们经常做的题,于是我们遇到这样的找规律题,优先去看看符不符合斐波那契.
- 好多看起来难的题都是找规律,我们优先找规律,实在找不到规律可以暴力试一下,在比试的时候要优先做那些会的题,别钻牛角尖.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n+1];
arr[1] = 1;
arr[2] = 1;
for(int i = 3;i<n+1;i++){
arr[i] = arr[i-1] + arr[i-2];
}
System.out.println(arr[n]);
}
}
2.2 36895-字符串通配符
做题链接:
链接: 36895-字符串通配符
题目描述:
题目分析:
- 读完题目是否有一些迷茫呢?模拟题,情况种类这么多,难以完全通过,*号是通配符,到底该通配几个符号呢,一连串的问号浮现在脑海中.
- *号匹配几个字符,这是关键,我们会想到递归和动态规划,但是递归的时间复杂度太高了,因此我们使用动态规划.
- 什么是动态规划,我们现在先简单了解,后面我会带领大家系统学习动态规划,先接触动态规划,脑海中多多少少对动态规划(简称dp)有一定的认识即可,现在搞不懂也没多大的关系.
- 递归想必大家都知道,上面我们讲了斐波那契的类似题每个月的兔子总数,因此我就拿这个举例带大家简单认识动态规划.
- 动态规划是用数组实现的,数组元素记忆我们要存的数据,上面的兔子问题数组下标表示第几个月,下标为2表示第二个月,该元素表示第二个月的兔子总数.
- 通过数组记忆我们的元素,不用重新计算,通过索引直接定位我们需要的数据,提高了我们的时间效率.
- 那么如何通过数组进行记忆,我们就需要找规律,初始化初始元素,通过初始元素依次记忆下一个元素.
- 因此呢,元素具有依赖关系,某一个元素可能依赖前一个数据或者后一个数据,我们只要找到依赖关系,问题就基本解决了.
- 然后我们回归到我们本道题字符串匹配问题,我们需要通过二维数组记忆我们的所有情况,因此我们选择动态规划.
接下来我们先用二维数组举例模拟一个过程来帮助我们理解一下这道题.横坐标我们用 i 来表示,纵坐标用 j 来表示.
- 初始值,特殊处理一下第0行,我们把dp[0][0]赋值为true,因为这个位置二者都为空.*号是通配符,可以匹配任意多个字符,特殊处理一下*号,遇到*号就赋值该位置的前一个值,*号的关系式子为dp[i][j] = dp[i-1][j] || dp[i][j-1],只要i的前一个或者j的前一个满足即可.
- 注意问号只匹配一个字符,不用赋予初始值,交给下面处理即可,与问号匹配的要有字符,不能为空,因此dp[i][j] = dp[i-1][j-1].
- 两个字符相等(不区分大小写,因此需要转换去比较),直接返回true即可.
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String t=sc.nextLine();
String s=sc.nextLine();
System.out.println(func(t,s));
}
}
public static boolean func(String t,String s){
char[] ct=t.toCharArray();
char[] cs=s.toCharArray();
int lt=ct.length;
int ls=cs.length;
boolean[][] dp=new boolean[ls+1][lt+1];
dp[0][0]=true;
for(int j = 1;j<lt;j++){
if(ct[j-1] == '*'){
dp[0][j] = dp[0][j-1];
}
}
for(int i=1;i<=ls;i++){
for(int j=1;j<=lt;j++){
if(ct[j-1]=='*'){
if(i==0){
dp[i][j]=dp[i][j-1];
}else{
if(cs[i-1]=='.' || (cs[i-1]>='0'&&cs[i-1]<='9') ||
(cs[i-1]>='a'&&cs[i-1]<='z') ||(cs[i-1]>='A'&&cs[i-1]<='Z')
){
dp[i][j]=dp[i-1][j] || dp[i][j-1];
}
}
}else{
if(i>0 && func2(ct[j-1],cs[i-1])){
dp[i][j]=dp[i-1][j-1];
}
}
}
}
return dp[ls][lt];
}
public static boolean func2(char t,char s){
if(t=='?') return true;
if(t>='a'&&t<='z'){
t=(char)(t-'a'+'A');
}
if(s>='a'&&s<='z'){
s=(char)(s-'a'+'A');
}
return s == t;
}
}
