摘要

红黑树是一种特殊的二叉查找树，能够通过操作实现自平衡。

定义和性质

（1）根节点和叶子节点都为黑色

（2）红色节点的子节点都为黑色

（3）任意一个节点到每一个叶子节点的路径所包含的黑色节点树相同。

红黑树的自平衡通过三种操作实现：左旋、右旋和变色

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

浏览器输入url->>显示主页的过程

浏览器输入url->>显示主页的过程

大致过程：

1. 浏览器通过DNS解析查找域名对应的IP地址（DNS解析）
2. 浏览器向web服务器发送一个HTTP请求（TCP连接 → 发送HTTP请求）
3. 服务器处理请求
4. 服务器发回HTML响应（服务器处理请求并返回HTTP报文）
5. 浏览器显示HTML（浏览器解析渲染界面 → 连接结束）状态码

状态码

一图流解释各协议的作用（HTTP、TCP、IP）

Cookie和Session的区别

1. Cookie 主要用于保存用户信息，session 的主要作⽤就是通过服务端记录⽤户的状态 。
2. Cookie 数据保存在客户端(浏览器端)， Session 数据保存在服务器端
3. 相对来说 Session 安全性更⾼

OSI与TCP/IP各层结构

1. 应用层：通过应用进程间的交互来完成特定的网络应用。包括DNS，HTTP，DNS等协议。
2. 运输层：向两台主机进程之间的通信提供通⽤的数据传输服务（包括TCP和UDP协议） 。
3. 网络层：计算机⽹络中进⾏通信的两个计算机之间可能会经过很多个数据链路，也可能还要经过很多通信⼦⽹。⽹络层的任务就是选择合适的⽹间路由和交换结点， 确保数据及时传送 。（网络层使用IP协议）
4. 数据链路层：两台主机之间的数据传输，总是在⼀段⼀段的链路上传送的，这就需要使⽤专⻔的链路层的协议。 在两个相邻节点之间传送数据时， 数据链路层将⽹络层交下来的 IP 数据报组装成帧 。
5. 物理层：实现相邻计算机节点之间⽐特流的透明传送，尽可能屏蔽掉具体传输介质和物理设备的差异 。

TCP三次握手与四次挥手

三次握手

1. 三次握手过程：客户端(syn)→服务端(syn/ACK)->客户端(ACK)->服务端

2. 为什么要三次握手：

   建⽴可靠的通信信道

   双⽅确认⾃⼰与对⽅的发送与接收是正常的

   第一次：s1(无) s2（s1发送正常，s2接收正常）

   第二次：s1(s2 收发正常， s1收发正常) s2(同上)

   第三次：s1(同上) s2(s1收发正常，s2收发正常)

3. 为什么要传回syn：用来确认信道无误，接收到的就是发送方传来的同一个syn

4. 为什么传回syn还要传回ack：syn用来确认s1到s2的信道无误，而ack用来后续判断s2到s1的信道是否有误

   四次挥手

   

5. 四次挥手过程: s1(FIN) -> s2(ACK,FIN) -> s1(ACK) -> s2

6. 为什么建立连接是三次握手，而断开需要四次挥手：s2在接收到s1的断开请求后，只是表示s1不会再发送数据了，但可以接收数据，自身可能也有数据需要发送，所以FIN和ACK分开发送。

TCP与UDP的区别

windows下的安装

下载安装

安装完成后配置

1
2

$ git config --global user.name "Your Name"
$ git config --global user.email "email@example.com"

创建版本库

版本库又名仓库，英文名repository，你可以简单理解成一个目录，这个目录里面的所有文件都可以被Git管理起来，每个文件的修改、删除，Git都能跟踪，以便任何时刻都可以追踪历史，或者在将来某个时刻可以“还原”。

创建目录

首先，选择一个合适的地方，创建一个空目录：

1
2
3
4

$ mkdir learngit//创建目录
$ cd learngit//切换到刚刚创建的目录下
$ pwd//显示当前所在目录
/Users/michael/learngit

远程仓库

GitHub提供Git仓库托管服务的，所以，只要注册一个GitHub账号，就可以免费获得Git远程仓库。

第1步：创建SSH Key。在用户主目录下，看看有没有.ssh目录，如果有，再看看这个目录下有没有id_rsa和id_rsa.pub这两个文件，如果已经有了，可直接跳到下一步。如果没有，打开Shell（Windows下打开Git Bash），创建SSH Key：

1

$ ssh-keygen -t rsa -C "youremail@example.com"

你需要把邮件地址换成你自己的邮件地址，然后一路回车，使用默认值即可，由于这个Key也不是用于军事目的，所以也无需设置密码。

如果一切顺利的话，可以在用户主目录里找到.ssh目录，里面有id_rsa和id_rsa.pub两个文件，这两个就是SSH Key的秘钥对，id_rsa是私钥，不能泄露出去，id_rsa.pub是公钥，可以放心地告诉任何人。

第2步：登陆GitHub，打开“Account settings”，“SSH Keys”页面：

然后，点“Add SSH Key”，填上任意Title，在Key文本框里粘贴id_rsa.pub文件的内容

添加远程库

题目

假定你知道某只股票每一天价格的变动。

你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。

请设计一个函数，计算你所能获得的最大收益。

示例1

输入：

1

[5,4,3,2,1]

输出：

1

0

tips：

题目

给定一个二叉树和一个值 sum sum，请找出所有的根节点到叶子节点的节点值之和等于 sum sum 的路径， 例如： 给出如下的二叉树， sum=22 sum=22，

返回 [ [5,4,11,2], [5,8,9]]

示例1

输入：

1

{1,2},1

输出：

1

[]

示例2

题目

假定你知道某只股票每一天价格的变动。

你最多可以同时持有一只股票。但你最多只能进行两次交易（一次买进和一次卖出记为一次交易。买进和卖出均无手续费）。

请设计一个函数，计算你所能获得的最大收益。

示例1

输入：

1

[8,9,3,5,1,3]

输出：

1

4

tips：

题目

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

示例1

输入：

1

{1,2,3,4,5,6,7}

输出：

1

true

思路

题目

给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。

示例1

输入：

1

"1A2C3D4B56","B1D23CA45B6A"

输出：

1

"123456"

tips：

1

1≤∣str 1∣,∣str 2∣≤5000

思路