目录
1. 数据库中，count不会返回null值，max和concat可能会返回null值
2. 数据库特点： 共享性高，冗余度小，安全性强，独立性强
3. top是sql server中的关键字，用于求前n条数据
4. 数据库使用函数进行全部扫描（数据遍历）最慢，并且函数执行本身也是需要耗时的
5. 使用%作为通配符时，匹配的是0个以上的字符（包含0）
6. RDBS是关系型数据库，hadoop是大数据方向的数据库不是关系型数据库
7. 统计每个月兔子的总数
8. 查找两个字符串a,b中的最长公共子串
9. 汽水瓶
10. 二叉树中只有完全二叉树可以使用顺序表存储
11. 递归函数的出口就是,用一个分支不调用自身,直接return
12. 已知二叉树后续遍历序列是bfegcda,中序遍历序列是badefcg,它的前序遍历序列是: B.abdcefg
13. 对于顺序表存储的线性表,访问结点和增加结点的时间复杂度为(C)
14. 初始序列为1 8 6 2 5 4 7 3的一组数采用堆排序，当建堆(小根堆)完毕时，堆所对应的二叉树中序遍历序列为：( A)
15. 公共子串计算
1. 数据库中，count不会返回null值，max和concat可能会返回null值
（1）count（*）一定可以返回数值，如果t1中没有数据，返回0
（2）max返回null 有两种可能情况：（1）t1中没有数据 （2）coll字段，全都是null
（3）concat（）：字符串拼接的函数（数据库中，字符串不能使用+拼接）
如果拼接的其中一个字符串是null，结果就是null
所以答案选D
2. 数据库特点： 共享性高，冗余度小，安全性强，独立性强
数据库管理系统的特点：
共享性高，冗余度小（通过关联，就可以共享；逻辑和物理上，独立性高）；
具有高度的物理独立性和逻辑独立性；
整体结构化，用数据模型描述；
由数据库管理系统提供数据安全性、完整性、并发控制和恢复能力。
3. top是sql server中的关键字，用于求前n条数据
top，是sql server中的关键字，用于求前n条数据（如果查从m到n条，要写子查询）
语法：select top n 查询字段 from
4. 数据库使用函数进行全部扫描（数据遍历）最慢，并且函数执行本身也是需要耗时的
PhoneNo是数字组成（使用数值数据类型），和字符串可以比较，但是会进行类型转换（有点耗时）
like：模糊匹配，最开始xxx的匹配，可以使用索引
substr（）使用函数，不会再使用索引，全部扫描（全部数据遍历），函数本身的执行，也是需要耗时的（最慢）
5. 使用%作为通配符时，匹配的是0个以上的字符（包含0）
6. RDBS是关系型数据库，hadoop是大数据方向的数据库不是关系型数据库
RDBS是关系型数据库，hadoop是大数据方向的数据库，不是关系型数据库
7. 统计每个月兔子的总数
题目链接：统计每个月兔子的总数_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
上代码文章来源地址https://www.toymoban.com/news/detail-408719.html
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int d = scan.nextInt();
int[] arr = new int[31];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < d; i++) {
arr[i] = arr[i-2] + arr[i-1];
}
System.out.println(arr[d-1]);
}
}8. 查找两个字符串a,b中的最长公共子串
题目链接：查找两个字符串a,b中的最长公共子串_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
这道题可以考虑使用动态规划来做,
因为动态规划是分治思想,也就是将问题化简,大问题化为小问题,先解决小问题,再用小问题的解推导出大问题的解
动态规划的特征也就是:
(1)把原来的问题分解为几个相似的子问题
(2)所有的子问题都只需要解决一次
(3)存储子问题的解
这道题的问题:两个字符串的最长公共子串
子问题:a的子串 和 b的子串 中最长公共子串
抽象子问题: a的前 i 个字符 和 b的前 j 个字符中,他们的最长公共子串
根据动态规划四步走分析:
(1)状态: a的前 i 个字符 和 b的前 j 个子符中最长公共子串的长度
如果要知道最长公共子串具体内容:长度,起始位置,结束位置
F(i , j): 以a的第 i 个子符结尾的子串 和 以b的第 j 个子符结尾的子串 , 其最长公共子串的长度
(2)状态转移方程:
如果a的第i个字符和b的第j个字符相同 F(i,j) = F(i-1 , j-1) + 1
不相同:0
(3)起始位置:i - maxLen:4-4 = 0 (maxLen最长公共子串长度)
(4)返回值:最长子串的内容
上代码
import java.io.*;
import java.util.*;
public class Main {
private static String getMaxSubstr(String str1, String str2) {
char[] arr1 = str1.toCharArray();
char[] arr2 = str2.toCharArray();
int len1 = arr1.length;
int len2 = arr2.length;
int[][] maxSubLen = new int[len1+1][len2+1];
//最长子串的起始位置
int start = 0;
//最长子串的长度
int maxLen = 0;
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
//如果第i个字符和第j个字符相等,则进行累加
if(arr1[i-1] == arr2[j-1]) {
maxSubLen[i][j] = maxSubLen[i-1][j-1] + 1;
}
//更新
if( maxSubLen[i][j] > maxLen) {
maxLen = maxSubLen[i][j];
start = i - maxLen;
}
}
}
return str1.substring(start,start+maxLen);
}
public static void main (String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1;
String str2;
if((str1 = br.readLine()) != null) {
str2 = br.readLine();
if(str1.length() < str2.length()) {
System.out.println(getMaxSubstr(str1,str2));
}else {
System.out.println(getMaxSubstr(str2,str1));
}
}
}
}
9. 汽水瓶
题目链接：汽水瓶_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
上代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
private static int getNum (int num) {
//累加汽水的个数
int sum = 0;
while(num > 1) {
sum += num/3;
//空汽水瓶的个数
num = num/3 + num%3;
//特殊情况,空瓶剩余2
if(num == 2) {
sum++;
break;
}
}
return sum;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int num = scan.nextInt();
if(num == 0) {
break;
}else {
System.out.println(getNum(num));
}
}
}
}10. 二叉树中只有完全二叉树可以使用顺序表存储
下列数据结构中,不能采用顺序存储结构的是()
A.非完全二叉树 B. 堆 C. 队列 D. 栈
这道题选A ,
二叉树中只有完全二叉树可以使用顺序表存储,
而非完全二叉树只能采用链式存储(Node left, Node right)
堆的底层就是一颗完全二叉树,也就是顺序存储结构
队列和栈也可以采用顺序表也就是数组来存储
11. 递归函数的出口就是,用一个分支不调用自身,直接return
递归函数最终会结束,那么这个函数一定?
A.使用了局部变量 B.有一个分支不调用自身
C.使用了全局变量或者使用了一个或多个参数 D,没有循环调用
递归函数的终止条件.也就是递归函数的出口:函数调用过程中有一个分支直接return,不会一直调用下去,所以这个选B
12. 已知二叉树后续遍历序列是bfegcda,中序遍历序列是badefcg,它的前序遍历序列是: B.abdcefg
已知二叉树后续遍历序列是bfegcda,中序遍历序列是badefcg,它的前序遍历序列是:
A,abcdefg B.abdcefg C.adbcfeg D,abecdfg
13. 对于顺序表存储的线性表,访问结点和增加结点的时间复杂度为(C)
对于顺序表存储的线性表,访问结点和增加结点的时间复杂度为()
A O(n) O(n) B O(n) O(1) C O(1) O(n) D O(1) O(1)
顺序存储的线性表,可以直接通过下标访问结点,所以时间复杂度O(1)
而增加结点最坏情况下,在数组头部增加结点,时间复杂度为O(n)选C
14. 初始序列为1 8 6 2 5 4 7 3的一组数采用堆排序，当建堆(小根堆)完毕时，堆所对应的二叉树中序遍历序列为：( A)
15. 公共子串计算
题目链接：公共子串计算_牛客题霸_牛客网 (nowcoder.com)
题目要求：
题目分析：
这道题和前面第8题可以说是一样的
第8题是求两个字符串的最长公共子串(是求出最长公共子串的起始位置,和公共最长子串长度来算出末尾位置,进行字符串截取)
而这道题是求两个字符串的最长公共子串的长度(也就是直接求出最长子串的长度就可以了)
这里再写一遍动态规划四步走吧
(1)状态: 以第一个字符串第i个字符结尾和以第二个字符串第j个字符结尾的最大公共子串的长度
(2)状态转移方程:
第i个字符 != 第j个字符 F(i , j) = 0
第i个字符 == 第j个字符 F(i , j) = F(i-1 , j-1) +1
(3)初始状态:F(i,0) = F(0 , j):0
(4)返回值:max(F(i,j))文章来源：https://www.toymoban.com/news/detail-408719.html
上代码
import java.util.Scanner;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str1 = br.readLine();
String str2 = br.readLine();
if(str1.length() > str2.length()) {
System.out.println(getMaxStr(str1,str2));
} else {
System.out.println(getMaxStr(str2,str1));
}
}
private static int getMaxStr(String a, String b) {
int aLen = a.length();
int bLen = b.length();
int[][] ab = new int[aLen+1][bLen+1];
int maxLen = 0;//记录最长子串长度
for(int i = 1; i <= aLen; i++) {
for(int j = 1; j <= bLen; j++) {
if(a.charAt(i-1) == b.charAt(j-1)) {
//状态转移方程
ab[i][j] = ab[i-1][j-1] + 1;
}
//更新长度
if(ab[i][j] > maxLen) {
maxLen = ab[i][j];
}
}
}
return maxLen;
}
}到了这里，关于刷题笔记之七（统计每个月兔子的总数+汽水瓶+查找两个字符串a,b中的最长公共子串+公共子串计算）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
