[toc]
很常见的搜索全排列题
但是处理这个字符串折腾了我好久,看我下面这个也太麻烦了
1 | List<char[]> lists = new ArrayList<>(); |
看看答案怎么做的，好像其他人都是逐个判断的。
也是，频繁substring还是很耗时间的，不建议
我的答案：
1 | class Solution { |
2244. 完成所有任务需要的最少轮数 - 力扣（LeetCode）
一眼想到动态规划，但就是要注意题意得先排序,还要注意溢出的问题
1 | class Solution { |
剑指 Offer II 104. 排列的数目 - 力扣（LeetCode）
看起来以为要搜索，结果一看数据范围：
target最大1000，且都是正数，那么可以直接基于总和做动态规划了，因为不会有超过target的情况出现
1 | class Solution { |
[toc]
应用层
表示层（数据信息变化）
会话层（建立进程间会话）
运输层
网络层
链路层
物理层
应用层（FTP\SMTP）
运输层（TCP\UDP）
网络层（IP、ICMP、IGMP）
网络接口层（MAC， 设备驱动，接口卡，以太网，令牌环）
应用层——数据
运输层——数据报
网络层——分组/包
链路层——数据帧
物理层——比特，电流，电缆
封装：从应用程序发出的数据，到链路层的过程种， 数据会不断变长，添加各种首部信息
分用：从链路传到应用程序时，会慢慢去掉首部
服务区别：
重复型服务： 来一个连接，处理一个， 处理完再接收下一个（UDP）
并发型服务： 来一个则生成一个服务器做处理，可同时处理多个（TCP）
Internet: 通过TCP/IP通信的主机集合
internet： 只所有的通信住机
[toc]
因为http是非常重要的东西，restful经常问道， 所以单独抽出一章节讲解。
这个最好看图解HTTP笔记里的内容。
A:
A:
在使用长连接的情况下，当一个网页打开完成后，客户端和服务器之间用于传输HTTP数据的TCP连接不会关闭，客户端再次访问这个服务器时，会继续使用这一条已经建立的连接。
Keep-Alive不会永久保持连接，它有一个保持时间，可以在不同的服务器软件（如Apache）中设定这个时间。
实现长连接需要客户端和服务端都支持长连接。
HTTP协议的长连接和短连接，实质上是TCP协议的长连接和短连接。
TCP短连接长连接都由客户端发起，而TCP长连接的保活功能主要为服务器应用提供。
如果客户端已经消失而连接未断开，则会使得服务器上保留一个半开放的连接，而服务器又在等待来自客户端的数据，此时服务器将永远等待客户端的数据。保活功能就是试图在服务端器端检测到这种半开放的连接。也因为短连接、长连接的实现在HTTP之外，与HTTP无关，从HTTP自身来看，HTTP依然是无连接的
A:
A:
状态码分类表
各类别常见状态码：
200 OK：表示从客户端发送给服务器的请求被正常处理并返回；
204 No Content：表示客户端发送给客户端的请求得到了成功处理，但在返回的响应报文中不含实体的主体部分（没有资源可以返回）；
206 Patial Content：表示客户端进行了范围请求，并且服务器成功执行了这部分的GET请求，响应报文中包含由Content-Range指定范围的实体内容。
301 Moved Permanently：永久性重定向，表示请求的资源被分配了新的URL，之后应使用更改的URL；
302 Found：临时性重定向，表示请求的资源被分配了新的URL，希望本次访问使用新的URL；
301与302的区别：前者是永久移动，后者是临时移动（之后可能还会更改URL）
303 See Other：表示请求的资源被分配了新的URL，应使用GET方法定向获取请求的资源；
302与303的区别：后者明确表示客户端应当采用GET方式获取资源
304 Not Modified：表示客户端发送附带条件（是指采用GET方法的请求报文中包含if-Match、If-Modified-Since、If-None-Match、If-Range、If-Unmodified-Since中任一首部）的请求时，服务器端允许访问资源，但是请求为满足条件的情况下返回改状态码；
307 Temporary Redirect：临时重定向，与303有着相同的含义，307会遵照浏览器标准不会从POST变成GET；（不同浏览器可能会出现不同的情况）；
400 Bad Request：表示请求报文中存在语法错误；
401 Unauthorized：未经许可，需要通过HTTP认证；
403 Forbidden：服务器拒绝该次访问（访问权限出现问题）
404 Not Found：表示服务器上无法找到请求的资源，除此之外，也可以在服务器拒绝请求但不想给拒绝原因时使用；
500 Inter Server Error：表示服务器在执行请求时发生了错误，也有可能是web应用存在的bug或某些临时的错误时；
503 Server Unavailable：表示服务器暂时处于超负载或正在进行停机维护，无法处理请求；
在 HTTP 协议中，重定向操作由服务器通过发送特殊的响应（即 redirects）而触发。HTTP 协议的重定向响应的状态码为 3xx 。
浏览器在接收到重定向响应的时候，会采用该响应提供的新的 URL ，并立即进行加载；大多数情况下，除了会有一小部分性能损失之外，重定向操作对于用户来说是不可见的。
HTTP 的重定向
A:
直接转发方式（Forward），客户端和浏览器只发出一次请求，Servlet、HTML、JSP或其它信息资源，由第二个信息资源响应该请求，在请求对象request中，保存的对象对于一个每个信息资源是共享的。
间接转发方式（Redirect）实际是两次HTTP请求，服务器端在响应第一次请求的时候，让浏览器再向另外一个URL发出请求，从而达到转发的目的。
直接转发就相当于：“A找B借钱，B说没有，B去找C借，借到借不到都会把消息传递给A”；
间接转发就相当于：“A找B借钱，B说没有，让A去找C借”。
A:
A:
对网址申请信息进行摘要， 避免签名内容过长。同时也避免了逆向推导原网址信息的过程。
A:
一个证书或证书链的拆封操作，是为了
从中获得一个公钥。可示为X1p?X1<
右操作数则为该认证机构所颁发的一个证书。如果能正确解开，输出结果为用户的公钥
证书链验证的要求是，路径中每个证书从最终实体到根证书
都是有效的，并且每个证书都要正确地对应发行该证书的权威可信任性CA。操作表达式为 Ap?A<>B<
指出该操作使用A的公钥，从B的证书中获得B的公钥Bp，然后再通过 Bp来解封C的证书。操作的最终结果
说人话就是下游证书解出来是上游父证书的密文公钥，然后继续解
A:
A:
首先， 请求有个Cache-Control， 里面可以指定最大缓存时间。
A:
服务端的响应中，携带last-modified时间给客户端。
客户端缓存超期时，把last_modified这个时间传递过去， 服务端校验如果发现时间一致，则不做业务处理，直接返回304， 让客户端直接继续用本地缓存即可。
A: 给get请求的url中加个时间戳。或者设置no-cache指令
关于浏览器缓存的其他解答
A:
A:
完全可以加，没有问题， GET和POST本质上就是TCP链接，并无差别。但是由于HTTP的规定和浏览器/服务器的限制，导致他们在应用过程中体现出一些不同。 例如某些框架可能针对get和post做过封装来限制一些语义。
A:
如果用了HTTPS， 则post比get安全， 否则是一样的的，因为传输时都是明文传输。
A:
区别一：
区别二：
区别三：
A:
所谓的 HTTP 流水线，是客户端可以先一次性发送多个请求，而在发送过程中不需先等待服务器的回应，可以减少整体的响应时间。
举例来说，客户端需要请求两个资源。以前的做法是，在同一个 TCP 连接里面，先发送 A 请求，然后等待服务器做出回应，收到后再发出 B 请求。HTTP 流水线机制则允许客户端同时发出 A 请求和 B 请求。
A:
*/*;q=0.8 //浏览器支持的请求类型A:
HTTP协议作为无状态协议，对于HTTP协议而言，无状态同样指每次request请求之前是相互独立的，当前请求并不会记录它的上一次请求信息。那么问题来了，既然无状态，那完成一套完整的业务逻辑，发送多次请求的情况数不胜数，使用http如何将上下文请求进行关联呢？机智的人类通过优化，找到了一种简单的方式记录http协议的请求信息.
根据这个会话ID，以建立多次请求-响应模式的关联数据传递, 这就是cookie和session对无状态的http协议的强大作用。
服务端生成这个全局的唯一标识，传递给客户端用于唯一标记这次请求，也就是cookie；而服务器创建的那个map结构就是session。
A:
A:
会话（Session）跟踪是Web程序中常用的技术，用来跟踪用户的整个会话。
常用的会话跟踪技术是Cookie与Session。
Cookie通过在客户端记录信息确定用户身份，Cookie具有不可跨域名性
Session通过在服务器端记录信息确定用户身份。
Session需要使用Cookie作为识别标志
cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗考虑到安全应当使用session。
session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能考虑到减轻服务器性能方面，应当使用cookie
Cookie机制是通过检查客户身上的“通行证”来确定客户身份的话，那么Session机制就是通过检查服务器上的“客户明细表”来确认客户身份。Session相当于程序在服务器上建立的一份客户档案，客户来访的时候只需要查询客户档案表就可以了。
A:
URL地址重写是对客户端不支持Cookie的解决方案。URL地址重写的原理是将该用户Session的id信息重写到URL地址中。服务器能够解析重写后的URL获取Session的id。这样即使客户端不支持Cookie，也可以使用Session来记录用户状态
A:
保证session一致性的架构设计常见方法：
建议：
web层、service层无状态是大规模分布式系统设计原则之一，session属于状态，不宜放在web层
让专业的软件做专业的事情，web-server存session？还是让cache去做这样的事情吧
A:
Token的引入：Token是在客户端频繁向服务端请求数据，服务端频繁的去数据库查询用户名和密码并进行对比，判断用户名和密码正确与否，并作出相应提示，在这样的背景下，Token便应运而生。
Token的定义：Token是服务端生成的一串字符串，以作客户端进行请求的一个令牌，当第一次登录后，服务器生成一个Token便将此Token返回给客户端，以后客户端只需带上这个Token前来请求数据即可，无需再次带上用户名和密码。最简单的token组成:uid(用户唯一的身份标识)、time(当前时间的时间戳)、sign(签名，由token的前几位+盐以哈希算法压缩成一定长的十六进制字符串，可以防止恶意第三方拼接token请求服务器)。
使用Token的目的：Token的目的是为了减轻服务器的压力，减少频繁的查询数据库，使服务器更加健壮。
Token 、Cookie和Session的区别
[toc]
Q: DNS为什么要使用UDP协议呢？
A:
DNS这个东西通信模式相当固定，报文基本上一个包搞定。大多数情况一问一答就结束了。
你三次握手来回3个包呢，人家一来一回就已经结速了，这种时候搞什么TCP？有必要中间连续穿好几次数据保证可靠性么？
域名由 “标号.标号.标号”组成
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Rk1b92vm-1613753140851)(en-resource://database/2048:1)]
标号由字母和“-”组成。
标号不超过63个字符
总域名（标号之和）不能超过255
分为根、顶级、二级、三级
顶级域名分类：
域名和ip可以是多对多的关系， 即1个域名可以对应多个ip（分布式多活）， 1个ip也可以被绑定成不同的域名。
递归其实就是从根域名如果找不到， 则让根域名发起请求向顶级域名查询。
即发起请求的对象变了，这种显然会占用根域名服务器的客户端资源，明显不好。
基于TCP传输，可靠性高。
客户端发送PASV命令
可以看到FTP服务器会给每个连接建立相应独立的控制进程和数据进程。
其实就是发送了PORT命令：
PORT h1,h2,h3,h4,p1,p2 (h1-h4是IP地址，p1-p2是端口号)
可以看到下载过程是FTP服务器向对方发起连接
单帧滑动-停止等待协议
- 一次只发一帧，1次只收一帧，并确认占有信道后才继续
- 发送端：收到ack确认后，才会发下一个，每个都有个定时器
- 接收端：序号不匹配递增的话都会丢弃。
FTP和TFTP，都可能是有人把文件存在一个集中的服务器上，大家去下载上传。
而P2P则是建立了主机和主机间的直接通信， 不需要依赖中间服务器
其实就是邮件客户端，类似于foxmail、outlook、qq邮箱等exe程序，
使用SMTP接收协议和POP读取服务完成整套邮件系统协议。
发送端发送QUIT命令
接收端返回221同意释放连接
注意前面3步只是完成了从发送者到 接收者所属邮件服务器的步骤，还没有到接收者本地的邮箱应用。
接收者客户端会通过POP协议定期去拉取邮件。
[toc]
#不同的存储引擎支持不同的事务处理
不支持事务的话，性能会高，但是可靠性就差。
简易记法： RU\RC\RR\SE
第一个R是read， U是uncommit， C是uncommit， R是repeated， SE是顺序
允许其他事务继续访问该行数据，但是未提交的写事务将会禁止其他事务访问该行，会对该写锁一直保持直到到事务提交。
区别就是写的时候，未提交的事务会禁止，相当于写的过程会让读不可见。
能解决脏读， RC隔离级别保证了对读取到的记录加锁(记录锁)
Repeateable Read 保证同一笔数据在事务中，必须是相同的，不会让他变化。
能避免不可重复度和脏读， “可能”避免幻读
RR隔离级别保证对读取到的记录加锁(记录锁)，同时保证对读取的范围加锁，新的满足查询条件的记录不能够插入(间隙锁)。
Serializable 所有事务都必须依次顺序执行。 都能解决
所有的读操作都是当前读，读加读锁(S锁)，写加写锁(X锁)。在该隔离级别下，读写冲突，因此并发性能急剧下降，在MySQL/InnoDB中不建议使用。
简易版：
这是mysql的默认事务型引擎
用于处理短期事务（不常回滚的），但本质上还是事务型的存储引擎
数据存储在tablespace中（一堆又innoDB管理的文件，我们看不懂的那种文件）
使用MVCC支持高并发，实现4个隔离级别， 有间隙锁
使用聚簇索引
MYSQL5.1之前，是默认的存储引擎
不支持事务和行级锁！也就是说不支持修复！
表存在2个文件中： 数据文件和索引文件
只能针对表加锁，不能针对行
有修复操作，但是用于修复表的错误（而不是回滚这种操作)
支持全文索引
如果表导入数据后不再更新，可以用MyISAM压缩表， 而且解压开销不大。
Archive： 只支持insert和select、压缩写、支持行级锁、不是事务引擎
blackhole： 会丢弃所有插入的数据，但是会记录日志。（一般用于数据备份、日志审计）
csv：把csv文件当作mysql表。不支持索引
Federated： 是访问mysql的一个代理引擎。本质还是连接mysql。默认禁用
memory引擎： 希望快速访问不存盘， 重启后丢失也无所谓，可以i用这个，类似于H2内存数据库。
用作缓存非常不错。
NDB集群引擎： 分布式mysql集群
A:
A:
[toc]
同理链路层就是物理上相邻的2个机器如何通信，物理层是电路上的通信
端口号是传输层重要的概念。
① 为进程适应不同操作系统提供一个复用和分用的软件
复用：发送方不同进程都用同一种协议传输，目的端口号承担了这个工作
分用：接收方把IP报文组装交付时，通过端口号确认交付给谁② 端口是进程的重要交互地址。
即由端口确定交给主机上的哪个进程。
③ 只具有本地意义，只对本机有效
端口号共16位，因此最大为65535
服务器端口号（做listen用的端口号）有2类：
熟知端口号有以下：
HTTP:80
HTTPS:443
DNS:53
FTP:21
TFTP:69
SNMP:161
TELNET:23
SMTP:25
UDP和TCP有各自的专属端口号，因此不会重复和干扰。
TCP全称
Transmission Control Protocol， 即传输控制协议。
基于套接字传输
套接字：IP+端口号
tcp的可靠性如下：
| 位数 | 含义 | 详情 |
|---|---|---|
| 16 | 源端口 | 因此端口号最多16位 |
| 16 | 目的端口 | |
| 32 | 报文序号 | 该报文的序号 |
| 32 | 确认号 | 期望收到的下一个报文序号。如果确认号位N，说明N-1都已经收到 |
| 4 | 数据偏移 | 数据部分的起始位置，可以理解为首部长度。单位是4字节。 |
| 6 | 保留位 | 没用，全部置成0 |
| 1 | URG紧急指针标志 | 是否存在紧急数据 |
| 1 | ACK标志 | 是否是确认报文 |
| 1 | PSH推送标志 | 是否需要尽快上交进程 |
| 1 | RST复位标志 | 是否需要重建连接 |
| 1 | SYN同步建立连接标志 | 是不是连接建立期间的报文 |
| 1 | FIN终止标志 | 是否是终止连接期间的报文 |
| 16 | 窗口 | 收到ack前对方可发送回来的数据量 |
| 16 | 校验和 | 校验首部+数据+伪首部（伪首部指携带了ip的首部） |
| 16 | 紧急指针位置 | 紧急数据放在末尾，需要给出紧急数据的长度，便可推断位置 |
| 0-320 | 可变选项 | 一些TCP选项，例如 最大报文长度、时间戳等。最长40字节 |
| ? | 填充位 | 保证首部长度为4字节整数倍 |
从上面可以看到：
A:
在TCP的发送端和接收端，有一个窗口的概念，直接用图片的方式简单明了回忆一下：
这里可以看到接收端一次性接收的缓存是有限的，所以进程出现问题迟迟没有接收数据，那么会在ack里告知还能发多少份。
这个叫通告窗口，即告知接收端还能收几份数据（TCP报文里的窗口位就是这个）
如果接收端的接收缓存用完，导致返回的ack报文里提示窗口为0，则发送端无法发送数据，此时会启动坚持定时器：
每隔5s发送1个字节的小报文，来查看对方窗口响应。当窗口不再为0，则结束坚持定时器
上面提到的坚持定时器机制里，导致了每次只发一小点数据。
避免措施：
1. 接收方设定一个最小窗口阈值，不通告小窗口
2. 发送方设定一个最小窗口阈值，每次发送满一定长度的报文
3. 发送手头所有数据切不接收ack
TCP通过三次握手建立连接，四次挥手结束连接
把这个图牢记于心就不会有问题：
CLOSED状态：建立连接前的初始状态即关闭状态在建立连接前，先从CLOSED状态变成LISTEN状态（监听状态，表示可以传信号了）
建立握手3次原因：一方接收到syn报文后，需向对方回应一个ack。三次握手中，第一个是sync报文，第二个是ack、sync报文合在一起，第三个ack报文。这样就都回应了ack，需要3次。
关键在于最后一次需要一个对 接收端sync的ack响应。
TCP中发送端发送fin后，就会将自己关闭。
但是接收端一方接收到fin报文后，数据可能还没发送完成。
所以需要先发完ack，再发fin，所以这里会多一次挥手。 最后ack是对fin的确认
能。收到第一个fin报文后，它可能刚好没有数据要传输了，fin和ack报文一起回应，对方再回应ack，总共三次，挥手完毕。实际中抓报文，有很多这样的情况。
A:
1.若最后一步客户发出的ACK丢失了，那么服务器将重发FIN，所以必须维持TIME_WAIT状态到可能的第二次重发FIN的时间。
2.为了避免在终止连接后再次重新建立新连接时，收到之前那次连接“迷路”的分组，要维持一个TIME_WAIT状态以便吸收掉迷路的分组。
2边同时发送SYNC
2边同时收到后， 就会发现自己在还没收到SYNC-ACK的情况下收到了新的SYNC，说明发生了"同时打开"的情况。
此时他会直接发送ack，并且不再等待sync-ack响应了，直接进入ESTABLISHED状态。所以此时仅需2次握手（当然整体上看是4次，一边各2次）
当2者发生同时关闭，即同时发出FIN时，会进入CLOSING状态，收到相互的ACK后进入TIME_WAIT状态. 即此时需2次挥手（整体上看是4次）
每一个交互按键都会产生一个数据分组，每次从客户传到服务器的是一个字节的按键。而Rlogin需要远程系统回显客户键入的字符，这样就会产生4个报文段：
（1）来自客户的交互按键
（2）来自服务器的按键确认
（3）来自服务器的按键回显
（4）来自客户的按键回显确认
当数据交互很快时， 可能会有很多小分组。
开启nagle后，会把小分组做合并一起发送。
A:
TCP粘包就是指发送方发送的若干包数据到达接收方时粘成了一包
从接收缓冲区来看，后一包数据的头紧接着前一包数据的尾
出现粘包的原因是多方面的，可能是来自发送方，也可能是来自接收方。
A:
发送方原因： 开启了nagle算法
接收方原因：如果TCP接收数据包到缓存的速度大于应用程序从缓存中读取数据包的速度，多个包就会被缓存，应用程序就有可能读取到多个首尾相接粘到一起的包
A:
如果发送方发送的多组数据本来就是同一块数据的不同部分，比如说一个文件被分成多个部分发送，这时当然不需要处理粘包现象
如果多个分组毫不相干，甚至是并列关系，导致应用层取出时无法识别各份数据，那么这个时候就一定要处理粘包现象了
A:
A:
UDP则是面向消息传输的，是有保护消息边界的，接收方一次只接受一条独立的信息，所以不存在粘包问题。
举个例子：有三个数据包，大小分别为2k、4k、6k，如果采用UDP发送的话，不管接受方的接收缓存有多大，我们必须要进行至少三次以上的发送才能把数据包发送完，但是使用TCP协议发送的话，我们只需要接受方的接收缓存有12k的大小，就可以一次把这3个数据包全部发送完毕。
异常情况时，会把报文里的复位表示RST置为1。有3种情况会发送复位报文
①端口不存在
②进程异常终止
③客户端异常退出， 服务器没有收到任何fin，此时称为TCP半打开状态。如果TCP配置了心跳，则可以检测
半关闭
TCP的半关连接是指：TCP连接只有一方发送了FIN，另一方没有发出FIN包，仍然可以在一个方向上正常发送数据。
半连接
三次握手中，主动发起握手的一方不发最后一次ACK，使得服务器端阻塞在SYN_RECV状态半连接攻击（SYN攻击）：会耗尽服务器资源，使得真正的请求无法建立连接。
这块概念很多很乱，我按问题整理了一下，一步步来
TCP的拥塞避免等机制对于初学者来说还是比较复杂的，工作中如果开发时偏应用层，那么大部分时候就会摸不到这个机制，感受也就没那么深了。
但如果你的开发过程涉及数据传输，一直在重传、超时之类的方案里有困惑的话，不妨重新学一学可靠性最精致的TCP协议。
所以这里我抛去死记硬背的那堆概念，用10个连续的问题来学习这个机制，注意看的时候先自己思考一下如果是自己，会怎么设计，再去看实际的TCP设计，来理解它的精妙之处。
A:
不是。
建立连接后，会先只发1条， 然后发2条，接着再发4条，逐步增加。
这个过程叫 “慢启动”。
这个1、2、4递增的数量被称之为 拥塞窗口 cwnd
可以理解为TCP希望刚开始，可以大胆点，不断加数量。但为了保险期间还是从1条还是倍增。
A:
不会无限倍增。
当到达慢启动门限ssthreshold时，会变成每次都增加1条。
这个过程叫拥塞避免过程， 也有叫他拥塞避免算法的
可以理解为tcp感觉到有风险了，于是开始慢慢地、小心翼翼地1条1条地添加发送条数。
A:
随着每次发送的数量越发越多， 最终会超出带宽限制，于是就会有某条报文发生超时。
有可能是发的中途丢了， 亦或者是返回的数据全阻塞住了，一条都回不来。
当发送端检测到发生超时时，就会让 慢启动门限ssthreshold = 当前拥塞窗口cwnd/2
接着cwnd 重新置为1，从新开始 慢启动算法。
这样的好处在于可以检测到每次发送的上限，动态调整发送窗口。
上面的过程叫做 超时重传。
注意发生超时重传时， cwnd会重置成1。
A:
每次发送数据包的时候， 都会有一个相应的计时器，一旦超过 RTO(超时时间） 而没有收到 ACK， TCP就会重发该数据包。
没收到 ACK 的数据包都会存在重传缓冲区里，等到 ACK 后，就从缓冲区里删除。
A:
通过“每次报文的往返时间样本”和“之前样本的偏差值”动态计算出来的。
A:
会使用karn算法： 发生重传时，不更新这次的RTT样。选用后面收到的ack
修正karn： 为了避免发生重传后，实际RTT都变慢了，导致一下子所有请求都超时， 会在发生重传时，把RTO假大1倍。
A:
如果能正常接收其他报文的ACK， 只是中间的部分报文丢了， 则有另一个办法。
接收端有一个冗余确认机制：
当A发现连续3次收到了ack=3时，就会觉察到不对劲，我都发3次了你还是说没收到，可你又能正常返回其他ACK给我，是不是我发的太多了？
上面这个判断3次的重传算法叫“快重传”。
于是A会马上进入 “快速恢复”。
和之前类似，慢启动门限ssthreshold = 当前拥塞窗口cwnd/2
但是！！ 新的拥塞窗口cwnd会设置成ssthreshold/2， 而不是1。
而且不会走慢启动倍增的那种，而是走拥塞避免， 逐步+1的那种。
A:
因为前面发生超时重传时， 是比较严重的情况， 超时时间内一个ACK都没收到。就好像来回数据都凭空消失了。
而快速重传发生时， 还是能收到部分ack的， 只是丢失了部分数据， 说明拥塞没那么严重，于是可以大胆一点将cwnd削减到1/4， 而不是直接从1开始。
到了这里，基本就能理清楚超时重传和快重传的区别了，重点是理解这2个区别是怎么来的。后面再补几个问题，避免你和其他概念搞混，但不会说得太深，具体需要你自己去扩展学习了。
A:
路由器有缓存，IP分组接收过多时就会耗尽空间，丢弃数据。详细可以看路由器的数据转发原理。
A:
坚持定时器和超时、网络拥塞没有关系， 和通告窗口即对端的接收能力有关。
简单来说， 就是对方的传输层缓冲区（接收端窗口）满了，告诉你别发了，我吃不下了，于是返回通告窗口为0。
但你想知道啥时候可以发，于是就启动一个坚持定时器，每隔5s发送1个字节的小报文，小小地试探下。当通告窗口不为0了，就重新开始发。
网络层的多播和广播机制，需要依赖传输层的UDP。
每次调用程序里多播的接口时，都会产生1个UDP消息，没有那种可以复用的UDP连接。
UDP数据报的最大长度，和应用程序可读写的数据报最大长度有关，和TCP/IP内核有关。
当数据报长度大于程序可读写长度，会引发 数据截断。所以udp数据的长度必须要控制好，毕竟他无法根据MTU做分片。
怎么确认MTU多大？
可以用taceroute命令检测MTU， 本质上是把TCP报文设置成不分片，然后逐步增大，直到发生了ICMP不可达的报错。
如果一次性发送了6个UDP数据报， 并且在链路层有6次ARP请求， 接收端收到6个UDP后，只会发送一个ARP响应。
UDP一般用于本地小范围通信， 所以差错其实相比TCP还小一点。
TFTP（小文件传输）
DNS（域名解析）
SNMP(简单网络管理协议）
IGMP
BOOTP（无盘系统引导）
RTP(实时传输协议)
多媒体应用
A:
可以实现，但必须在应用层做改造。
详细说明：送端发送数据时，生成一个随机seq=x，然后每一片按照数据大小分配seq。数据到达接收端后接收端放入缓存，并发送一个ack=x的包，表示对方已经收到了数据。发送端收到了ack包后，删除缓冲区对应的数据。时间到后，定时任务检查是否需要重传数据。
目前有多种开源程序利用udp实现了可靠的数据传输。分别为RUDP、RTP、UDT
[toc]
分类表示法已经不常用了。
网络号全0，但主机号非全0的某个ip就是指本网络的某个主机
网络号不为全1，但主机号为1的ip，则指某个网络的广播地址
全0，指本网络的本主机
全1，指本网络的广播地址
环回地址，指127.0.0.1，在同一台主机上进行网络传输
私有地址，指不会参与路由器转发的地址,， 只会参与本局域网，发给本局域网的交换机：
A类： 10.0.0.0-10.25.255.255
B类： 172.16.0.0-172.31.0.0
C类： 192.168.0.0-192.168.255.255
Classless Inter-Domain Routing 无类型域间选路
CIDR有三种编址方式：
对于CIDR编址
子网号的全0和全1没有特殊含义，但不可设置成全0或者全1。
主机号的全0指本网络， 全1指广播。（网络号仍然遵从ABCD地址的规则）
IP报文的首部至少有20个字节（160位），首部如下：
| 位数 | 含义 | 详情 |
|---|---|---|
| 4 | 版本 | IPV4或者IPV6 |
| 4 | 首部长度 | 单位是字（4字节 |
| 8 | 区分服务 | 设置服务的时延、吞吐量、可靠性，一般不用 |
| 16 | IP报文总长度 | 单位字节 |
| 16 | 报文标识 | 用于分片后的同报文组装。相同报文的不同分片，该值相同 |
| 3 | 分片标志 | 判断是否可分片或者是否是分配最后一个 |
| 13 | 片偏移 | 用于按顺序组装同报文的分片 |
| 8 | 生存时间TTL | 该报文最大跳数，每经过一次转发就减一 |
| 8 | 协议类型 | ICMP/IGMP/TCP/UDP |
| 16 | 首部校验和 | 用于和首部做校验，看首部是否正确 |
| 32 | 源IP地址 | |
| 32 | 目的IP地址 | |
| ？ | 任选项 | 很少被使用，最多40字节 |
上面可以看到IP报文的以下限制：
A:
Hub集线器在同一个冲突域通信无法分割；交换机在同一个广播域通信，可分割冲突域；路由器实现不同广播域间通信，可分隔广播域。
假设某个路由器在N1网络，他的路由表如下：
| 目的网络 | 下一跳地址 | 解释 | 到目的网络距离 |
|---|---|---|---|
| N1 | 0.0.0.0 | 假设目的网络就是路由器所在网络，说明可以直接交付给本网络的主机了，不用再转发，所以地址为全0 | 0 |
| N2 | R2 | 如果为N2，则会发给R2路由 | 4 |
| 0.0.0.0 | R1默认路由 | 如果路由表找不到目的网络，则会默认转给R1处理，0.0.0.0是默认转发网络的标识 | ？ |
| 特定IP地址 | R3 | 这种特定地址的选择是管理员配置的 | 3 |
如果路由表中的目的网络由很多，怎么确定IP和路由表中的目的网络是匹配的？
使用 最长前缀匹配， 即前缀匹配得最多的就是目的网络。
优化算法可用二叉线索树来确认最长前缀。
Q： 为什么要用二叉线索树来 判断最长匹配前缀？ 字典树不可以吗？
A:
全称Address Resolution Protocol，地址解析协议。
从主机发给路由， 或者路由发给路由时，底层还是得封装一层mac地址然后往下交给交换机。
那么ip和mac地址的对应关系， 是怎么得知的？
答案就是ARP协议
本质就是当mac缓存表里没有ip和mac的对应关系时， 主机或者路由会广播ARP报文， 对应ip方向的交换机会把报文发送回来，这时候就直到mac地址和ip的对饮关系了。
由mac地址反取ip。
因为ip不存在，无法直接转给给路由。所以会比ARP难。
过程：
1）将源设备和目标设备的MAC地址字段都设为发送者的MAC地址和IP地址，发送主机发送一个本地的RARP广播，能够到达网络上的所有设备，在此广播包中，声明自己的MAC地址并且请求任何收到此请求的RARP服务器分配一个IP地址；
? 2）本地网段上的RARP服务器收到此请求后，检查其RARP列表，查找该MAC地址对应的IP地址；
? 3）如果存在，RARP服务器就给源主机发送一个响应数据包并将此IP地址提供给对方主机使用；如果不存在，RARP服务器对此不做任何的响应；
? 4） 源主机收到从RARP服务器的响应信息，就利用得到的IP地址进行通讯；如果一直没有收到RARP服务器的响应信息，表示初始化失败。
全称Internet control message protocl，网络控制报文协议
他会包装在IP的数据报文中，并把首部的协议类型改成ICMP那个数字。
首部总共8个字节，分别为
2字节的ICMP类型
2字节的ICMP报文代码（类似错误码）
4字节的校验和
后面就是数据部分了。
常见的2种用途：
差错报告有以下其他特点：
* ICMP自身出错时，不会再发ICMP差错报文
* 如果是报文分配后发生错误，则只会发1次，而不会每个分片发一次
* 不针对多播，不针对127.0.0.1、0.0.0.0等特殊的地址发送差错报文，不可广播（避免广播风暴）
全称Dynamic Host Configuration Protocol， 动态主机配置协议
当某个局域网内新增了一台主机，这个主机的ip是怎么生成的呢？这就会用到DHCP协议
主机所在网内会有一台DCHP服务器。
当新主机加入时，发生如下之事：
有以下几个注意点：
DCHP可以认为是基于UDP的应用层协议，但本质是为了寻求新主机的动态ip地址
可以理解为 在一个复杂的拓扑图下， 怎么选择最优的一个路由做目的地址的下一跳。
有2种方式：
全称Routing Information Protocol,路由信息协议
是一种动态路由信息协议。
路由只会和相邻的其他路由交换信息。
交换的是路由表的信息，关键在于目的网络和距离
之前路由表里知道了表里会存储 到目的网络的距离即跨越路由数量，那么只要拿到周边所有路由的距离表， 看下哪个方向最小， 然后把下一跳地址选为最小的那个路由方向即可。
使用UDP广播，把自己的路由报文发给周边的其他路由。
当路径不可达时，会导致2个路由之间不断叠加该目的地址的距离，直到16时，会被设置成不可达。
所以RIP本质也是基于UDP的应用层协议，但是目的是为了网络层的最优路由选取。
open shortest path first，开放最短路径优先协议
指路由器里有全网的拓扑结构，使用最短路算法计算最优路由
因此路由会把自己的连接情况通过OSPF协议发给所有其他路由，以建立拓扑图。
这个是属于IP层的协议，不借助UDP。
RIP和OSPF是自治网络系统AS里的选路措施。
AS里的选路措施被称作IGP（内部网关协议）
1个AS里只会有一种选路措施。
而跨自治系统的协议叫EGP（外部网关协议）
通常使用BGP协议
Border Gateway Protocol边界网关协议
A:
A:
路由中毒是指在路由信息在路由表中失效时，先将度量值变为无穷大的数，而不是马上从路由表中删掉这条路由信息。 然后再将中毒路由信息发布出去，当相邻的路由器收到该中毒路由就可以通过其度量值是16，说明该路由是无效的。
??因为RIP协议中的度量值其实就是跳数，而RIP协议的跳数最大是15，大于15的目的地被认为是不可达，所以当其度量值为16，就表示这是一个无效路由，这就是所谓的路由中毒，这个数字在限制了网络大小的同时也防止了一个叫做“记数到无穷大”的问题。
A:
收到中毒路由信息的相邻的路由器会发送一个毒性逆转的信息，表示已经收到中毒路由信息。
??那么为什么收到中毒路由的路由器为什么要回复一个毒性逆转的信息？这是因为如果不回复的话，那么发送中毒路由的路由器就会一直以广播的形式发送中毒路由，直到相邻的路由器收到并回复一个毒性逆转的信息。
UDP的时候会用到多播
internet group message protol， 网络组管理协议
负责收集和解释一个网络中的组成员信息
IGMP协议应用于路由器
多播开放最短通路优先（Multicast Open Shortest PathFirst，MOSPF）协议是OSPF协议的扩展
使用多播链路状态路由选择来创建源点基准树。
这个协议需要一个新的链路状态更新分组，把主机的单播地址和组地址或主机负责的地址联系起来，这个分组就称为组成员关系LSA。
此外，这个数可以保存在高速缓存中，以便以后有同样源点/组地址对的分组可以使用它。
多播的其他更详细概念见链接
需要建立专用通道
当专用A试图向专用B通信时，会先加密，再通过加密隧道发到对方内网，具体报文内容不会和互联网直接接触。
内外网转换用的一个东西， 公网ip和内网ip互转。
ip从子网A变道子网B。
在本网时，按TCP通信
要漫游到外网时， 注册一个转交地址
本地代理接收地址，开启隧道
数据发送到外网
在外网时，使用代理ip发送数据
回到本地时，会注册并转交之前的地址
[toc]
limit 1 offset 1 不存在却要求返回null时， 可以用子查询，或者IFNULL(临时表结果或字段， NULL)
子查询是select结果作为字段，例如 select (select xx) 而不是 select xxx from (select xxx)。 当select中的字段结果不存在，会自动返回NULL
如果排名问题要去重，记得加 distinct
CREATE FUNCTION中
可以set N:=N-1: 进行变量更新。 不能在return中进行更新
1 | CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT |
要做排名时给出序号时，有两种方式
简单方式：
利用子查询字段，注意子查询字段的特点等同于摘出一个字段，再做一次额外查询，得到唯一的一个结果。
1 | # Write your MySQL query statement below |
但效率太慢。
高速的序号方法：
使用dense_rank() over(order by xxx) 可以得到序号，1 1 2 3 3 4，不会跳序号
其他序号方式：
row_number() over(order by xxx) 就是简单的12345这种，不考虑重复
rank() over(order by xxx) 如果重复了，1 1 3 4 4 6
1 | select score, |
寻找3个连续出现的数字，如果id是连续的，则可以自联结，即自己和自己join， 构造where a.id = b.id-1 and b.id = c.id-1 这样的情况。非常好理解
1 | select distinct a.num as ConsecutiveNums from |
善用自join联结解决一些表内成员互相比较的复杂问题。
1 | # 查询收入超过他经理的员工名字。 |
group分组后， 可以用having进行组内聚合情况的过滤， 剔除不想要的组
1 | # 查找 Person 表中所有重复的电子邮箱。 |
表a在 表b中不存在记录， 用left join + where xxx is null 来处理
1 | select c.name as Customers |
in 的用法 where a in(1,2,3,4)
或者 where a in (select aaa from xxx)
in也支持二元组形式
where (a,b) in (select aaa,bbb from xxx)
每组最大值的人选的情况，可以用join + in（分组结果）的方法
1 | # 查找每个部门中薪资最高的员工，先join，再用in获取符合组+最大值的行 |
找某薪水是组内前几位的情况， 擅用自查询， 即join后， 拿某条记录在where中遍历一遍, 然后根据count(distinct xxx)来确认自己的排名
1 | # 找出每个部门获得前三高工资的所有员工 |
1 | # 写一段 SQL 语句查出?"2013-10-01"?至?"2013-10-03"?期间非禁止用户（乘客和司机都必须未被禁止）的取消率。非禁止用户即 banned 为 No 的用户，禁止用户即 banned 为 Yes 的用户。 |
求3个或3个以上连续id的记录，直接自联结，然后用3个or条件判断
t1.id t2.id t3.id
t2.id t1.id t3.id
t2.id t3.id t1.id
然后取每种连接表的t1即可
注意distinct 可以用于星号
distinct s1.*
也可用于多列 distict s1.a,s1.b,s1.completed
1 | # 找出每行的人数大于或等于 100 且 id 连续的三行或更多行记录。 |
[toc]
SHOW DATABASE;
SHOW TABLES ;
SHOW COLUMNS FORM 表名
SHOW STATUS 显示广泛的服务器状态
SHOW CREATE DATABASE/TABLE 显示创建库或表的SQL语句是啥
SHOW GRANTS 显示授权用户
SHOW ERRORS SHOW WARNINGS 显示服务器错误或警告消息
SELECT prod_name
FROM products
SELECT id,name,price
FROM products
SELECT *
FROM products
SELECT DISTINCT id
FROM products
SELECT name
FROM products
LIMIT begin,len //即开始行，和行数
注意： 行从0开始， 故LIMIT1，返回的是第二行
SELECT name,age
FROM products
ORDER BY age
找出年龄最小的？ 加个LIMIT 1即可
先按price排，再按name排
SELECT id,price,name
FROM products
ORDER BY price, name
按price降序排，再按name升序排
SELECT id,price,name
FROM products
ORDER BY price DEC, name
SELECT name, price
FROM products
WHERE price = 2
注意： ORDER BY 排序语句应该放在WHERE的后面
SQL做where字符匹配时，不区分大小写。
SELECT id,name
FROM products
WHERE id <> 1003; //或者 id != 1003
SELECT name,price
FROM products
WHERE price BETWEEN 5 AND 10
WHERE price IS NULL
WHERE id=1003 AND price <10 AND age < 18
WHERE id=1002 OR id=1003 AND price>10
根据SQL的规则， AND优先于OR，变成了
WHERE id=1002 OR （id=1003 AND price>10）
所以最好在OR和AND组合时，加上括号
WHERE （id=1002 OR id=1003） AND price>10
WHERE id IN (1002,1003,1004)
WHERE id NOT IN (1002,1003,1004)
百分号通配符，查找以jet开头的任何名字
WHERE name LIKE ‘jet%’
包含有anvil的名字
WHERE name LIKE ‘%anvil%’
查找以s起头，e结尾的所有名字
WHERE name LIKE ‘s%e’
不能匹配0个字符，即该处必须有1个字符
WHERE name LIKE ‘_ton anvil’
1.不要过度使用通配符
2.不要把通配符用在搜索模式的开始处
3.注意通配符的位置
LIKE匹配的是整个串，REGEXP只要出现了类似的即可，即有子串即可
例如LIKE ‘abc’ ，只能返回abc。
REGEXP ‘abc’， 则可以返回 abcd
.可以匹配任意一个字符
WHERE name REGEXP ‘.000’
搜索2个串, |类似于或OR
WHERE name REGEXP ‘1000|2000’
注意： ‘1|2|3 Ton’ 指代的是1或2或3 Ton， 故不要连续用|后又跟字符，而应该用[]
匹配几个字符中的一个即可
WHERE name REGEXP ‘[123] TON’
则可返回 1 Ton 和 2 Ton
匹配1-9加a-z
WHERE name REGEXP ‘[1-9] [a-z]’
匹配 正则符号模样的特殊字符
用\作为前导
WHERE name REGEXP ‘\.’
则找到匹配.的， 此时.不代表任意字符
匹配某个字符的0个或1个
WHERE name REGEXP ‘sticks?’
则可匹配stick或者sticks
指定匹配数目 {n}
不少于指定数目的匹配 {n,}
匹配n到m数目的匹配 {n,m}
WHERE name REGEXP ‘[[:digit:]]{4}’
则匹配4个任意数字
^定位为文本的开始，$定位为文本的结束
注意： ^有另外一个用途，可以用来否定集合[]
在SQL中测试自己写的正则表达式对不对
SELECT ‘hello’ REGEXP ‘abc’
若正确，则返回1，否则返回0。 显然这个例子返回0
计算字段
SELECT Concat(name, ‘(’ , country, ‘)’ )
则返回的行里的每个值为
LSX(CHINA)
CRISTINA(USA)
RTrim(name)可以删除name中多余的右边空格，常可以用在拼接中
给计算字段取别名
SELECT Concat(name, ‘(’ , country, ‘)’ ) AS newtitle
则列名叫newtitle
执行算数计算
SELECT id, num, price, num*price AS sumProfit
则多返回一个列，叫做总利润
测试拼接字段
SELECT 3*2+5, 则返回11
SELECT Now(), 则返回数据库的当前时间
数据处理函数
Select name, Upper(name) AS upcase_name 都转为大写
SELECT AVG(price) AS avg_price
FROM products
WHERE id = 1003
SELECT COUNT（*） AS num_cust
计算num的数量，不包括NULL
SELECT COUTN（num） AS num_cust
还有MAX,MIN,SUM
SELECT AVG（DISTINCT price） AS avg_price
SELECT id, COUNT(*) AS id_num
FROM products
GROUP BY id
1.除了聚集计算语句外， SELECT中出现的每个列都必须出现在GROUP BY中
2.GROUP BY 必须出在 ORDER BY 之前
SELECT id， COUNT() AD orders
FROM orders
GROUP BY id
HAVING COUNT() >= 2
SELECT id, COUNT() AS num
FROM products
WHERE price >= 10
GROUP BY id
HAVING COUNT() >=2
顺序：先WHERE过滤， 在COUNT过滤
语句使用顺序
SELECT
FROM
WHERE
GROUP BY
HAVING
ORDER BY
LIMIT
SELECT cus_id
FROM orders
WHERE sail_id IN （SELECT sail_id
FROM orderitem
WHERE prod_id = ‘TNT2’）
即先从产品表中，找到产品id为INT2的所有订单
再从订单表中，找到订单id匹配的所有客户。
检索出上述客户id的所有信息
SELECT cus_name, cus_age
FROM customer
WHERE cus_id IN (SELECT cus_id
FROM orders
WHERE sail_id IN （SELECT sail_id
FROM orderitem
WHERE prod_id = ‘TNT2’））
显示每个客户的订单总数
SELECT name, state, (SELECT COUNT(*)
FROM orders
WHERE orders.cus_id = cus.cus_id ) AS orders
FROM customers
ORDER BY name
对于customer中的每一个客户id， 都从订单表中进行检索，找出每个id的订单数量。
CREATE TABLE 表名
（
列名 数据类型 列属性
……
PRIMARY KEY (主键列1，主键列2……)
）ENGINE=InnoDB
ALTER TABLE 表名
ADD 列名 数据类型
ALTER TABLE 表名
DROP COLUMN 列名
DROP TABLE 表名
RENAME TABLE 旧表名 TO 新表名
INSERT INTO 表名(
列名1
列名2
……
)
VALUES（
数据1
数据2
……
），
（
数据3
数据4
）;
这样就插入了2行
更新数据：
UPDATE 表名
SET 列名1=数据1
列名2=数据2
WHERE 查询条件
DELETE FROM 表名
WHERE 查询条件
alert table table_test drop primary key;
alert table table_test add primary key(id);
[toc]
看答案也没看懂，主要是没有深入研究规律，没精力了，先放着
剑指 Offer II 013. 二维子矩阵的和 - 力扣（LeetCode）
做过好几次了， 维护一个dp[y][x]， 表示（y，x）到(0,0)的矩形和，这个和可以提前遍历一次得到
然后再通过加减矩阵的方式得到结果
1 | class NumMatrix { |
606. 根据二叉树创建字符串 - 力扣（LeetCode）
1 | /** |