八股文-- 2022.08.31

途虎养车2022.08.31

• 在Java中，LinkedList类有而ArrayList类没有的方法是：removeLast()方法

  • LinkedList :底层基于双向链表实现，不支持高效的随机元素访问

  • ArrayList : 底层基于Object数组实现，支持高效的随机元素访问

• 在计算机中，一个浮点数由两部分组成，他们是阶码和尾数

• 不符合Java语言特征的是： 支持类C的指针操作运算

• 时间复杂度为： while循环的时间复杂度是log2n

int i=1;
while(i<=n){
i+i*2;
}
1
2
3
4

• 一个长度为n的顺序表中，在下标为i的位置（0<=i

• 栈和队列的共同点是：在端点操作线性表

  • 栈：先进后出

  • 队列：先进先出

• 在OSI的七层参考模型中，工作在第三层以上的网间连接设备是：网关

  • OSI的七层参考模型：“物链网数会示用”

• 已知二叉树的前缀优先遍历顺序为：c b d a e f g ，中间优先遍历顺序为：a b c d e f g，则后缀优先遍历顺序为：（未查找到前缀优先遍历等相关内容 ？？？）

补充二叉树的三种遍历顺序：

• 先序遍历：根节点->左子树->右子树

• 中序遍历：左子树->根节点->右子树

• 后序遍历：左子树->右子树–>根节点

已知先序/后序遍历顺序，和中序遍历顺序，求后序/先序遍历顺序可以使用图表大法！

口诀：先序竖，后序反竖，中序横

• 假如两个表的连接是这样的：table_1 inner join table_2，其中table_1和table_2是两个具有公共属性的表，这种连接会生成哪种结果？

  只包括table_1和table_2满足条件的行

  • INNER JOIN(等值连接) 只返回两个表中联结字段相等的行
  • LEFT JOIN(左联接) 返回包括左表中的所有记录和右表中联结字段相等的记录
  • RIGHT JOIN(右联接) 返回包括右表中的所有记录和左表中联结字段相等的记录

• 在数据库系统中，没有哪一种数据模型？实体联系模型

  补充1：常用的逻辑数据模型

  • 层次模型
  • 网状模型
  • 关系模型

  补充2 ： 数据模型按不同的应用层次分成三种类型：分别是概念数据模型、逻辑数据模型、物理数据模型。

• 若已知色彩显示屏的分辨率为1024×768，如果他能显示16色，则显示存储器容量至少应为：

  16色 表示 用 4bit 显示颜色 2^4=16 也就是 0.5B 代表一个点

  1024x768==786432个点需要 786432x0.5 == 393216B 再除以 1024 结果是 384 kB

• 下列说法正确的是？

  A. UDP协议保证数据按序发送，按序到达，提供超时重传来保证可靠性 × UPD是无序的

  B. UDP支持一对一，多对多，一对多的通信 √

  C. TCP有流量控制和拥塞控制 √

  D. 开始传输实际数据之前TCP的客户端和服务端必须通过四次握手建立连接 ×

• Linux内核的同步机制的描述正确的是？

  A. 自旋锁与互斥锁有点类似，都不会引起调用者睡眠 × 只有自旋锁不会引起调度睡眠

  B. 自旋锁使用者一般维持锁时间非常长 ×

  C. 读写信号量适于在读多写少的情况下使用 √

  D.原子操作绝不会在执行完毕前被任何其他任务或事物打断，通常用于实现资源的引用计数 √

• 以下算法属于堆栈型替换算法的是：

  A. 最近最久未使用算法LRU

  B. 优化替换算法OPT

  C. 先进先出算法

  D. 近期最少使用算法LFU

• SQL标准定义的事物隔离级别：读未提交、读已提交、可重复读以及可串行化

• 下面对ER模型中实体集之间联系的正确叙述是？ABC

  A. 实体集内部之间也可能存在联系

  B. 实体集之间的联系是由客观实际确定的

  C. 两个实体集之间联系存在数量关系

  D.实体集之间联系必须有属性 × 实体集之间联系不一定有属性

编程题1

途虎十周年庆典开幕仪式上，空中绽放了一颗二叉树型的烟花，给定一颗二叉树root代表烟花，节点值表示巨型烟花这一位置的颜色，请你帮小乐虎计算巨型烟花一共有多少种不同的颜色

试调数据：{1,3,2,5,#,2} 输出：4

试调数据：{8,8,8} 输出：1

原题目链接：LCP 44. 开幕式焰火 - 力扣（LeetCode）

二叉树相关遍历知识补充：数据结构（四）：二叉树_山舟的博客-CSDN博客_二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   Set<Integer> set; 
    public int numColor(TreeNode root) {
      //1.  使用set去重
    set= new HashSet<>();
    //2. 进行遍历
        dfs(root);
        return set.size();

    }
    //前序遍历
    public void dfs(TreeNode root){
	//root为空是递归的终止条件
	if (root == null)return;
     set.add(root.val);
        dfs(root.left);
        dfs(root.right);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

编程题2

给你一个数组oils,表示不同升数的机油，以及一个整数box，表示保养一辆车总共需要的机油升数，计算并返回可以正好凑成一次保养所需的最少的机油桶数（不能剩余），如果没有任何方式能组合成要求的邮箱大小，返回-1.你可以认为每种规格的机油的数量是无限的

示例：

输入：[1，2，5]，11

输出：3

说明：11=5+1+1

原题链接：322. 零钱兑换 - 力扣（LeetCode）

//动态规划算法，完全背包问题——————本题不适合贪心算法
class Solution {
    public int coinChange(int[] coins, int amount) {
  
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);

       dp[0] = 0;
        //外层从金额amount开始循环
        for (int i = 1; i <= amount; i++) {
            //内层从硬币的类型开始循环
            for (int j = 0; j < coins.length; j++) {
				//硬币类型 <= 兑换金额amount
                if (coins[j] <= i) {
                    //所需的金币数量
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

编程题3

给你一个整数数组nums和一个整数k，你需要将这个数组划分到k个大小相同的子集中，使得同一个子集里面没有两个相同的元素，一个子集的不兼容性是该子集里面最大值和最小值的差。

请你返回将数组划分k个子集后，各子集不兼容性的和 的最小值，如果无法分成k个子集，返回-1.

子集的定义是数组中的一些数字的集合，对数字顺序没有要求

原题链接：1681. 最小不兼容性 - 力扣（LeetCode）

//状态压缩
class Solution {
    public int minimumIncompatibility(int[] nums, int k) {
        k=nums.length/k;    //每份有len/k 个数（转换k的含义）
        int n = nums.length;
        int[] dp = new int[1<<n];
        Arrays.fill(dp,Integer.MAX_VALUE/2);
        dp[0]=0;
        for (int status = 1; status < (1<<n); status++) {
            int curBitCount = Integer.bitCount(status);
            if (curBitCount%k!=0) continue;
            for (int pre = status; pre >=0 ; pre = (pre-1)& status) {   //子集
                int preBitCount = Integer.bitCount(pre);
                if (preBitCount%k!=0) continue;
                int dif = curBitCount-preBitCount;
                if (dif==k){
                    if (check(status,pre,nums,dp)){ //判断子集是否合法， 即能否从dp[pre]转移到dp[cur]中
                        dp[status] =Math.min(dp[status],dp[pre]+dv);    //条件成立，进行转移
                    }
                }

                if (pre == 0) break;    //这个是子集生成中，跳出的死循环的
            }
        }
        return dp[dp.length-1]==Integer.MAX_VALUE/2?-1:dp[dp.length-1];
    }

    int dv;//各子集的最小兼容性
    //判断是否可以从dp[pre]转移到dp[cur]中
    private boolean check(int cur,int pre,int[] nums,int []dp){
        if (dp[pre] == Integer.MAX_VALUE/2) return false;   //pre状态不合法,所以不可能转移到cur了
        int xor = cur^pre;  //得出pre状态 和 cur状态 的不同
        int[] map = new int[17];    //用于一个子集中 元素 出现次数
        int idx= 0 ;
        //pre->转移到cur中，其中 子集元素出现次数 dp[cur]<-dp[pre]+ dif  (dif这个 子集的元素 )
        while (xor!=0){
            if ((xor&1)==1){
                map[nums[idx]]++;
            }
            idx++;
            xor>>=1;
        }


        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        dv=0;   //子集的 不兼容性
        for (int i = 0; i < map.length; i++) {
            if (map[i]==1){
                max =Math.max(max,i);
                min = Math.min(min,i);
            }
            if (map[i]>1) return false;  //同一 元素 出现了 多次
        }
        dv = max-min;
        return true;
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

补充二叉树的链式实现

//二叉树的结构
typedef int BTData;
typedef struct BinaryTree
{
	BTData x;//数据域
	struct BinaryTree* left;//左子树的根节点
	struct BinaryTree* right;//右子树的根节点
}BTNode;

1
2
3
4
5
6
7
8
9

//前序遍历：根 左子树 右子树
void PrevOrder(BTNode* root)
{
	//root为空是递归的终止条件
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->x);//访问根，这里进行打印操作，也可进行其他操作
	PrevOrder(root->left);//递归访问左子树
	PrevOrder(root->right);//递归访问右子树
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//中序遍历：左子树 根 右子树
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%c ", root->x);
	InOrder(root->right);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//后序遍历：左子树 右子树 根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->x);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//层次遍历二叉树，通过队列实现
void TreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root != NULL)//把整个树的根节点入队
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//保存当前的队头
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->x);//打印
		//如果队头的左右结点不为空，左右结点入队
		if (front->left != NULL)
		{
			QueuePush(&q, front->left);
		}
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}

	QueueDestroy(&q);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27