*团和*滴2022秋招笔试知识点总结（超详细）

admin管理员组

文章数量:1607699

文章目录

• 前言
• 重要知识点
• • Java基础
  • • jdk10新特性与char类型的相关运算
    • 代码块的执行顺序
  • 数据库
  • • like的使用
    • MySQL数据库锁级别
    • 视图
  • 计算机网络
  • • HTTP和HTTPS协议
    • IP组播协议
  • 操作系统
  • • Linux读取参数
    • Linux给命令创建别名
    • Linux的du和df命令
    • epoll
    • PV原语
    • 页式存储管理
    • 设计与测试
  • 算法
  • • 贪心算法
    • 树的遍历
• 结语

前言

真是一个美好的周末…一连做了四套大厂的题目，心里也清楚这几个公司是我暂时还匹配不上的公司，先感受一下难度好让我在后面规划时间，看是需要怎么样的强度，这笔试看大家水平了，笔者感觉呢编程题是需要几百道力扣题的样子，应该都是上面的一些变种，那些思路太重要了，注意分门别类地刷就完事了。
我还是建议大家先试一下ACM模式，这个不像力扣上那么方便，还需要自己通过Scanner的方式输入，输出也需要自己打印出来。我将最近这两场笔试我考到的所需知识点给大家，当然不能直接说原题，题目会变但是知识点是不变的。大致分为以下五个部分，读者也可根据自身情况有的放矢.

重要知识点

Java基础

jdk10新特性与char类型的相关运算

局部变量类型推断
JDK10 可以使⽤var 作为局部变量类型推断标识符。仅适⽤于局部变量，如增强 for 循环的索引，传统 for 循环局部变量；不能使⽤于⽅法形参、构造函数形参、⽅法返回类型或任何其他类型的变量声明；标识符 var 不是关键字，⽽是⼀个保留类型名称，⽽且不⽀持类或接⼝叫 var，也不符合命名规范

@Test
public void testVar() {
	var strVar = "SpringBoot";
	System.out.println(strVar instanceof String);//true
	//repeat(int count)方法:⽤于字符串循环输出
	System.out.println(strVar.repeat(2));
	var flagVar = Boolean.valueOf(true);
	System.out.println(flagVar instanceof Boolean);//true
	for (var i = 0; i < 10; ++i) {
		System.out.println(i);
	}
}

char

16 位，是整数类型，用单引号括起来的 1 个字符（可以是一个中文字符），使用 Unicode 码代表字符，0~2^16-1（65535） 。 注意事项： 不能为 0个字符。 转义字符：\n 换行 \r 回车 \t Tab 字符 " 双引号 \ 表示一个\ 两字符 char 中间用“+”连接，内部先把字符转成 int 类型，再进行加法运算，char 本质就是个数！二进制的，显示的时候，经过“处理”显示为字符。
(引自 : java的基本数据类型有八种 )
char类型用于标识单个字符.通常用来表示字符常量.例如:'A’是编码为65所对应的的字符常量.与"A"'不同,"A"是一个包含字符A的字符串.(在java中,char类型用UTF-16编码表示Unicode代码点的代码单元)
Java中char类型多种赋值方式形式,以及ASCII码的讲解

char字符变量可以实现加减运算
char字符变量是可以进行加减运算的，在运算的时候，我们通过查找对应字符变量值的ASCII值，利用其在ASCII里的对应值进行加减运算。

//如何实现？ 比如：
char a = '1';
char b = '2'
System.out.println("a+b= "+(a+b));
//通过查找ASCII，我们可以知道字符1的ASCII值为 49，2的ASCII值为50，这里指的是十进制，
//所以运行程序我们得到字符相加的结果为99.完成了字符的加法运算，减法也是如此！

char字符变量可以和int整型数值加减么？

可以进行加减，因为char类型是可以转换为int类型的（计算过程中自定进行转换，不需要强制转换的）。
这里首先看一下数据类型：
基本数据类型有以下四种：
整型数据类型有：byte(8bit)、short(16bit)、int(32bit)、long(64bit)、
小数数据类型有：单精度（32bit float）、双精度（64bit double）
boolean类型变量的取值有：ture、false
char数据类型有：unicode字符,16位
对应的类类型：Integer、Float、Boolean、Character、Double、Short、Byte、Long
转换原则 :
从低精度向高精度转换
byte 、short、int、long、float、double、char
注：两个char型运算时，自动转换为int型；当char与别的类型运算时，也会先自动转换为int型的，再做其它类型的自动转换
基本类型向类类型转换
正向转换：通过类包装器来new出一个新的类类型的变量
Integer a= new Integer(2);
反向转换：通过类包装器来转换
int b=a.intValue();
类类型向字符串转换
正向转换：因为每个类都是object类的子类，而所有的object类都有一个toString()函数，所以通过toString()函数来转换即可
反向转换：通过类包装器new出一个新的类类型的变量
所以char类型是可以和int类型进行加减运算的！

代码块的执行顺序

执行顺序：父类静态代码块>子类静态代码块>父类构造块>父类构造方法>子类构造块>子类构造方法
注意：静态代码块只执行一次，并且是在main之前执行
直接这么给结论有点苍白，来看代码

​
//构造块就是非静态代码块
//执行顺序：父类静态代码块（只执行一次，并且是在main之前执行）>子类静态代码块>父类构造块>父类构造方法>子类构造块>子类构造方法
class   Person2
{
    public   int  age;
    public  String name;
    public   int an;
    //构造方法
    public  Person2(int age,String name)
    {
        this.name=name;
        this.age=age;
        System.out.println("父类构造方法");
    }
    //静态代码块
    static {
        System.out.println("父类静态代码块");
    }
    //构造快
    {
        System.out.println("父类构造块");
    }
    //普通方法
    public  void  Info()
    {
        System.out.println("姓名："+this.name+"\t"+"年龄："+this.age+"\t"+"未知："+an);
    }
}
class  Students   extends  Person2{
 
    public Students()
    {
        super(12,"nihao");
        System.out.println("子类的构造方法");
    }
    {
        System.out.println("子类构造块");
    }
    static
    {
        System.out.println("子类静态代码块");
    }
}
 
 
public class 代码块 {
    public static void main(String[] args) {
        Students s=new  Students();
        s.Info();
        int n=s.an;
        System.out.println(n);
    }
}
 ​

结果：

数据库

like的使用

在sql结构化查询语言中，like语句有着至关重要的作用。

like语句的语法格式是：select * from 表名 where 字段名 like 对应值（子串），它主要是针对字符型字段的，它的作用是在一个字符型字段列中检索包含对应子串的。

1. % 包含零个或多个字符的任意字符串：
   1、like ‘Mc%’ 将搜索以字母 Mc 开头的所有字符串（如 McBadden）。
   2、like ‘%inger’ 将搜索以字母 inger 结尾的所有字符串（如 Ringer、Stringer）。
   3、like ‘%en%’ 将搜索在任何位置包含字母 en 的所有字符串（如 Bennet、Green、McBadden）。

2. _（下划线） 任何单个字符：
   like ‘_heryl’ 将搜索以字母 heryl 结尾的所有六个字母的名称（如 Cheryl、Sheryl）。

3. /[ ] 指定范围 ([a-f]) 或集合 ([abcdef]) 中的任何单个字符：
   1，like ‘[CK]ars[eo]n’ 将搜索下列字符串：Carsen、Karsen、Carson 和 Karson（如 Carson）。
   2、like ‘[M-Z]inger’ 将搜索以字符串 inger 结尾、以从 M 到 Z 的任何单个字母开头的所有名称（如 Ringer）。

4. [^] 不属于指定范围 ([a-f]) 或集合 ([abcdef]) 的任何单个字符：
   like ‘M[^c]%’ 将搜索以字母 M 开头，并且第二个字母不是 c 的所有名称（如MacFeather）

5. ？同于DOS命令中的？通配符，代表单个字符 :b?b代表brb,bFb等

6. ‘#’ 大致同上，不同的是代只能代表单个数字。k#k代表k1k,k8k,k0k 。

下面我们来举例说明一下：
例1，查询name字段中包含有“明”字的。
select * from table1 where name like ‘%明%’
例2，查询name字段中含有数字的。
select * from table1 where name like ‘%[0-9]%’
例3，查询name字段中含有小写字母的。
select * from table1 where name like ‘%[a-z]%’
例4，查询name字段中不含有数字的。
select * from table1 where name like ‘%[!0-9]%’

MySQL中like的使用

MySQL数据库锁级别

先说明一下：InnoDB支持表、行(默认)级锁，而MyISAM支持表级锁

相对其他数据库而言，MySQL的锁机制比较简单，其最显著的特点是不同的存储引擎支持不同的锁机制。
MySQL大致可归纳为以下3种锁：
表级锁：开销小，加锁快；不会出现死锁；锁定粒度大，发生锁冲突的概率最高，并发度最低。
行级锁：开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低，并发度也最高。
页面锁：开销和加锁时间界于表锁和行锁之间；会出现死锁；锁定粒度界于表锁和行锁之间，并发度一般

现在大多数MySQL都用InnoDB引擎了，我们着重了解这方面
InnoDB与MyISAM的最大不同有两点：一是支持事务（TRANSACTION）；二是采用了行级锁。
行级锁和表级锁本来就有许多不同之处，另外，事务的引入也带来了一些新问题。

事务（Transaction）及其ACID属性

事务是由一组SQL语句组成的逻辑处理单元，事务具有4属性，通常称为事务的ACID属性。

1. 原子性（Actomicity）：事务是一个原子操作单元，其对数据的修改，要么全都执行，要么全都不执行
2. 一致性（Consistent）：在事务开始和完成时，数据都必须保持一致状态。这意味着所有相关的数据规则都必须应用于事务的修改，以操持完整性；事务结束时，所有的内部数据结构（如B树索引或双向链表）也都必须是正确的
3. 隔离性（Isolation）：数据库系统提供一定的隔离机制，保证事务在不受外部并发操作影响的“独立”环境执行。这意味着事务处理过程中的中间状态对外部是不可见的，反之亦然
4. 持久性（Durable）：事务完成之后，它对于数据的修改是永久性的，即使出现系统故障也能够保持

并发事务带来的问题
相对于串行处理来说，并发事务处理能大大增加数据库资源的利用率，提高数据库系统的事务吞吐量，从而可以支持可以支持更多的用户。但并发事务处理也会带来一些问题，主要包括以下几种情况。

1. 更新丢失（Lost Update）：当两个或多个事务选择同一行，然后基于最初选定的值更新该行时，由于每个事务都不知道其他事务的存在，就会发生丢失更新问题——最后的更新覆盖了其他事务所做的更新。例如，两个编辑人员制作了同一文档的电子副本。每个编辑人员独立地更改其副本，然后保存更改后的副本，这样就覆盖了原始文档。最后保存其更改保存其更改副本的编辑人员覆盖另一个编辑人员所做的修改。如果在一个编辑人员完成并提交事务之前，另一个编辑人员不能访问同一文件，则可避免此问题
2. 脏读（Dirty Reads）：一个事务正在对一条记录做修改，在这个事务并提交前，这条记录的数据就处于不一致状态；这时，另一个事务也来读取同一条记录，如果不加控制，第二个事务读取了这些“脏”的数据，并据此做进一步的处理，就会产生未提交的数据依赖关系。这种现象被形象地叫做“脏读”
3. 不可重复读（Non-Repeatable Reads）：一个事务在读取某些数据已经发生了改变、或某些记录已经被删除了！这种现象叫做“不可重复读”
4. 幻读（Phantom Reads）：一个事务按相同的查询条件重新读取以前检索过的数据，却发现其他事务插入了满足其查询条件的新数据，这种现象就称为“幻读”。
   产生幻读的原因是，行锁只能锁住行，但是新插入记录这个动作，要更新的是记录之间的“间隙”。因此，为了解决幻读问题，InnoDB只好引入新的锁，也就是间隙锁(Gap Lock)，这个后文会继续介绍。

InnoDB都有哪些锁？

1. 行锁：共享锁（lock in share mode）排他锁（for update）
2. 意向锁（表级别）：意向共享锁 意向排他锁
3. 间隙锁
4. Next-key lock：行锁（排他锁）+间隙锁

Mysql数据库中的各种锁

视图

视图(VIEW)也被称作虚表，即虚拟的表，是一组数据的逻辑表示,其本质是对应于一条SELECT语句，结果集被赋予一个名字，即视图名字。
视图本身并不包含任何数据，它只包含映射到基表的一个查询语句，当基表数据发生变化，视图数据也随之变化
查看视图：

DESCRIBE 视图名 或者简写：DESC 视图名
SHOW TABLE STATUS LIKE ‘视图名’
SHOW CREATE VIEW 视图名

创建视图：

#语句格式
#CREATE VIEW <视图名>[(<列名>,[,<列名>])]AS<子查询> [WITH CHECK OPTION]

#CREATE VIEW IS_Student
#AS SELECT Sno,Sname,Sage 
#FROM student
#WHERE sdept='is';
#视图没有主码

#基于多个表创建视图

CREATE VIEW IS_S1(Sno,Sname,Grade)
As
SELECT student.Sno,Sname,Grade
FROM student,sc
WHERE sdept='IS'AND
student.Sno=sc.Sno AND
sc.Cno='1';

计算机网络

每每看到这个我就想祭出我的超级无敌大图，这是之前刷牛客题看到的题解，觉得很好就保存了，经常看看会发现很多问题都能解决了

HTTP和HTTPS协议

HTTP与HTTPS的区别

安全性上，HTTPS是安全超文本协议，在HTTP基础上有更强的安全性。简单来说，HTTPS是使用TLS/SSL加密的HTTP协议
申请证书上，HTTPS需要使用ca申请证书
传输协议上, HTTP是超文本传输协议，明文传输；HTTPS是具有安全性的 SSL 加密传输协议
连接方式与端口上，http的连接简单，是无状态的，端口是 80； https 在http的基础上使用了ssl协议进行加密传输，端口是 443

HTTP的工作过程

1. HTTP由请求和响应构成，是一个标准的客户端服务器模型（C/S）。HTTP协议永远都是客户端发起请求，服务器回送响应
2. 地址解析。域名系统DNS解析域名得到主机的IP地址
3. 封装HTTP请求数据包。封装的内容有以上部分结合本机自己的信息
4. 封装成TCP包，建立TCP连接（TCP的三次握手）
5. 客户机发送请求命令。 建立连接后，客户机向服务器发送一个请求
6. 服务器响应。服务器接到请求后，给予相应的响应信息
7. 服务器关闭TCP连接。一般Web服务器向浏览器发送了请求数据，它要关闭TCP连接
8. 客户端解析报文，解析HTML代码，并渲染

原文地址

IP组播协议

要实现一套完整的组播服务，需要在网络各个位置部署多种组播协议相互配合，共同运作。但不同结构的组播网络所需使用的组播协议不完全一样。IPv4组播网络中所涉及的主要组播协议有以下几个：IGMP、PIM、MSDP、MBGP

原文地址

操作系统

Linux读取参数

可以在shell脚本中像使用其他变量一样使用$1变量。shell脚本会自动将命令行参数的值分配给变量，不需要你作任何处理。
如果需要输入更多的命令行参数，则每个参数都必须用空格分开

$ cat test2.sh
#!/bin/bash 
# testing two command line parameters 
# 
total=$[ $1 * $2 ] 
echo The first parameter is $1. 
echo The second parameter is $2. 
echo The total value is $total. 
$ 
$ ./test2.sh 2 5
The first parameter is 2. 
The second parameter is 5. 
The total value is 10. 
$ 

shell会将每个参数分配给对应的变量

Linux给命令创建别名

用到的命令：
alias 是用来查看系统中有什么别名
source让配置生效临时取消别名的方法
unalias 临时取消别名
cp mnttest.txttmp 使用转义字符取消
bincp mnttest.txttmp 使用绝对路径配置别名临时修改
alias 命令=‘这里面必须是命令’ 例如： # alias rm=echo do not use rm #alias alias cp=…

原文地址

Linux的du和df命令

Linux下查看文件占磁盘大小一般使用du或df命令

df命令:用于显示磁盘分区上的可使用的磁盘空间。默认显示单位为KB。可以利用该命令来获取硬盘被占用了多少空间，目前还剩下多少空间等信息。
du命令:查看使用空间的，但是与df命令不同的是Linux du命令是对文件和目录磁盘使用的空间的查看，还是和df命令有一些区别的
du和df的详情

epoll

说明：linux 下的事件监听机制主要有　poll ,select，epoll,这里主要介绍epoll机制
系统调用

int epoll_create(int size);　　　　　　　//底层实现调用的是epoll_create1(0) ,size内核实现是没有使用的但是有判断不能小于０
int epoll_create1(int flags);　　　　　　//　flags: EPOLL_CLOEXEC
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); //op: EPOLL_CTL_ADD/EPOLL_CTL_MOD/EPOLL_CTL_DEL
int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout); // 0 < maxevents <= MAX_INT/sizeof(struct epoll_event)
int epoll_pwait(int epfd, struct epoll_event *events,int maxevents, int timeout,const sigset_t *sigmask); //和epoll_wait的不同是可以选择屏蔽某些信号中断

epoll 实现机制

1. 通过epoll_create创建一个epollfd文件描述符．kernel里通过struct eventpoll结构体管理epoll的数据（２，３里的红黑树，双向链表都由这个顶层的结构体管理）;
2. 通过epoll_ctl（EPOLL_CTL_ADD　为例）将准备监听的设备描述符插入管理事件监听的红黑树上;（１）fd　ＡＤＤ 的时候会注册一个回调函数１（２）调用监听设备具体实现的poll()函数，执行回调函数１（将等待队列加到唤醒链表里）（３）将新加入的设备描述符等信息打包（struct epitem）插入到红黑树里
3. 调用epoll_wait 等待事件到来．有事件到来后会插入到一个管理ready 事件的链表里，epoll_wait　通过检测这个链表来唤醒当前睡眠的进程，链表不为空唤醒进程，用户取到对应的数据（fd,事件类型　．．．)
4. 何时将ready 的事件加入到链表里？　２步注册的回调函数里又注册了一个回调函数，在事件唤醒时通过　wake_up_locked_poll　等接口调用到回调函数．回调函数实现将准备好的事件加入到ready链表里．

poll /select /epoll　对比

select ,poll 处理基本一致，不同点在于select 使用fd 标注位存放监听的文件描述符（max　＝　１０２４）poll 采用链表存放
select，poll　不会指明哪些文件描述符就绪，需要用户遍历所有加入的文件描述符找打就绪的，epoll返回就绪的文件描述符，可直接遍历处理
select ,poll　使用轮询的方式查看事件是否就绪，epoll　采用回调机制
select,poll　需要通过copy_to_user 的方式将就绪的设备描述符返回，epoll就绪的文件描述符信息直接在内核态使用用户空间指针，减少拉copy

总结：
在监听的设备很少，但是事件频繁发生的情况下使用poll,select效率会高些，epoll适合监听大量的设备，每个设备上发生的事件频率较低，因为epoll 内部的回调有开销．

epoll与enventfd

PV原语

PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。 信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出，其基本思路是用一种新的变量类型(semaphore)来记录当前可用资源的数量。

semaphore有两种实现方式：
1) semaphore的取值必须大于或等于0。0表示当前已没有空闲资源，而正数表示当前空闲资源的数量；
2) semaphore的取值可正可负，负数的绝对值表示正在等待进入临界区的进程个数。
信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语(P、V原语)来访问。初始化可
指定一个非负整数，即空闲资源总数。
P原语：P是荷兰语Proberen(测试)的首字母。为阻塞原语，负责把当前进程由运行状态转换为阻塞状态，直到另外一个进程唤醒它。操作为：申请一个空闲资源(把信号量减1)，若成功，则退出；若失败，则该进程被阻塞；
V原语：V是荷兰语Verhogen(增加)的首字母。为唤醒原语，负责把一个被阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。操作为：释放一个被占用的资源(把信号量加1)，如果发现有被阻塞的
进程，则选择一个唤醒之。
P原语操作的动作是：
(1)sem减1；
(2)若sem减1后仍大于或等于零，则进程继续执行；
(3)若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。
V原语操作的动作是：
(1)sem加1；
(2)若相加结果大于零，则进程继续执行；
(3)若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。
PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。在PV原语执行期间不允许有中断的发生

PV原语操作详解

页式存储管理

页式存储管理为操作系统中的内容，但是在计算机组成原理中的虚拟存储器部分也用到了这一方式。我这就先暂时将这分为操作系统里面了
分区式存储管理最大的缺点是碎片问题严重，内存利用率低。究其原因，主要在于连续分配的限制，即它要求每个作用在内存中必须占一个连续的分区。
如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”。
基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。

连续分配：为用户进程分配的必须是一个连续的内存空间。
非连续分配：为用户进程分配的可以是一些分散的内存空间。
分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。
分页存储管理分为：实分页存储管理和虚分页存储管理

页式存储管理详情

设计与测试

用例之间的关系：包含include、扩展extend、泛化generalization
需求分析之用例模型UML图
遇到了一些关于测试用例和工程规约的东西，不清楚软件工程本专业的学不学，我先在这多补个课。先把我之前学到的一些工程规约图及其作用拿出来分享一下，这是关于一个铁路购票项目的。
用例图(UML)关心的内容：用户角色、用户行为

类图关注内容：模型的抽象、模型的属性和行为、模型的关系
时序图：有哪些对象参与协作、随着时间的推进系统在干什么

状态图(停在那里的状态)：有多少状态、状态触发的条件

活动图：有多少个系统参与协作、每个处理流程的瞬间、判断、循环怎样进行的

算法

贪心算法

1. 贪心法（Greedy Algorithm）定义
   求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择；
   贪心法就是这样的算法：它在每个决策点作出在当时看来最佳的选择，即总是遵循某种规则，做出局部最优的选择，以推导出全局最优解（局部最优解->全局最优解)
2. 对贪心法的深入理解
   （1）原理：一种启发式策略，在每个决策点作出在当时看来最佳的选择
   （2）求解最优化问题的两个关键要素：贪心选择性质+最优子结构
   ①贪心选择性质：进行选择时，直接做出在当前问题中看来最优的选择，而不必考虑子问题的解；
   ②最优子结构：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质
   （3）解题关键：贪心策略的选择
   贪心算法不是对所有问题都能得到整体最优解的，因此选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
   （4）一般步骤：
   ①建立数学模型来描述最优化问题；
   ②把求解的最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解；
   ③证明做出贪心选择后：
   1°原问题总是存在全局最优解，即贪心选择始终安全；
   2°剩余子问题的局部最优解与贪心选择组合，即可得到原问题的全局最优解。
   并完成2°
3. 贪心法与动态规划
   最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了

贪心算法详解与具体用例

树的遍历

先明确树的三种遍历：先序遍历：根左右； 中序遍历：左根右； 后序遍历：左右根
思路：
根据后序遍历，先找到这棵树的根节点的值，也就是数组中最后一个节点(数组长度-1)的位置，由此创建根节点。
然后在中序遍历中找到根的值所在的下标，切出左右子树的前序和中序。
注意：如果后序遍历的数组长度为0，说明是一棵空树。
下面用具体的例子来说明：中序：CDBAE 后序：DCBEA
1、由后序遍历可以确定A是这棵树的根节点，然后根据中序遍历切出A的左右子树，得到CDB属于A的左子树，E属于A的右子树，如下图：

2、接着以B为根节点，在中序遍历中再次切出B的左右子树，得到CD为B的左子树，右子树为空。
3、再以C为根节点，结合中序遍历，得到D为C的右子树，左子树为空。

创建好的二叉树如下图所示：

含代码

结语

写着写着又是新的一周了，希望这周好运会降临在我们头上，会陆续受到面试邀请。继续投简历笔试面试吧。

本文标签： 知识点笔试详细