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

╰+哭是因爲堅強的太久メ 2023-09-25 12:39 13阅读 0赞

**目录**

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值 ##

![64f74190de6043d2994b7863ef8e4cd6.png][]

（1）count（\*）一定可以返回数值，如果t1中没有数据，返回0

（2）max返回null 有两种可能情况：（1）t1中没有数据 （2）coll字段，全都是null

（3）concat（）：字符串拼接的函数（数据库中，字符串不能使用+拼接）

如果拼接的其中一个字符串是null，结果就是null

所以答案选D

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

## 2. 数据库特点： 共享性高，冗余度小，安全性强，独立性强 ##

![da53fb9c7e78418e90902a45e286d29c.png][]

数据库管理系统的特点：

共享性高，冗余度小（通过关联，就可以共享；逻辑和物理上，独立性高）；

具有高度的物理独立性和逻辑独立性；

整体结构化，用数据模型描述；

由数据库管理系统提供数据安全性、完整性、并发控制和恢复能力。

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

## 3. top是sql server中的关键字，用于求前n条数据 ##

![4aa1d639f83f4a08951325324230da1e.png][]

top，是sql server中的关键字，用于求前n条数据（如果查从m到n条，要写子查询）

语法：select top n 查询字段 from

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

## 4. 数据库使用函数进行全部扫描（数据遍历）最慢，并且函数执行本身也是需要耗时的 ##

![c7e0f393ecf4415ebbc40a692006974f.png][]

PhoneNo是数字组成（使用数值数据类型），和字符串可以比较，但是会进行类型转换（有点耗时）

like：模糊匹配，最开始xxx的匹配，可以使用索引

substr（）使用函数，不会再使用索引，全部扫描（全部数据遍历），函数本身的执行，也是需要耗时的（最慢）

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

## 5. 使用%作为通配符时，匹配的是0个以上的字符（包含0） ##

![9ad29abd615745f69f3b6161ad82fc1a.png][]

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

## 6. RDBS是关系型数据库，hadoop是大数据方向的数据库不是关系型数据库 ##

![a9d5c84dd0804a4dabf2d275b6acdc2a.png][]

RDBS是关系型数据库，hadoop是大数据方向的数据库，不是关系型数据库

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

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

**题目链接：**[统计每个月兔子的总数\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

**题目要求：**

![4ba366f599dc420a80d653a149c39e52.png][]

**题目分析：**

![acb03d9fb876428ca102bb53e566fb20.png][]

**上代码**

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)][a_b_ _nowcoder.com]

**题目要求：**

![caaf4ba21c8e49a48a55120b32988b60.png][]

**题目分析：**

> 这道题可以考虑使用动态规划来做,
> 
> 因为动态规划是分治思想,也就是将问题化简,大问题化为小问题,先解决小问题,再用小问题的解推导出大问题的解
> 
> 动态规划的特征也就是:
> 
> (1)把原来的问题分解为几个**相似的子问题**
> 
> (2)所有的**子问题都只需要解决一次**
> 
> (3)**存储子问题的解**
> 
> 这道题的问题:两个字符串的最长公共子串
> 
> 子问题:a的子串 和 b的子串 中最长公共子串
> 
> 抽象子问题: a的前 i 个字符 和 b的前 j 个字符中,他们的最长公共子串
> 
> 根据动态规划四步走分析:
> 
> (1)状态: a的前 i 个字符 和 b的前 j 个子符中最长公共子串的长度
> 
> 如果要知道最长公共子串具体内容:长度,起始位置,结束位置
> 
> F(i , j): 以a的第 i 个子符结尾的子串 和 以b的第 j 个子符结尾的子串 , 其最长公共子串的长度
> 
> ![be193f22f74c45628c3092ab9a8b4248.png][]
> 
> (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)][_nowcoder.com 1]

**题目要求：**

![fcdc2fa8417f4622bf881b9f6ded73ee.png][]

![c6b9e5d3f7d641a999dfbc8b5870bfa8.png][]

**题目分析：**

![947fe9a6c7d14166aee1f854b63c23b3.png][]

**上代码**

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

![683d394aa112465a938014a5cebfb233.png][]

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

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

![f8f37a1f7b4d44b59ee240b10071b025.png][]

![05774b9da0b449f7ac790f6a1641c19d.png][]

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

## 15. 公共子串计算 ##

**题目链接：**[公共子串计算\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com 2]

**题目要求：**

![8220ba1a076545bb86a9f62584238869.png][]

**题目分析：**

> 这道题和前面第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;
        }
    }

[64f74190de6043d2994b7863ef8e4cd6.png]: https://img-blog.csdnimg.cn/64f74190de6043d2994b7863ef8e4cd6.png
[da53fb9c7e78418e90902a45e286d29c.png]: https://img-blog.csdnimg.cn/da53fb9c7e78418e90902a45e286d29c.png
[4aa1d639f83f4a08951325324230da1e.png]: https://img-blog.csdnimg.cn/4aa1d639f83f4a08951325324230da1e.png
[c7e0f393ecf4415ebbc40a692006974f.png]: https://img-blog.csdnimg.cn/c7e0f393ecf4415ebbc40a692006974f.png
[9ad29abd615745f69f3b6161ad82fc1a.png]: https://img-blog.csdnimg.cn/9ad29abd615745f69f3b6161ad82fc1a.png
[a9d5c84dd0804a4dabf2d275b6acdc2a.png]: https://img-blog.csdnimg.cn/a9d5c84dd0804a4dabf2d275b6acdc2a.png
[_nowcoder.com]: https://www.nowcoder.com/practice/1221ec77125d4370833fd3ad5ba72395?tpId=37&&tqId=21260&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
[4ba366f599dc420a80d653a149c39e52.png]: https://img-blog.csdnimg.cn/4ba366f599dc420a80d653a149c39e52.png
[acb03d9fb876428ca102bb53e566fb20.png]: https://img-blog.csdnimg.cn/acb03d9fb876428ca102bb53e566fb20.png
[a_b_ _nowcoder.com]: https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506?tpId=37&tqId=21288&ru=/exam/oj
[caaf4ba21c8e49a48a55120b32988b60.png]: https://img-blog.csdnimg.cn/caaf4ba21c8e49a48a55120b32988b60.png
[be193f22f74c45628c3092ab9a8b4248.png]: https://img-blog.csdnimg.cn/be193f22f74c45628c3092ab9a8b4248.png
[_nowcoder.com 1]: https://www.nowcoder.com/practice/fe298c55694f4ed39e256170ff2c205f?tpId=37&tqId=21245&ru=/exam/oj
[fcdc2fa8417f4622bf881b9f6ded73ee.png]: https://img-blog.csdnimg.cn/fcdc2fa8417f4622bf881b9f6ded73ee.png
[c6b9e5d3f7d641a999dfbc8b5870bfa8.png]: https://img-blog.csdnimg.cn/c6b9e5d3f7d641a999dfbc8b5870bfa8.png
[947fe9a6c7d14166aee1f854b63c23b3.png]: https://img-blog.csdnimg.cn/947fe9a6c7d14166aee1f854b63c23b3.png
[683d394aa112465a938014a5cebfb233.png]: https://img-blog.csdnimg.cn/683d394aa112465a938014a5cebfb233.png
[f8f37a1f7b4d44b59ee240b10071b025.png]: https://img-blog.csdnimg.cn/f8f37a1f7b4d44b59ee240b10071b025.png
[05774b9da0b449f7ac790f6a1641c19d.png]: https://img-blog.csdnimg.cn/05774b9da0b449f7ac790f6a1641c19d.png
[_nowcoder.com 2]: https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b?tpId=37&tqId=21298&ru=/exam/oj
[8220ba1a076545bb86a9f62584238869.png]: https://img-blog.csdnimg.cn/8220ba1a076545bb86a9f62584238869.png