概览LeetCode Hot
2.11 有效的括号2.12 合并两个有序链表2.13 括号生成2.14 合并K个升序链表2.15 下一个排列 计算机网络
TCP三次握手TCP四次挥手TCP流量控制TCP拥塞控制HTTPS 总结
概览LeetCode Hot：有效的括号、合并两个有序链表、括号生成、合并K个升序链表、下一个排列
计算机网络：TCP三次握手、TCP四次挥手、TCP流量控制、TCP拥塞控制、HTTPS
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1： 输入：s = "()" 输出：true
//辅助栈
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map pairs = new HashMap() {{
put(')', '('); //注意键值
put(']', '[');
put('}', '{');
}};
Deque stack = new linkedList();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) { //左括号入栈，右括号与栈顶元素比较
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
2.12 合并两个有序链表
同剑指offer23题一样
2.13 括号生成数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1： 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
//看做隐式树，DFS+剪枝
public class Solution {
// 做加法
public List generateParenthesis(int n) {
List res = new ArrayList<>();
if (n == 0) {
return res;
}
dfs("", 0, 0, n, res);
return res;
}
private void dfs(String curStr, int left, int right, int n, List res) {
if (left == n && right == n) {
res.add(curStr);
return;
}
// 剪枝
if (left < right) {
return;
}
if (left < n) {
dfs(curStr + "(", left + 1, right, n, res);
}
if (right < n) {
dfs(curStr + ")", left, right + 1, n, res);
}
}
}
2.14 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
//优先级队列
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue queue = new PriorityQueue<>(lists.length, new Comparator() {
@Override
public int compare(ListNode o1, ListNode o2) {
if (o1.val < o2.val) return -1;
else if (o1.val == o2.val) return 0;
else return 1;
}
});
ListNode dummy = new ListNode(0);
ListNode p = dummy;
for (ListNode node : lists) {
if (node != null) queue.add(node);
}
while (!queue.isEmpty()) {
p.next = queue.poll();
p = p.next;
if (p.next != null) queue.add(p.next);
}
return dummy.next;
}
}
//也可以使用分治的思想，两两合并链表
2.15 下一个排列
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1： 输入：nums = [1,2,3] 输出：[1,3,2]
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
for (int i = len - 1; i > 0; i--) {
//从后往前先找出第一个相邻的后一个大于前一个情况，此时的i-1位置就是需要交换的位置
if (nums[i] > nums[i - 1]) {
//对i自己和之后的元素排序，[i,len)从小到大，第一个大于i-1位置的进行交换，那么就是下一个排列
Arrays.sort(nums, i, len);
for (int j = i; j nums[i - 1]) {
int temp = nums[j];
nums[j] = nums[i - 1];
nums[i - 1] = temp;
return;
}
}
}
}
Arrays.sort(nums);//都没有找到，则数组是按降序排序的，返回升序排序
return;
}
}
计算机网络
TCP三次握手
为什么要三次握手？
为了防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误。 （网络中存在延迟的重复分组）
client发出的第一个连接请求报文段并没有丢失，而是在某个网络结点长时间的滞留了，以致延误到连接释放以后的某个时间才到达server。本来这是一个早已失效的报文段。但server收到此失效的连接请求报文段后，就误认为是client再次发出的一个新的连接请求。于是就向client发出确认报文段，同意建立连接。
TCP四次挥手为什么要四次分手？
可以看作客户端和服务端的两次挥手，也就是客户端和服务端分别释放连接的过程。
TCP协议是一种面向连接的、可靠的、基于字节流的运输层通信协议。TCP是全双工模式，这就意味着，当主机1发出FIN报文段时，只是表示主机1已经没有数据要发送了，主机1告诉主机2，它的数据已经全部发送完毕了；但是，这个时候主机1还是可以接受来自主机2的数据；当主机2返回ACK报文段时，表示它已经知道主机1没有数据发送了，但是主机2还是可以发送数据到主机1的；当主机2也发送了FIN 报文段时，这个时候就表示主机2也没有数据要发送了，就会告诉主机1，我也没有数据要发送了，之后彼此就会愉快的中断这次TCP连接。
MSL：报文段最大生存时间，它是任何报文段被丢弃前在网络内的最长时间。
原因：
保证TCP协议的全双工连接能够可靠关闭
保证这次连接的重复数据段从网络中消失
第一点：如果主机1直接CLOSED了，那么由于IP协议的不可靠性或者是其它网络原因，导致主机2没有收到主机1最后回复的ACK。那么主机2就会在超时之后继续发送FIN，此时由于主机1已经CLOSED了，就找不到与重发的FIN对应的连接。所以，主机1不是直接进入CLOSED，而是要保持TIME_WAIT状态。当再次收到FIN的时候，能够保证对方收到ACK，最后正确的关闭连接。
第二点：如果主机1直接CLOSED，然后又再向主机2发起一个新连接，我们不能保证这个新连接与刚关闭的连接的端口号是不同的。也就是说有可能新连接和老连接的端口号是相同的。一般来说不会发生什么问题，但是还是有特殊情况出现：假设新连接和已经关闭的老连接端口号是一样的，如果前一次连接的某些数据仍然滞留在网络中（称为Lost Duplicate），这些延迟数据在建立新连接之后才到达主机2， 由于新连接和老连接的端口号是一样的，TCP协议就认为那个延迟的数据是属于新连接的，这样就和真正的新连接的数据包发生混淆了。所以TCP连接要在TIME_WAIT状态等待2倍MSL，保证本次连接的所有数据都从网络中消失。
TCP流量控制滑动窗口机制
TCP滑动窗口技术通过动态改变窗口大小来调节两台主机间数据传输。每个TCP/IP主机支持全双工数据传输，因此每个TCP主机有两个滑动窗口一个用于接收数据，另一个用于发送数据。TCP使用肯定确认技术，其确认号指的是下一个所期待的字节。 假定发送方设备以每一次三个数据包的方式发送数据，也就是说，窗口大小为3。发送方发送序列号为1、2、3的三个数据包，接收方设备成功接收数据包，用序列号4确认。发送方设备收到确认，继续以窗口大小3发送数据。当接收方设备要求降低或者增大网络流量时，可以对窗口大小进行减小或者增加，本例降低窗口大小为2，每一次发送两个数据包。当接收方设备要求窗口大小为0，表明接收方已经接收了全部数据，或者接收方应用程序没有时间读取数据，要求暂停发送。发送方接收到携带窗口号为0的确认，停止这一方向的数据传输。
TCP拥塞控制慢开始算法：
在刚刚开始发送报文段时，先把拥塞窗口 cwnd 设置为一个最大报文段 MSS（Maximum Segment Size，最大报文长度）的数值。而在每收到一个对新的报文段的确认后，把拥塞窗口增加至多一个MSS的数值（底数为2的指数增长规律）。
慢开始的“慢”并不是指cwnd的增长速率慢，而是指在TCP开始发送报文段时先设置cwnd=1，使得发送方在开始时只发送一个报文段（目的是试探一下网络的拥塞情况），然后再逐渐增大cwnd。
为了防止拥塞窗口cwnd增长过大引起网络拥塞，还需要设置一个慢开始门限ssthresh状态变量。
拥塞避免 :
让拥塞窗口cwnd缓慢地增大，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。
无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有收到确认），就要把慢开始门限ssthresh设置为出现拥塞时的发送 方窗口值的一半（但不能小于2）。然后把拥塞窗口cwnd重新设置为1，执行慢开始算法。
快重传:
快重传算法首先要求接收方每收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方）而不要等到自己发送数据时才进行捎带确认。
快重传算法规定，发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段。
快恢复：
当发送方连续收到三个重复确认，就执行“乘法减小”算法，把慢开始门限ssthresh减半。
与慢开始不同之处是现在不执行慢开始算法（即拥塞窗口cwnd现在不设置为1），而是把cwnd值设置为慢开始门限ssthresh减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大。
HTTPSSSL/TSL原理
SSL/TLS协议的基本思路是采用公钥加密算法，也就是说，客户端先向服务器端索要公钥，然后用公钥加密信息，服务器收到密文后，用自己的私钥解密。
但是，这里有两个问题。
（1）如何保证公钥不被篡改？
解决方法：将公钥放在数字证书中。只要证书是可信的，公钥就是可信的。
（2）公钥加密计算量太大，如何减少耗用的时间？
解决方法：每一次对话（session），客户端和服务器端都生成一个"对话密钥"（session key），用它来加密信息。由于"对话密钥"是对称加密，所以运算速度非常快，而服务器公钥只用于加密"对话密钥"本身，这样就减少了加密运算的消耗时间。
因此，SSL/TLS协议的基本过程是这样的：
（1） 客户端向服务器端索要并验证公钥。
（2） 双方协商生成"对话密钥"。
（3） 双方采用"对话密钥"进行加密通信。
HTTPS简介
HTTPS其实是有两部分组成：HTTP + SSL / TLS，也就是在HTTP上又加了一层处理加密信息的模块。服务端和客户端的信息传输都会通过TLS进行加密，所以传输的数据都是加密后的数据。
1. 客户端发起HTTPS请求
这个没什么好说的，就是用户在浏览器里输入一个https网址，然后连接到server的443端口。
2. 服务端的配置
采用HTTPS协议的服务器必须要有一套数字证书，可以自己制作，也可以向组织申请。区别就是自己颁发的证书需要客户端验证通过，才可以继续访问，而使用受信任的公司申请的证书则不会弹出提示页。这套证书其实就是一对公钥和私钥。
3. 传送证书
这个证书其实就是公钥，只是包含了很多信息，如证书的颁发机构，过期时间等等。
4. 客户端解析证书
这部分工作是有客户端的TLS来完成的，首先会验证公钥是否有效，比如颁发机构，过期时间等等，如果发现异常，则会弹出一个警告框，提示证书存在问题。如果证书没有问题，那么就生成一个随即值。然后用证书对该随机值进行加密。
5. 传送加密信息
这部分传送的是用证书加密后的随机值，目的就是让服务端得到这个随机值，以后客户端和服务端的通信就可以通过这个随机值来进行加密解密了。
6. 服务段加密信息
服务端用私钥解密后，得到了客户端传过来的随机值(私钥)，然后把内容通过该值进行对称加密。
7. 传输加密后的信息
这部分信息是服务段用私钥加密后的信息，可以在客户端被还原
8. 客户端解密信息
客户端用之前生成的私钥解密服务段传过来的信息，于是获取了解密后的内容。整个过程第三方即使监听到了数据，也束手无策。
总结1.计算机网络因为是本专业专业课程，学得都还不错，只列举了重点和面试常问的知识，同样后面查漏补缺。
