notes

Varint 中的每个 byte 的最高位 bit 有特殊的含义，如果该位为 1，表示后续的 byte 也是该数字的一部分，如果该位为 0，则结束。其他的 7 个 bit 都用来表示数字。

三次握手的过程中，当用户首次访问server时，发送syn包，server根据用户IP生成cookie，并与syn+ack一同发回client；client再次访问server时，在syn包携带TCP cookie；如果server校验合法，则在用户回复ack前就可以直接发送数据；否则按照正常三次握手进行。

无栈协成，不切换栈寄存器只切换this，生命周期取决于对象的生命周期。用类成员变量，传递参数。

一致性（Consistency） （所有节点访问同一份最新的数据副本）
可用性（Availability）（每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）
分区容错性（Partition tolerance）（如果不能在时限内达成数据一致性，则发生分区，必须就当前操作在 C 和 A 之间做出选择。）

KMP PMT 前缀 后缀 相同最长的个数就是要回退的位置

Skip Lists 

randomLevel():
    level = 1
    # random()返回一个[0..1)之间的随机数
    while random() < p and level < MAX_LEVEL do:
        level := leve + 1
    return level

（ 1 ）慢开始、拥塞避免（ 2 ）快重传、快恢复

控制拥塞窗口大小，没有丢包就增加，丢包就减小。


基于丢包的拥塞控制：将丢包视为出现拥塞，采取缓慢探测的方式，逐渐增大拥塞窗口，当出现丢包时，将拥塞窗口减小，如 Reno、Cubic 等。

基于时延的拥塞控制：将时延增加视为出现拥塞，延时增加时减小拥塞窗口，延时减小时增大拥塞窗口，如 Vegas、FastTCP 等。

基于链路容量的拥塞控制：实时测量网络带宽和时延，认为网络上报文总量大于带宽时延乘积时出现了拥塞，如 BBR。

基于学习的拥塞控制：没有特定的拥塞信号，而是借助评价函数，基于训练数据，使用机器学习的方法形成一个控制策略，如 Remy。

拥塞控制算法的核心是选择一个有效的策略来控制拥塞窗口的变化，下面介绍几种经典的拥塞控制算法。

Reno

Reno[2] 将拥塞控制的过程分为四个阶段：慢启动、拥塞避免、快重传和快恢复，是现有的众多拥塞控制算法的基础，下面详细说明这几个阶段。

慢启动阶段，在没有出现丢包时每收到一个 ACK 就将拥塞窗口大小加一（单位是 MSS，最大单个报文段长度），每轮次发送窗口增加一倍，呈指数增长，若出现丢包，则将拥塞窗口减半，进入拥塞避免阶段；当窗口达到慢启动阈值或出现丢包时，进入拥塞避免阶段，窗口每轮次加一，呈线性增长；当收到对一个报文的三个重复的 ACK 时，认为这个报文的下一个报文丢失了，进入快重传阶段，立即重传丢失的报文，而不是等待超时重传；快重传完成后进入快恢复阶段，将慢启动阈值修改为当前拥塞窗口值的一半，同时拥塞窗口值等于慢启动阈值，然后进入拥塞避免阶段，重复上诉过程。Reno 拥塞控制过程如图 1 所示

每一次通信前都进行一次同步。即A记录好自己的变更后，先告诉B，C，D，E: “我要给大家同步一个变更，序列号是a, 我的上一次变更记录，是由V发起的（V可能是任何一个节点），序列号是a-1；我的最新一条可以落实的记录（可能已经落实了），序列号是b”。B，C，D，E收到后检查自己的上一次变更，发起人和序列号是否和A相同。相同的就把变更记录下来，并给A回复OK。A收到2个人的OK回复后就给告诉告诉B，C，D，E:“刚才那个变更同步请求（发起者A，序列号a）已经得到了过半通过，大家可以把记录的变更落实啦；刚才没有收到请求的同学，请联系我重发请求而且收到后就可以落实了；发现上一次变更记录和我不吻合的同学，请删除和我不吻合的上一次记录，并联系我对齐一下我们从哪个时候开始不一致的，删除你前面所有和我不一致的记录，并补齐你可能中间缺失的记录“。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None



class Solution:
    def preorderTraversal(self, root):
        if root is None: return []
        return [] if root is None else [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

result, stack = [], [root]    
while stack:
    cur_node = stack.pop() # 访问根节点，直接进行操作(输出到数组)
    result.append(cur_node.val)
    stack.append(cur_node.right)
    stack.append(cur_node.left)
return result



class Solution:
    def inorderTraversal(self, root):
        if root is None: return []
        return [] if root is None else self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

while p_node or stack:
    while p_node: # 把所有当前访问节点的左孩子都入栈
        stack.append(p_node)
        p_node = p_node.left
    cur_node = stack.pop() # 操作栈顶节点，如果是第一次运行到这步，那么这是整棵树的最左节点
    result.append(cur_node.val) # 因为已经保证没有左节点，可以访问根节点
    if cur_node.right:
        p_node = cur_node.right # 将指针指向当前节点的右节点
return result



class Solution:
    def postorderTraversal(self, root):
        if root is None: return []
        return [] if root is None else self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

result, stack = [], [root]
while stack:
    cur_node = stack.pop()
    result.append(cur_node.val)
    stack.append(cur_node.left)
    stack.append(cur_node.right)
return result[::-1] # 反序操作


while queue:
    level_len = len(queue) # 记录现在队列中的节点数量
    level_nodes = [] # 每层输出
    while level_len > 0: # 具体出队入队操作，保证本层所有节点的子节点都入队
        cur_node = queue.popleft()
        level_nodes.append(cur_node.val)
        queue.append(cur_node.left)
        queue.append(cur_node.right)
        level_len -= 1
    result.append(level_nodes)
return result


class Solution:
    def invertTree(self, root):
        if root is None: return []
        root.left, root.right = root.right, root.left
        self.invertTree(root.right) # 下面两句的顺序并不重要
        self.invertTree(root.left)
        return root

while stack:
    cur_node = stack.pop()
    cur_node.left, cur_node.right = cur_node.right, cur_node.left
    stack.append(cur_node.left)
    stack.append(cur_node.right)
return root



def qsort1(alist):
    print(alist)
    if len(alist) <= 1:
        return alist
    else:
        pivot = alist[0]
        return qsort1([x for x in alist[1:] if x < pivot]) + \
               [pivot] + \
               qsort1([x for x in alist[1:] if x >= pivot])

unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
print(qsort1(unsortedArray))