刷题笔记之七（统计每个月兔子的总数+汽水瓶+查找两个字符串a,b中的最长公共子串+公共子串计算）

目录

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)

题目要求：

 题目分析：

上代码

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))

上代码

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;
    }
}