1、中文和英文之间，中文和数字之间用空格。
2、标点符号用中文的标点符号，比如逗号：，句号：。
3、贴代码要高亮，符合 Markdown 的语法规范。

传送门：leecode-225 用队列实现栈。

思路：

• 定义两个队列，queue 和 help
• 压栈：只要有新数据，就放入 queue 队列
• 出栈：
  • 如果 queue 队列为空，返回 -1
  • 如果 queue 队列元素数量 >1，将 queue 队列中数据除了队尾元素，其它全部放入 help 队列
  • 将 queue 队列剩下的最后一个元素（原队尾元素）出队并返回，交换 queue 队列和 help 队列的指向

实现：

<?php

class MyStack
{
    private $queue;
    private $help;

    function __construct()
    {
        $this->queue = new SplQueue();
        $this->help = new SplQueue();
    }

    /**
    * Push element x onto stack.
    * @param Integer $x
    * @return NULL
    */
    function push($x)
    {
        $this->queue->enqueue($x);
    }

    /**
    * Removes the element on top of the stack and returns that element.
    * @return Integer
    */
    function pop()
    {
        if ($this->queue->isEmpty()) {
            return -1;
        }

        if ($this->queue->count() === 1) {
            return $this->queue->dequeue();
        }

        // queue 队列除了队尾，都移入 help
        while ($this->queue->count() > 1) {
            $this->help->enqueue($this->queue->dequeue());
        }

        $res = $this->queue->dequeue();

        // 交换 queue 和 help
        $this->swap();

        return $res;
    }

    function swap()
    {
        $tmp = $this->queue;
        $this->queue = $this->help;
        $this->help = $tmp;
    }

    /**
    * Get the top element.
    * @return Integer
    */
    function top()
    {
        if ($this->queue->isEmpty()) {
            return -1;
        }

        if ($this->queue->count() === 1) {
            $res = $this->queue->dequeue();
            $this->queue->enqueue($res);
            return $res;
        }

        while ($this->queue->count() > 1) {
            $this->help->enqueue($this->queue->dequeue());
        }

        $res = $this->queue->dequeue();

        $this->help->enqueue($res);

        $this->swap();

        return $res;
    }

    /**
    * Returns whether the stack is empty.
    * @return Boolean
    */
    function empty()
    {
        return $this->queue->isEmpty();
    }
}

传送门：leecode - 145 二叉树的后序遍历。

递归法：

class Solution
{
    private $list = [];

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root)
    {
        if ($root === null) return [];
        $this->postorderTraversal($root->left);
        $this->postorderTraversal($root->right);
        $this->list[] = $root->val;
        return $this->list;
    }
}

迭代法：

前序遍历的顺序是根->左->右，将其转换为根->右->左，由于栈是先进后出的顺序，所以入栈时先将左子树入栈，最后将结果倒序。

class Solution
{
    private $stack = [];
    private $list = [];

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function postorderTraversal($root)
    {
        if ($root === null) return [];

        array_push($this->stack, $root);

        while (!empty($this->stack)) {
            $node = array_pop($this->stack);
            $this->list[] = $node->val;
            if ($node->left !== null) {
                array_push($this->stack, $node->left);
            }
            if ($node->right !== null) {
                array_push($this->stack, $node->right);
            }
        }

        return array_reverse($this->list);
    }
}

力扣传送门：leecode-912 排序数组。

1、**

归并排序使用的就是分治**。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

实现思路为：递归划分为左右两半部分，然后使用双指针思路对左右两半部分合并排序。

归并排序的递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))。
归并排序的终止条件：p >= r 不用再继续分解。

解释一下这个递推公式：

merge_sort(p…r) 表示，给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题，merge_sort(p…q) 和 merge_sort(q+1…r)，其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从 p 到 r 之间的数据就也排好序了。

2、实现

<?php

class MergeSort
{
    /**
     * 归并排序
     *
     * @param $arr
     * @param $left
     * @param $right
     */
    public static function sort(&$arr, $left, $right)
    {
        if ($left >= $right) {
            return;
        }

        $mid = intval(floor(($left + $right) / 2));
        // 递归前面的
        self::sort($arr, $left, $mid);
        // 递归后面的
        self::sort($arr, $mid + 1, $right);
        // 归并
        self::merge($arr, $left, $mid, $right);
    }

    /**
     * 归并
     *
     * @param $arr
     * @param $left
     * @param $mid
     * @param $right
     */
    public static function merge(&$arr, $left, $mid, $right)
    {
        $p1 = $left;
        $p2 = $mid + 1;

        // 创建一个临时数组，用于存放归并之后的结果
        $help = [];

        while ($p1 <= $mid && $p2 <= $right) {
            $help[] = $arr[$p1] <= $arr[$p2] ? $arr[$p1++] : $arr[$p2++];
        }

        // 将剩余的数组直接放入临时数组
        while ($p1 <= $mid) {
            $help[] = $arr[$p1++];
        }
        while ($p2 <= $right) {
            $help[] = $arr[$p2++];
        }

        // 把临时数组存入原数组
        for ($i = 0; $i < count($help); $i++) {
            $arr[$left + $i] = $help[$i];
        }
    }
}

// Test
$arr = [6, 4, 3, 7, 5, 1, 2];
MergeSort::sort($arr, 0, count($arr) - 1);
print_r($arr);

3、复杂度分析

时间复杂度：归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
空间复杂度：归并排序每次递归需要用到一个辅助表，长度与待排序的表相等，虽然递归次数是 O(logn) ，但每次递归都会释放掉所占的辅助空间，因而空间复杂度还是 O(n)。

4、稳定性分析

合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

5、它是原地排序算法吗？

归并排序是非原地排序算法，主要原因是合并函数无法在原地执行。

传送门：leetcode - 104 二叉树的最大深度。

思路 1：DFS（深度优先遍历）。

max(头结点左⼦树的最⼤深度, 头结点右⼦树的最⼤深度) + 1

实现：

/**
 * @param TreeNode $root
 * @return Integer
 */
function maxDepth($root)
{
    if ($root === null) {
       return 0;
    }

    $maxLeftHigh = $this->maxDepth($root->left);
    $maxRightHigh = $this->maxDepth($root->right);

    return max($maxLeftHigh, $maxRightHigh) + 1;
}

思路 2：BFS（广度优先遍历）。

/**
 * @param TreeNode $root
 * @return Integer
 */
function maxDepth($root)
{
    if (is_null($root)) {
        return 0;
    }

    // 广度优先搜索的队列里存放的是「当前层的所有节点」
    $queue = [];
    array_push($queue, $root);

    // 二叉树深度
    $res = 0;

    while (!empty($queue)) {
        // 这一层有多少个节点
        $len = count($queue);

        // 拿出各个节点，并把左右子节点入队
        while ($len > 0) {
            $node = array_shift($queue);

            if (!is_null($node->left)) {
                array_push($queue, $node->left);
            }
            if (!is_null($node->right)) {
                array_push($queue, $node->right);
            }

            $len--;
        }

        // 当前层所有节点已经出列，如果队列不为空，说明有下一层节点，深度 + 1
        $res++;
    }

    return $res;
}

传送门：leetcode-21 合并两个有序链表。

题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：

• 创建 dummy 空节点与指针 curr
• 通过两个链表的节点 val 大小对比，更新空链表指针 curr 值
• 最后 return 到 dummy.next，即头节点可得整个链表

代码实现：

<?php

class ListNode
{
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null)
    {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution
{
    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function mergeTwoLists($l1, $l2) {
        // 创建 dummy 空节点和 curr 指针
        $dummy = new ListNode();
        $curr = $dummy;

        while ($l1 !== null && $l2 !== null) {
            if ($l1->val <= $l2->val) {
                $curr->next = $l1;
                $l1 = $l1->next;
            } else {
                $curr->next = $l2;
                $l2 = $l2->next;
            }
            $curr = $curr->next;
        }

        if ($l1 !== null) {
            $curr->next = $l1;
        }
        if ($l2 !== null) {
            $curr->next = $l2;
        }

        return $dummy->next;
    }
}

传送门：剑指 Offer 22-链表中倒数第 k 个节点。

思路：

双指针：

1. slow 和 fast 俩指针都从头结点 head 开始
2. for 循环中 fast 先走 k 步
3. while 循环中 fast 和 slow 均一次走一步，直到 fast 走到链表末尾
4. 返回 slow

实现：

<?php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution
{
    /**
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function getKthFromEnd($head, $k)
    {
        $fast = $head;
        $slow = $head;

        for ($i = 0; $i < $k; $i++) {
            $fast = $fast->next;
        }

        while ($fast !== null) {
            $fast = $fast->next;
            $slow = $slow->next;
        }

        return $slow;
    }
}

操作系统八股文：互联网面试相关知识点学习笔记 。

1、说一下网络模型都有哪些？什么是 I/O 多路复用？select 和 epoll 的区别？水平触发和边缘触发的区别是啥？使用的时候需要注意什么？epoll 储存描述符的数据结构是什么？select 有描述符限制吗？是多少？

• Linux下一共有几种 IO 模型？（5 种）分别是？（阻塞 I/O、非阻塞 I/O、I/O 复用、信号驱动 I/O、异步 I/O）
• 什么是同步阻塞 I/O？（应用程序通过 IO 函数向内核发起系统调用，导致应用程序阻塞，等待内核数据准备好，内核数据准备好后，从内核拷贝到用户空间，IO 函数返回成功指示，这整个过程应用进程都是阻塞的。）同步阻塞 IO 的两种方式，各有什么特点？（单线程和多线程。单线程：服务端会阻塞在第一个客户端的 recv()，无法进行第二个客户端的连接；多线程：解决了单线程的阻塞其他客户端的连接问题，但是每来一个客户端连接就要开辟一个线程，线程数太多导致消耗系统资源多，而且线程上下文切换也有开销）
• 什么是同步非阻塞 I/O？（非阻塞 I/O 是在应用调用 recv() 读取数据时，如果该缓冲区没有数据的话，就会直接返回一个 EWOULDBLOCK 错误，不会让应用一直等待中。在没有数据的时候会即刻返回错误标识，那也意味着如果应用要读取数据就需要不断的调用 recv() 请求，直到读取到它数据要的数据为止。）
• 同步非阻塞 I/O 存在的问题？（NIO 这个模型在客户端少的时候十分好用，但是客户端如果很多，比如有 1 万个客户端进行连接，那么每次循环就要遍历 1 万个 socket，如果一万个 socket 中只有 10 个 socket 有数据，也会遍历一万个 socket，就会做很多无用功。而且这个遍历过程是在用户态进行的，用户态判断 socket 是否有数据还是调用内核的 read() 方法实现的，这就涉及到用户态和内核态的切换，每遍历一个就要切换一次，开销很大。）
• IO 多路复用是什么？（一种同步 IO 模型，实现了一个线程可以监视多个文件句柄。多路是指多个网络连接，复用指的是使用同一个线程。 ）
• IO 多路复用有哪几种实现方式？（select、poll、epoll）
• select 的优点和缺点是什么？（优点：解决了 NIO 在用户态和内核态频繁切换的问题；缺点：1、单个进程监视 fd 数量有限，为 1024；2、需要将所有的 fd 集合从用户态拷贝到内核态，再将所有的 fd 集合从内核态拷贝到用户态，拷贝开销大；3、在用户态和内核态都需要对 fd 集合进行遍历，时间复杂度 O(N)）
• select 有描述符限制吗？是多少？（有，1024）
• poll 相对于 select 的优点是什么？（没有 fd 的限制）poll 的缺点是什么？（1、需要将所有的 fd 集合从用户态拷贝到内核态，再将所有的 fd 集合从内核态拷贝到用户态，拷贝开销大；2、在用户态和内核态都需要对 fd 集合进行遍历，时间复杂度 O(N)）
• epoll 是什么？（基于回调机制，从 select、poll 的全量遍历和拷贝 socket，时间复杂度 O(N)，优化为只拷贝真正就绪的 socket，无需遍历所有的 socket，时间复杂度 O(1)）
• epoll 储存描述符的数据结构是什么？（红黑树）
• 水平触发和边缘触发的区别是啥？（epoll_wait 是否会通知多次）使用的时候需要注意什么？（边缘触发只会通知一次，所以在 ET 模式下，read 一个 fd 的时候一定要把它的 buffer 读完，或者遇到 EAGAIN 错误。）
• 阻塞 IO、非阻塞 IO、多路复用 IO、信号驱动 IO 都属于同步 IO, 只有异步 IO 才是真正的异步 IO。

2、进程、线程、协程的区别？

一个进程可以由多个称为线程的执行单元组成。每个线程都运行在进程的上下文中，共享着同样的代码和全局数据。

虚拟内存是操作系统为每个进程提供的一种抽象，每个进程都有属于自己的、私有的、地址连续的虚拟内存，当然我们知道最终进程的数据及代码必然要放到物理内存上，那么必须有某种机制能记住虚拟地址空间中的某个数据被放到了哪个物理内存地址上，这就是所谓的地址空间映射，也就是虚拟内存地址与物理内存地址的映射关系，那么操作系统是如何记住这种映射关系的呢，答案就是页表，页表中记录了虚拟内存地址到物理内存地址的映射关系。有了页表就可以将虚拟地址转换为物理内存地址了，这种机制就是虚拟内存。

每个进程都有自己的虚拟地址空间，进程内的所有线程共享进程的虚拟地址空间。

进程切换与线程切换的一个最主要区别就在于进程切换涉及到虚拟地址空间的切换而线程切换则不会。因为每个进程都有自己的虚拟地址空间，而线程是共享所在进程的虚拟地址空间的，因此同一个进程中的线程进行线程切换时不涉及虚拟地址空间的转换。

多线程比多进程之间更容易共享数据，在上下文切换中线程一般比进程更高效。

协程（Coroutine）是用户态的线程。通常创建协程时，会从进程的堆中分配一段内存作为协程的栈。

协程本质上就是用户态下的线程，协程不是被操作系统内核所管理，而完全是由程序所控制，所以也有人说协程是 “轻线程”，但我们一定要区分用户态和内核态的区别，很关键。

协程适用于 IO 阻塞且需要大量并发的场景，当发生 IO 阻塞，由协程的调度器进行调度，通过将数据流 yield 掉，并且记录当前栈上的数据，阻塞完后立刻再通过线程恢复栈，并把阻塞的结果放到这个线程上去运行。

面试题：什么是协程，协程和线程的区别和联系？进程和线程的区别和联系？

进程是计算机资源（包括 CPU、内存、磁盘 IO 等）分配的最小单位，线程是程序执行（CPU 调度和分配）的最小单位。

进程有独立的地址空间，每启动一个进程，系统都会为进程分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种开销非常昂贵。线程没有地址空间，但是线程共享所属进程的地址空间。

同一进程中的多个线程共享所属进程的代码段（代码和常量）、数据段（全局变量和静态变量）、扩展段（堆存储），但是每个线程拥有自己的栈段（又叫运行时段，用于存放所有局部变量和临时变量）、寄存器的内容。

健壮性：因为不同进程有自己独立的地址空间，所以一个进程死掉，不会对其他进程造成影响。而一个线程死掉，线程所属的整个进程可能也会死掉，所以多进程方式比多线程方式更加健壮。

3、说一下内存管理，虚拟内存，分段分页？操作系统中，内存管理怎么做的？如何保证碎片都能被有效利用？

为什么需要虚拟内存？

早期计算机在运行时，直接把整个程序加载入内存。这会产生一些问题：

1. 如果程序很大或很多时，内存很快会被耗尽。
2. 进程间不独立，一个进程可能修改另一个进程数据，导致出错。

虚拟内存是什么？

于是就有了虚拟内存，它是一种内存管理技术，能为每个进程提供一个独有的、连续的虚拟地址空间。并通过内存交换技术，把不常用的内存换出到硬盘，需要时再换入内存，从而让有限的内存能运行更大的程序。

虚拟内存怎么用？

当有进程被创建时，操作系统会为其分配虚拟内存，并通过内存管理单元（MMU）的映射关系，将虚拟地址转化为物理地址。这主要有分段和分页两种方式。

分段

分段根据程序的逻辑角度，分成了栈、堆、数据、代码等不同属性的段。

地址转换分为以下三步：

1. 将虚拟地址划分成段号和偏移量。
2. 根据段号，从段表中，查询对应的段基地址。
3. 拿段基地址，加上偏移量，得到物理内存地址。

分段保留了逻辑特征，便于共享和保护，但每个段的大小不一，会产生内存碎片的问题。解决办法就是内存交换，先把不连续的段换出到硬盘，再换入内存，使之连续。但如果要交换的段很大，就会产生内存交换效率低的问题。

分页

简单分页

于是，就有了分页，把虚拟和物理内存分成固定大小的页。

地址转换分为以下三步：

1. 将虚拟地址划分成页号和偏移量。
2. 根据页号，从页表中，查询对应的物理页号。
3. 拿物理页号，加上偏移量，得到物理内存地址。

若进程访问的虚拟地址不在页表上，则产生一个缺页异常，先将进程阻塞，再将硬盘中对应的页换入内存、更新页表，再让进程运行。采用分页后，释放内存都是以页为单位，这样就不会产生进程无法使用的小内存（内存碎片）。同时，在内存交换时，只需交换若干页，大大提高了效率。

但操作系统可以同时运行很多进程，这会使简单分页产生的页表过大。

多级页表

于是，就有了多级页表。若上一级页表的页表项未被用到，则无需创建对应的下一级页表，从而节省了内存。但寻址时需要多级表参与，会增加时间的开销。

TLB

于是根据程序的局部性原理，即在一段时间内，程序的执行仅限于其中某一部分。在 CPU 中加入 TLB，缓存最近常被访问的页表项，从而提高地址转换的速度。

段页式

分段和分页并不是对立的，它们可以组合形成段页式。先把程序划分成多个段，再把段划分成多个页，从而在保留逻辑特征的基础上，提高内存的利用率，但会增加硬件成本和系统开销。

页面置换算法

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的交换区。选择调出页面的算法就称为页面置换算法：

1. OPT：淘汰永不使用的，保证最低的缺页率。但很难预知谁不会被使用，因此无法实现。
2. FIFO：淘汰最先进入的。
3. LRU：淘汰最近最少使用的。它会赋予每个页一个访问字段，记录该页自上次访问后经历的时间 T。这样，当需要淘汰时，就淘汰 T 值最大的。
4. LFU：淘汰最少使用的。

Linux 内存管理

Linux 系统主要采用分页，同时也用分段，用于访问控制和内存保护。另外，Linux 系统中虚拟空间可分为用户态和内核态两部分。

4、进程的内存空间分配？各个段的作用是什么？

能够手画下图：

一个进程的内存空间布局如下：

一个程序分为如下段：

• Text：代码段
• Data（initialized）：已初始化的数据段
• BSS：未初始化的数据段
• Heap：堆
• Memory Mapping：内存映射段
• Stack：栈

从低地址到高地址的用户空间内存区域排列为：

代码段 Text：

CPU 执行的程序指令部分，为了程序的安全性，通常情况下是只读的，程序段可以被父子进程共享。

已初始化的数据段 Data：

在程序执行之前已经明确赋值的变量部分，所以有初值的全局变量和 static 变量在 Data 区。

未初始化的数据段 BSS：

用来存放程序中未初始化的全局变量的一块内存区域，在程序载入时由内核清 0，段内包含：

• 初始化为 0 的全局变量/静态变量
• 源码中未显示进行初始化的变量

堆 Heap：

堆通常用作动态内存分配，堆空间起始于 BSS 段的末尾，并向高地址处生长，堆空间通常由 malloc, realloc 及 free 管理，这些接口可能再使用 brk/sbrk 系统调用来调整大小，在一个进程中，堆空间被进程内所有的共享库及动态加载模块所共享。

栈 Stack：

栈保存函数的局部变量（但不包括 static 声明的变量， static 意味着在数据段中存放变量）、参数以及返回值，栈区域由高地址向低地址增长。

5、进程间通信的方式有哪些？区别是什么？

面试题：什么是协程，协程和线程的区别和联系？进程和线程的区别和联系？

进程是计算机资源（包括 CPU、内存、磁盘 IO 等）分配的最小单位，线程是程序执行（CPU 调度和分配）的最小单位。

进程有独立的地址空间，每启动一个进程，系统都会为进程分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种开销非常昂贵。线程没有地址空间，但是线程共享所属进程的地址空间。

同一进程中的多个线程共享所属进程的代码段（代码和常量）、数据段（全局变量和静态变量）、扩展段（堆存储），但是每个线程拥有自己的栈段（又叫运行时段，用于存放所有局部变量和临时变量）、寄存器的内容。

健壮性：因为不同进程有自己独立的地址空间，所以一个进程死掉，不会对其他进程造成影响。而一个线程死掉，线程所属的整个进程可能也会死掉，所以多进程方式比多线程方式更加健壮。

6、什么是进程状态？进程状态都有哪些？三态模型之间是如何转换的？

• 进程的状态是什么？（一个进程的生命状态）进程的状态都有哪些？（三态模型：运行态、就绪态、阻塞态；五态模型：新建态、终止态、运行态、就绪态、阻塞态）
• 什么是就绪态、阻塞态、运行态？（就绪态：具备运行条件，但是没有空闲 CPU，暂时不能运行；阻塞态：因等待某一事件而暂时不能运行；运行态：占有 CPU，并在 CPU 上正在运行；）三者的转换关系是什么？（转换图）
• 五态模型的转换关系是什么？（转换图）
• 进程阻塞的原因？（等待 I/O、进程 sleep、等待解锁等）
• 什么是 CPU 时间片轮转调度？（时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则 CPU 将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 当即进行切换）
• 进程阻塞会消耗 CPU 资源吗？（不会，CPU 会发生时间片轮转调度，去执行下一个进程）
• 进程阻塞不会消耗系统资源？（系统资源不仅包括 CPU，还有内存、磁盘 IO 等。进程阻塞不会消耗 CPU 资源，当然不代表不会消耗系统资源。而且进程是系统进行资源分配的最小单位。进程虽然阻塞了，但仍然存在，存在就会占用系统资源。）

7、进程切换和线程切换的区别？

虚拟内存是操作系统为每个进程提供的一种抽象，每个进程都有属于自己的、私有的、地址连续的虚拟内存，当然我们知道最终进程的数据及代码必然要放到物理内存上，那么必须有某种机制能记住虚拟地址空间中的某个数据被放到了哪个物理内存地址上，这就是所谓的地址空间映射，也就是虚拟内存地址与物理内存地址的映射关系，那么操作系统是如何记住这种映射关系的呢，答案就是页表，页表中记录了虚拟内存地址到物理内存地址的映射关系。有了页表就可以将虚拟地址转换为物理内存地址了，这种机制就是虚拟内存。

每个进程都有自己的虚拟地址空间，进程内的所有线程共享进程的虚拟地址空间。

进程切换与线程切换的一个最主要区别就在于进程切换涉及到虚拟地址空间的切换而线程切换则不会。因为每个进程都有自己的虚拟地址空间，而线程是共享所在进程的虚拟地址空间的，因此同一个进程中的线程进行线程切换时不涉及虚拟地址空间的转换。

8、什么是用户态？内核态？为什么要区分内核空间和用户空间？

• 什么是用户态？什么是内核态？什么是系统调用？（用户态提供应用程序运行的空间，为了使应用程序访问到内核管理的资源例如 CPU、内存、I/O 等，内核必须提供一组通用的访问接口，这些接口就叫系统调用（System Call）。内核是一种特殊的软件程序，特殊在哪儿呢？内核控制计算机的硬件资源，例如协调 CPU 资源、分配内存资源、并且提供稳定的环境供应用程序运行。）
• 为什么需要区分内核空间与用户空间？（对于 Linux 来说，通过区分内核空间和用户空间的设计，隔离了操作系统代码（操作系统的代码要比应用程序的代码健壮很多）与应用程序代码。即便是单个应用程序出现错误也不会影响到操作系统的稳定性，这样其它的程序还可以正常的运行，所以，区分内核空间和用户空间本质上是要提高操作系统的稳定性及可用性。）
• 当进程运行在内核空间时就处于内核态，而进程运行在用户空间时则处于用户态。
• 用户态到内核态怎样切换？（系统调用、异常、外设中断）
• 系统调用和库函数的区别？（系统调用指运行在用户空间的程序向操作系统内核请求需要更高权限运行的服务，它通过软中断向内核态发出一个明确的请求，系统调用运行在内核空间；库函数用于提供用户态服务，它可能调用封装了一个或几个不同的系统调用（printf 调用 write），也可能直接提供用户态服务（atoi 不调用任何系统调用），库函数运行在用户空间；）

9、磁盘 I/O 都有哪些方式？各自的区别是什么？

1、缓存 IO：

缓存 IO 的优点：

• 在一定程度上分离了内核空间和用户空间，保护系统本身的运行安全
• 可以减少读盘的次数，从而提高性能

缓存 IO 的缺点：

• 数据在传输过程中需要在应用程序地址空间（用户空间）和缓存（内核空间）之间进行多次数据拷贝操作

2、直接 IO：

直接 IO 的特点：直接 IO 是不经过 Page Cache 的，多用于数据库，如果访问的数据不在应用程序缓存中，那么每次数据都会直接从磁盘进行加载，这种直接加载会非常缓慢。

3、mmap：

10、孤儿进程是什么？有危害吗？

父进程已经退出，而它的一个或多个子进程还在运行，这些子进程将成为孤儿进程，孤儿进程会被 init 进程（进程号为 1）收养，并由 init 进程完成对它们的状态收集工作。

当孤儿进程结束之后，init 进程会回收其占用的资源，因此孤儿进程其实没有多少危害。

11、什么是僵尸进程？如何解决？

在每个进程退出的时候，内核释放该进程所有的资源，包括打开的文件、占用的内存等。但是仍然为其保留一定的信息（包括进程号、退出状态、运行时间等）。直到父进程通过 wait / waitpid 来获取时才释放。

如果一个进程通过 fork 创建了子进程，如果子进程退出而父进程没有调用 wait() 或 waitpid() 获取子进程的状态信息，那么子进程占用的资源就不会释放，系统能使用的进程号是有限的，如果有大量的僵尸进程，将因为没有可用的进程号而导致无法创建新的进程。

如果父进程退出了，子进程将由僵尸进程变成孤儿进程，从而被 init 进程接管，init 进程会释放其占用的资源。

我们在进行多进程编程的时候，一定要用 wait 来回收退出的子进程。

12、软链接和硬链接是什么？区别是什么？

什么是硬链接？

硬链接通过索引节点进行连接，多个文件名指向同一索引节点，同一索引节点指向的是同一文件。

什么是软链接？

软链接本质是新建一个文件，保存原文件的路径名，相当于快捷方式，因此新建文件和原文件的 inode 是不同的。

软链接和硬链接的区别是什么？

1. 硬链接不支持为目录创建硬链接，但软链接可以
2. 硬链接和软链接中对目标文件的修改都会在原文件中保持同步。
   • 删除原文件，硬链接目标文件不受影响；删除硬链接目标文件，原文件不受影响。
   • 删除原文件，软链接目标文件成为断链（没有链接对象）；删除软链接目标文件，原文件不受影响。

13、同一个进程内的线程会共享什么资源？

线程和进程资源比较：

线程占有的都是不共享的：栈、寄存器、状态、程序计数器。

线程共享进程的：地址空间、全局变量、打开的文件、子进程、堆空间等。

传送门：leetcode - 226 翻转二叉树。

思路：递归。

实现：

/**
 * @param TreeNode $root
 * @return TreeNode
 */
function invertTree($root) {
    // 递归函数的终止条件，节点为空时返回
    if (is_null($root)) {
        return null;
    }

    // 下面三句是将当前节点的左右子树交换
    $tmp = $root->left;
    $root->left = $root->right;
    $root->right = $tmp;

    //递归交换当前节点的左子树
    $this->invertTree($root->left);
    // 递归交换当前节点的右子树
    $this->invertTree($root->right);

    return $root;
}

1、什么是荷兰国旗问题？

题目描述：给定一个数组 arr，和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在数组的中间，大于 num 的数放在数组的右边。

思路：

将数组分为小于区域、等于区域、大于区域三部分。
假如数组为 [3, 6, 4, 2, 7]，num 为 4。

less) [3, 6, 4, 2, 7] (more  
^      ^               ^  
less  curr             more  

当 curr 小于 num 时，当前数和小于区域的下一个数交换，curr 右移，小于区域右移。

less [3),  6, 4, 2, 7] (more  
      ^    ^            ^  
      less curr         more  

当 curr 大于 num 时，当前数和大于区域的下一个数交换，curr 不移，大于区域左移。

less [3),  7, 4, 2, (6] more  
      ^    ^         ^  
      less curr      more  

于是，curr 继续比较。

less [3),  2, 4, (7, 6] more  
      ^    ^      ^  
      less curr   more  

此时，curr 小于 num。

less [3,  2),  4,     (7, 6] more  
          ^    ^      ^  
          less curr   more  

当 curr 等于 num 时，小于区域不移，大于区域也不移，curr 右移。

代码实现：

<?php

class NetherlandsFlag
{
    public static function partition(&$arr, $left, $right, $num)
    {
        // 小于区域指针
        $less = $left - 1;
        // 大于区域指针
        $more = $right + 1;
        // 当前位置指针
        $curr = $left;

        while ($curr < $more) {
            // 当前数和小于区域的下一个数交换，curr 右移，小于区域右移
            if ($arr[$curr] < $num) {
                self::swap($arr, ++$less, $curr++);
            } 
            // 当前数和大于区域的下一个数交换，curr 不移，大于区域左移
            elseif ($arr[$curr] > $num) {
                self::swap($arr, --$more, $curr);
            } 
            // 小于区域和大于区域都不移，curr 右移
            else {
                $curr++;
            }
        }

        // 返回等于区域
        return [$less + 1, $more - 1];
    }

    public static function swap(&$arr, $i, $j)
    {
        $tmp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $tmp;
    }
}

// Test
$arr = [3, 6, 4, 2, 7];
// [2, 2]
var_dump(NetherlandsFlag::partition($arr, 0, count($arr) - 1, 4));
// [3, 2, 4, 7, 6]
var_dump($arr);

2、什么是颜色分类问题？ 传送门：【leetcode-75】颜色分类

思路：和上面的荷兰国旗相同，只是把荷兰国旗中需要比较的数置为 1 即可。

代码实现：

class Solution 
{
    static function swap(&$arr, $i, $j)
    {
        $tmp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $tmp;
    }

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function sortColors(&$nums) 
    {
        $num = 1;
        $less = -1;
        $more = count($nums);
        $curr = 0;

        while ($curr < $more) {
            if ($nums[$curr] < $num) {
                self::swap($nums, $curr++, ++$less);
            } elseif ($nums[$curr] > $num) {
                self::swap($nums, $curr, --$more);
            } else {
                $curr++;
            }
        }
    }
}

Kafka

1、为什么需要 MQ？

核心就三点：异步、削峰、解耦。

2、消息模型有哪两种？区别是什么？

点对点模型、发布/订阅模型。

发布订阅模型可以实现多个订阅者消费同一个 Topic。

3、Zookeeper 在 Kafka 中的作用？

4、说一下 Kafka 集群的组成？

最好能够手画下面这张图：

5、Kafka 可以保证某个 Topic 下的消息有序吗？

Kafka 保证的是分区有序而不是主题有序。

6、什么是 AR、ISR、OSR？

分区中的所有副本统称为 AR（Assigned Replicas）。所有与 leader 副本保持一定程度同步的副本（包括 leader 副本在内）组成 ISR（In-Sync Replicas），ISR 集合是 AR 集合中的一个子集。消息会先发送到 leader 副本，然后 follower 副本才能从 leader 副本中拉取消息进行同步，同步期间内 follower 副本相对于 leader 副本而言会有一定程度的滞后。

前面所说的一定程度的同步是指可忍受的滞后范围，这个范围可以通过参数进行配置。与 leader 副本同步滞后过多的副本（不包括 leader 副本）组成 OSR（Out-of-Sync Replicas），由此可见，AR = ISR + OSR。在正常情况下，所有的 follower 副本都应该与 leader 副本保持一定程度的同步，即 AR=ISR，OSR 集合为空。

7、什么是 HW、LEO？

HW 是 High Watermark 的缩写，俗称高水位，它标识了一个特定的消息偏移量（offset），消费者只能拉取到这个 offset 之前的消息。

LEO 是 Log End Offset 的缩写，它标识当前日志文件中下一条待写入消息的 offset。

7、Kafka 支持读写分离吗？为什么？

Kafka 是不支持读写分离的，因为读写分离会带来数据不一致的问题。

8、为什么 Kafka 这么快？

1. Partition 并行处理
2. 顺序读写磁盘，充分利用磁盘特性
3. 采用了零拷贝技术

• Producer 生产的数据持久化到 broker，采用 mmap 文件映射，实现顺序的快速写入
• Customer 从 broker 读取数据，采用 sendfile，数据通过 DMA 拷贝到内核态 Buffer 后，直接通过 DMA 拷贝到 NIC Buffer，无需 CPU 拷贝

4. 数据压缩

9、Kafka 是如何保证高可用的？

Replica 备份机制、ACK 机制、ISR 机制、故障恢复机制。

10、ISR 是一种什么同步机制？

Kafka 不是完全同步，也不是完全异步，是一种 ISR 机制，它是基于 Replica 机制和 ACK 机制同步完成的。

11、Kafka 会不会丢数据？

会。

12、如何保证消息不被重复消费？

保证幂等。

13、如何保证消息的顺序性？

同一个 Partition 下消息有序，多个 Partition 下消息不一定有序，可以将消息根据 key 路由到指定的 Partition 上，这样就保证了有序。

另外，实际业务中，Producer 写入消息的时候还可以写入微秒时间戳，可以判断哪条消息先写入的，哪条消息后写入的。

14、如何保证消息的可靠性传输？

一般是要求起码设置如下 4 个参数：

• 给 Topic 设置 replication.factor 参数：这个值必须大于 1，要求每个 partition 必须有至少 2 个副本。
• 在 Kafka 服务端设置 min.insync.replicas 参数：这个值必须大于 1，这个是要求一个 eader 至少感知到有至少一个 Follower 还跟自己保持联系，没掉队，这样才能确保 Leader 挂了还有一个 Follower 吧。
• 在 producer 端设置 acks=all：这个是要求每条数据，必须是写入 ISR 中所有 replica 之后，才能认为是写成功了。
• 在 producer 端设置 retries=MAX（很大很大很大的一个值，无限次重试的意思）：这个是要求一旦写入失败，就无限重试，卡在这里了。

15、Acks 参数的作用是什么？

生产者发送消息中包含 acks 字段，该字段代表 Leader 应答生产者前 Leader 收到的应答数。

• acks = 0：生产者无需等待服务端的任何确认，消息被添加到生产者套接字缓冲区后就视为已发送，因此不能保证服务端已收到消息
• acks = 1：只要 Partition Leader 接收到消息而且写入本地磁盘了，就认为成功了，不管它其他的 Follower 有没有同步过去这条消息了
• acks = all：Leader 将等待 ISR 中的所有副本确认后再做出应答，因此只要 ISR 中任何一个副本还存活着，这条应答过的消息就不会丢失

16、Kafka 副本是怎么管理的？

• AR：分区中的所有 Replica 统称为 AR
• ISR：所有与 Leader 副本保持一定程度同步的 Replica（包括 Leader 副本在内）组成 ISR
• OSR：与 Leader 副本同步滞后过多的 Replica 组成了 OSR

Leader 负责维护和跟踪 ISR 集合中所有 Follower 副本的滞后状态，当 Follower 副本落后过多时，就会将其放入 OSR 集合，当 Follower 副本追上了 Leader 的进度时，就会将其放入 ISR 集合。

17、如何确定当前能读到哪一条消息？

考察 HW 和 LEO 的概念。

17、发送消息的分区策略有哪些？

1. 轮询：依次将消息发送该 Topic 下的所有分区，如果在创建消息的时候 key 为 null，Kafka 默认采用这种策略。
2. key 指定分区：在创建消息是 key 不为空，并且使用默认分区器，Kafka 会将 key 进行 hash，然后根据 hash 值映射到指定的分区上。这样的好处是 key 相同的消息会在一个分区下，Kafka 并不能保证全局有序，但是在每个分区下的消息是有序的，按照顺序存储，按照顺序消费。在保证同一个 key 的消息是有序的，这样基本能满足消息的顺序性的需求。但是如果 partation 数量发生变化，那就很难保证 key 与分区之间的映射关系了。
3. 自定义策略：实现 Partitioner 接口就能自定义分区策略。
4. 指定 Partiton 发送

18、Kafka 是怎么去实现负载均衡的？

Kafka 的负责均衡主要是通过分区来实现的，我们知道 Kafka 是主写主读的架构，如下图：

共三个 broker ，里面各有三个副本，总共有三个 Partation， 深色的是 Leader，浅色的是 Follower，上下灰色分别代表生产者和消费者，虚线代表 Follower 从 Leader 拉取消息。

我们从这张图就可以很明显的看出来，每个 broker 都有消费者拉取消息，每个 Broker 也都有生产者发送消息，每个 Broker 上的读写负载都是一样的，这也说明了 Kafka 独特的架构方式可以通过主写主读来实现负载均衡。

19、Kafka 的负责均衡会有什么问题呢？

1. broker 端分配不均：当创建 Topic 的时候可能会出现某些 broker 分配到的分区数多，而有些 broker 分配的分区少，这就导致了 Leader 多副本不均。
2. 生产者写入消息不均：生产者可能只对某些 broker 中的 Leader 副本进行大量的写入操作，而对其他的 Leader 副本不闻不问。
3. 消费者消费不均：消费者可能只对某些 broker 中的 Leader 副本进行大量的拉取操作，而对其他的 Leader 副本不闻不问。
4. Leader 副本切换不均：当主从副本切换或者分区副本进行了重分配后，可能会导致各个 broker 中的 Leader 副本分配不均匀。

20、副本 Leader 是怎么选举的？

一般是从 ISR 队列中选举，但是可以开启 Unclean 领导者选举。

传送门：剑指 Offer 62 - 圆圈中最后剩下的数字。

猴子选大王：一群猴子排成一圈，按 1,2,…,n 依次编号。然后从第 1 只开始数，数到第 m 只，把它踢出圈，从它后面再开始数，再数到第 m 只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入 m、n，输出最后那个大王的编号。用程序模拟该过程。

思路 1：

/**
 * @param Integer $n
 * @param Integer $m
 * @return Integer
 */
function lastRemaining($n, $m)
{
    // 从第一个开始循环
    $i = 1;

    // 创建一个从 1 到 $n - 1 的数组
    $arr = range(0, $n - 1);

    while (count($arr) > 1) {
        // 不被整除则压入数组尾部
        if ($i % $m !== 0) {
            array_push($arr, $arr[$i - 1]);
        }
        unset($arr[$i - 1]);
        $i++;
    }

    return $arr[$i - 1];
}

思路 2：

这个问题实际上是约瑟夫问题。

既然约塞夫问题就是用人来举例的，那我们也给每个人一个编号（索引值），每个人用字母代替，下面这个例子是 N=8 m=3 的例子，我们定义 F(n,m) 表示最后剩下那个人的索引号，因此我们只关心最后剩下来这个人的索引号的变化情况即可。

从 8 个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人作为开头重新编号。

• 第一次 C 被杀掉，人数变成 7，D 作为开头（最终活下来的 G 的编号从 6 变成 3）
• 第二次 F 被杀掉，人数变成 6，G 作为开头（最终活下来的 G 的编号从 3 变成 0）
• 第三次 A 被杀掉，人数变成 5，B 作为开头，（最终活下来的 G 的编号从 0 变成 3）
• 以此类推，当只剩一个人时，他的编号必定为0！（重点！）

最终活着的人编号的反推

现在我们知道了 G 的索引号的变化过程，那么我们反推一下从 N = 7 到 N = 8 的过程。

如何才能将 N = 7 的排列变回到 N = 8 呢？

我们先把被杀掉的 C 补充回来，然后右移 m 个人，发现溢出了，再把溢出的补充在最前面。神奇了，经过这个操作就恢复了 N = 8 的排列了！

因此我们可以推出递推公式 f(8,3) = [f(7, 3) + 3] % 8。

进行推广泛化，即 f(n,m) = [f(n-1, m) + m] % n。

/**
 * @param Integer $n
 * @param Integer $m
 * @return Integer
 */
function lastRemaining($n, $m)
{
    $x = 0;
    for ($i = 2; $i <= $n; $i++) {
        $x = ($x + $m) % $i;
    }
    return $x;
}

堆是一个利用完全二叉树的结构来维护的一维数组，任意结点小于（或大于）它的左右子节点，最小值（或最大值）在根结点位置。

最小值在根节点（堆顶）的叫做小根（顶）堆，最大值在根节点（堆顶）的叫做大根（顶）堆。

完全二叉树：完全二叉树除最后一层外，每一层的结点数均达到最大值，在最后一层上只缺少右边的若干结点，即最后一层的结点优先填在左边。

如何将一棵完全二叉树构建为最大堆？

比如现在有一个数组为：arr = [5, 1, 13, 3, 16, 7, 10, 14, 6, 9]，它的完全二叉树结构如下图：

将该完全二叉树构建为最大堆的代码如下：

<?php

$arr = [5, 1, 13, 3, 16, 7, 10, 14, 6, 9];

for ($i = 1; $i < count($arr); $i++) {
    // 0 - i 区间形成大根堆
    heapInsert($arr, $i);
}

/**
 * 构建大根堆（加入一个结点并向上调整的过程）
 *
 * @param $arr
 * @param $index
 */
function heapInsert(&$arr, $index)
{
    while ($arr[$index] > $arr[intval(($index - 1) / 2)]) {
        // 父结点
        $parent = intval(($index - 1) / 2);
        // swap
        list($arr[$index], $arr[$parent]) = [$arr[$parent], $arr[$index]];
        // 索引来到父结点位置
        $index = $parent;
    }
}

print_r($arr);

执行结果：

Array
(
    [0] => 16
    [1] => 14
    [2] => 10
    [3] => 13
    [4] => 9
    [5] => 5
    [6] => 7
    [7] => 1
    [8] => 6
    [9] => 3
)

大根堆的构建结果如下图：

构建堆的时间复杂度分析：构建堆时，从第 2 个结点开始向上调整，第 2 个结点调整次数 log2，第 3 个结点调整次数 log3，第 N 个结点调整次数 logN，所以，构建堆的时间复杂度为：log2 + log3 + ... + logN = O(N)，其中 O(N) 是推导得出的结论。

传送门：剑指 Offer 50 - 第一个只出现一次的字符。

思路：有序哈希表。

Java 使用 LinkedHashMap 实现有序哈希表，而 PHP 的 Array 结构已经实现了有序哈希。

实现：

class Solution
{
    /**
     * @param String $s
     * @return String
     */
    function firstUniqChar($s)
    {
        $map = [];

        $len = strlen($s);

        for ($i = 0; $i < $len; $i++) {
            if (isset($map[$s[$i]])) {
                $map[$s[$i]] += 1;
            } else {
                $map[$s[$i]] = 1;
            }
        }

        foreach ($map as $k => $v) {
            if ($v === 1) return $k;
        }

        return ' ';
    }
}

传送门：剑指 Offer 63 - 股票的最大利润。

思路：动态规划。

实现：

class Solution 
{
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) 
    {
        $cost = PHP_INT_MAX;
        $profit = 0;

        for ($i = 0; $i < count($prices); $i++) {
            $cost = min($cost, $prices[$i]);
            $profit = max($profit, $prices[$i] - $cost);
        }

        return $profit;
    }
}

传送门：从尾到头打印链表。

思路：利用栈后进先出的特点。

实现：

<?php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution
{
    private $help = [];

    /**
     * @param ListNode $head
     * @return Integer[]
     */
    function reversePrint($head)
    {
        $curr = $head;
        while ($curr !== null) {
            // 往数组头部插入元素
            array_unshift($this->help, $curr->val);
            $curr = $curr->next;
        }
        return $this->help;
    }
}

传送门：leetcode - 3 无重复字符的最长子串。

思路：滑动窗口。

什么是滑动窗口？

其实就是一个队列，比如例题中的 pwwkew，进入这个队列（窗口）为 pw 满足题目要求，当再进入 w，队列变成了 pww，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要从队列的左边开始将元素移出，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)。

实现：

class Solution 
{
    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s) {
        if (empty($s)) return 0;

        $map = [];

        $max = 0;
        $start = 0;

        for ($end = 0; $end < strlen($s); $end++) {
            if (isset($map[$s[$end]])) {
                $start = max($start, $map[$s[$end]] + 1);
            }
            $map[$s[$end]] = $end;
            $max = max($max, $end - $start + 1);
        }

        return $max;
    }
}

传送门：剑指 Offer 42 - 连续子数组的最大和。

思路：

1、状态，即子问题。
dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。

2、转移策略，自带剪枝。
若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。

3、状态转移方程，根据前两步抽象而来。

• 当 dp[i−1]>0 时：执行 dp[i] = dp[i-1] + nums[i]；
• 当 dp[i−1]≤0 时：执行 dp[i] = nums[i] ；

实现：

class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function maxSubArray($nums)
    {
        $res = $nums[0];

        for ($i = 1; $i < count($nums); $i++) {
            if ($nums[$i - 1] > 0) {
                $nums[$i] = $nums[$i - 1] + $nums[$i];
            }
            $res = max($res, $nums[$i]);
        }

        return $res;
    }
}

传送门：剑指 Offer 29 - 顺时针打印矩阵。

传送门：剑指 Offer 58 - II 左旋转字符串。

class Solution
{
    /**
     * @param String $s
     * @param Integer $n
     * @return String
     */
    function reverseLeftWords($s, $n)
    {
        $leftStr = substr($s, 0, $n);
        $rightStr = substr($s, $n);
        return $rightStr . $leftStr;
    }
}

传送门：二分查找。

实现：

class Solution
{
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target)
    {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = intval(floor(($left + $right) / 2));
            if ($nums[$mid] === $target) {
                return $mid;
            } elseif ($nums[$mid] > $target) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        return -1;
    }
}

传送门：leetcode - 20 有效的括号。

思路：

使用栈数据结构来解决。

实现：

/**
 * @param String $s
 * @return Boolean
 */
function isValid($s) 
{
    // 哈希表
    $map = ['(' => ')', '[' => ']', '{' => '}'];

    // 存储左括号的栈
    $stack = [];

    $len = strlen($s);

    for ($i = 0; $i < $len; $i++) {
        $char = $s[$i];

        // 左括号入栈
        if (isset($map[$char])) {
            array_push($stack, $map[$char]);
        }
        // //右括号，分 2 种情况判断
        else {
            if (empty($stack) || array_pop($stack) != $char) {
                return false;
            }
        }
    }

    // 返回时，判断栈是否为空
    return empty($stack);
}

传送门：剑指 Offer 04 - 二维数组中的查找。

思路 1：暴力法。

class Solution
{
    /**
     * @param Integer[][] $matrix
     * @param Integer $target
     * @return Boolean
     */
    function findNumberIn2DArray($matrix, $target)
    {
        foreach ($matrix as $k => $line) {
            foreach ($line as $kk => $num) {
                if ($num === $target) {
                    return true;
                }
            }
        }
        return false;
    }
}

思路 2：

若使用暴力法遍历矩阵 matrix ，则时间复杂度为 O(NM)。暴力法未利用矩阵从上到下递增、从左到右递增的特点，显然不是最优解法。
如下图所示，我们将矩阵逆时针旋转 45°，并将其转化为图形式，发现其类似于二叉搜索树，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从根节点开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target 。

class Solution
{
    /**
     * @param Integer[][] $matrix
     * @param Integer $target
     * @return Boolean
     */
    function findNumberIn2DArray($matrix, $target)
    {
        $i = count($matrix[0]) - 1;
        $j = 0;

        while ($i >= 0 && $j < count($matrix)) {
            if ($matrix[$j][$i] > $target) {
                $i--;
            } elseif ($matrix[$j][$i] < $target) {
                $j++;
            } else {
                return true;
            }
        }
        return false;
    }
}

计算机网络

1、网络模型有哪几种？不同模型的区别是什么？

目前存在 3 种划分网络模型的方式：

• OSI 七层模型

• TCP/IP 四层模型

• 五层模型

• 七层网络模型：正统意义上的国际标准网络模型

• 四层网络模型：简称 TCP/IP 协议，最核心的两个协议是 TCP/IP，是事实上的国际标准网络模型

• 五层网络模型：学习和开发用的网络模型

2、TCP/IP 指的是 TCP、IP 这两种协议吗？

从字面意义看，很多人会认为 TCP/IP 是 TCP、IP 这两种协议，实际上 TCP/IP 指的是网络通信过程中用到的协议的统称。由于该协议族中最核心的两个协议分别为 TCP（传输控制协议）和 IP（网际协议），因此它也被称为 TCP/IP 协议族（TCP/IP Protocol Suite 或 TCP/IP Protocols），简称 TCP/IP，它具有四层网络结构。

3、五层网络模型都有哪五层？简单描述一下各层的作用是什么？各层的传输单元是什么？

五层：应用层、传输层、网络层、数据链路层、物理层。

应用层：规定应用程序之间如何传递报文，比如 HTTP 协议，HTTP 客户端和 HTTP 服务端的首要工作就是根据 HTTP 协议的标准组装和解析 HTTP 数据包，每个 HTTP 报文格式由三部分组成：请求行/响应行、请求头/响应头、请求体/响应体。

传输层：为两台主机提供端到端的逻辑通信，相隔几千里的两台主机的进程就好像在直接通信一样。

网络层：提供了主机到主机的通信，将传输层产生的报文段封装成分组数据包发送到目的主机，并提供路由选择的能力。

数据链路层：以太网、Wifi、蓝牙工作在这一层，网络访问层提供了主机连接到物理网络需要的硬件和相关的协议。

4、五层网络模型中，各层都有哪些协议？

• 应用层：HTTP、域名解析协议 DNS、收发邮件 SMTP 和 POP3 协议、时钟同步协议 NTP、网络文件共享协议 NFS、文件传输协议 FTP
• 传输层：TCP、UDP
• 网络层：IP
• 数据链路层：暂不需要记忆
• 物理层：暂不需要记忆

5、假设你正在电脑上用微信跟女朋友聊天，用 QQ 跟技术大佬们讨论技术细节，当电脑收到一个数据包时，它怎么知道这是一条微信的聊天内容，还是一条 QQ 的消息呢？

通过端口号，传输层用端口号来标识不同的应用程序。

6、IP 协议在哪一层？这一层给传输层交付的报文段封装了什么重要信息？IP 协议是无连接的吗？

IP 协议是网络层的主要协议，TCP 和 UDP 都是用 IP 协议作为网络层协议。这一层的主要作用是给包加上源地址和目标地址，将数据包传送到目标地址。

IP 协议是一个无连接的协议，也不具备重发机制，这也是 TCP 协议复杂的原因之一就是基于了这样一个不靠谱的协议。

7、收到 IP 数据包解析以后，它怎么知道这个分组应该投递到上层的哪一个协议（TCP 和 UDP）？

IP 协议中有一个 Protocol 字段，为 6 表示 TCP。

8、五层网络模型中，各层的传输单元是什么？

• 应用层：报文
• 运输层：报文段或用户数据报
• 网络层：IP 数据报，也称数据包、分组、包
• 数据链路层：帧
• 物理层：比特

9、网络分层的好处是什么？

各层独立、灵活性更好、易于测试和维护、能促进标准化

10、徒手画出五层网络模型，包括各层的协议都有哪些、封装了什么信息等

11、什么是 MAC 地址？

集线器 HUB 工作在物理层，它的每个接口仅仅简单地转发比特，收到 1 就转发 1，收到 0 就转发 0，不进行差错检测，由于转发到了所有出口，那么这几台机器怎么知道数据包是不是发给自己的呢？

首先，你要给所有的连接到集线器的设备，都起个名字。原来你们叫 ABCD，但现在需要一个更专业的，全局唯一的名字作为标识，你把这个更高端的名字称为 MAC 地址。

你的 MAC 地址是 aa-aa-aa-aa-aa-aa，你的伙伴 B 的 MAC 地址是 bb-bb-bb-bb-bb-bb，以此类推，不重复就好。

MAC 地址又称为物理地址、硬件地址，但是不要被物理二字误导认为物理地址属于物理层范畴，物理地址属于数据链路层范畴。

MAC 地址是 6 个字节，48 位，IEEE 的注册管理机构 RA 负责向厂家分配地址字段的前三个字节（即高位 24 位）。地址字段中的后三个字节（即低位 24 位）由厂家自行指派，称为扩展标识符，必须保证生产出的适配器没有重复地址。

12、集线器和交换机的区别是什么？

• 集线器：仅仅是无脑地将电信号转发到所有出口（广播），不做任何处理，你觉得它是没有智商的，因此人家定性在了物理层。
• 交换机：如果把这个集线器弄得更智能一些，只发给目标 MAC 地址指向的那台电脑，就好了。虽然只比集线器多了这一点点区别，但看起来似乎有智能了，你把这东西叫做交换机。也正因为这一点点智能，你把它放在了另一个层级，数据链路层。交换机内部维护一张 MAC 地址表，记录着每一个 MAC 地址的设备，连接在其哪一个端口上。

13、交换机最开始的时候，MAC 地址表是空的，是怎么逐步建立起来的呢？

交换机的自学习过程。

14、为什么有了 MAC 地址，还需要 IP 地址？

交换机需要维护 MAC 地址与端口的映射关系，当机器数量增多时，交换机就无法维护如此庞大的映射关系了。

IP 地址是地域相关的，多个 IP 地址可以汇聚表示，而 MAC 地址是地域无关的难以汇聚，所以大规模网络只能增加路由器进行三层路由组网了。

注意，路由器的每一个端口，都有独立的 MAC 地址。

15、机器 A 给机器 C 发送数据包，怎么知道二者是否在同一个子网下，不需要通过路由器转发？

通过子网掩码，判断机器 A 和 机器 C 是否在同一个子网下。

假如机器 A 的 IP：192.168.0.1，机器 A 的子网掩码：255.255.255.0，机器 C 的 IP：192.168.1.1。

将源 IP：192.168.0.1 与目的 IP：192.168.0.1 分别同这个子网掩码：255.255.255.0 进行与运算，相等则是在一个子网，不相等则是在不同子网，就这么简单。

192.168.0.1 & 255.255.255.0 = 192.168.0.0
192.168.1.1 & 255.255.255.0 = 192.168.1.0

因此 A 和 C 不在同一个子网下。

16、什么是 ARP 协议？

我们只知道 IP 地址，可是数据链路层需要知道 MAC 地址怎么办？

假如你（A）此时不知道你同伴 B 的 MAC 地址（现实中就是不知道的，刚刚我们只是假设已知），你只知道它的 IP 地址，你该怎么把数据包准确传给 B 呢？

答案很简单，在网络层，我需要把 IP 地址对应的 MAC 地址找到，也就是通过某种方式，找到 192.168.0.2 对应的 MAC 地址 BBBB。

这种方式就是 ARP 协议，同时电脑 A 和 B 里面也会有一张 ARP 缓存表，表中记录着 IP 地址与 MAC 地址的对应关系。

一开始的时候这个表示空的，电脑 A 为了知道电脑 B（192.168.0.2）的 MAC 地址，将会广播一条 ARP 请求，B 收到请求后，带上自己的 MAC 地址给 A 一个响应。此时 A 便会更新自己的 ARP 表。

这样通过大家不断地广播 ARP 请求，最终所有电脑里面都将 ARP 缓存表更新完整。

17、分别从电脑视角、交换机视角、路由器视角来分析数据的传输过程

电脑视角：

• 首先我要知道我的 IP 和对方的 IP
• 通过子网掩码判断我们是否在同一个子网
• 在同一个子网就通过 ARP 获取对方 MAC 地址直接扔出去
• 不在同一个子网就通过 ARP 获取默认网关的 MAC 地址直接扔出去

交换机视角：

• 我收到的数据包必须有目标 MAC 地址
• 通过 MAC 地址表查映射关系
• 查到了就按照映射关系从我的指定的端口发出去
• 查不到就所有端口都发出去

路由器视角：

• 我收到的数据包必须有目标 IP 地址
• 通过路由表查映射关系
• 查到了就按照映射关系从我的指定端口发出去（不在任何一个子网范围，走其路由器的默认网关也是查到了）
• 查不到则返回一个路由不可到达的数据包

从始至终这个数据包的两个 IP 地址都是不变的，只有 MAC 地址在不断变化。

18、机器 A 怎么知道，哪个设备是路由器？

如果 A 给 C 发消息，A 和 C 的 IP 地址分别是 & A 机器配置的子网掩码，发现不相等，则 A 认为 C 和自己不在同一个子网，于是把包发给路由器，就不管了，之后怎么转发，A 不关心。

A 如何知道，哪个设备是路由器？

上一步 A 通过是否与 C 在同一个子网内，判断出自己应该把包发给路由器，那路由器的 IP 是多少呢？

其实说发给路由器不准确，应该说 A 会把包发给默认网关。

对 A 来说，A 只能直接把包发给同处于一个子网下的某个 IP 上，所以发给路由器还是发给某个电脑，对 A 来说也不关心，只要这个设备有个 IP 地址就行。

所以默认网关，就是 A 在自己电脑里配置的一个 IP 地址，以便在发给不同子网的机器时，发给这个 IP 地址。

19、描述一下 TCP 的三次握手过程？握手过程中客户端和服务端各自的状态变化是什么？

能够手动画出下面这张图。

三次握手最重要的是交换彼此的 ISN（初始序列号）。

• 第一次握手：客户端发送的一个报文段是 SYN 报文，这个报文只有 SYN 标记被置位。该 SYN 的作用是同步客户端的初始序列号。
• 第二次握手：服务端收到客户端的 SYN 段以后，将 SYN 和 ACK 标记都置位。SYN 标记的作用与第一次握手中的一样，也是同步服务端生成的初始序列号。ACK 用来告知发送端之前发送的 SYN 段已经收到了，确认号字段指定了发送端下次发送段的序号，这里等于客户端 ISN 加 1，与第一次握手一样，该 SYN 段也需要被确认。（SYN + ACK 报文虽然没有携带数据，由于它需要被确认，因此也消耗一个序列号。）
• 第三次握手：客户端发送三次握手最后一个 ACK 段，这个 ACK 段用来确认收到了服务端发送的 SYN 段。因为这个 ACK 段不携带任何数据，且不需要再被确认，这个 ACK 段不消耗任何序列号。

除了交换彼此的初始序列号，三次握手的另一个重要作用是交换一些辅助信息，比如最大段大小（MSS）、窗口大小（Win）、窗口缩放因子（WS）、是否支持选择确认（SACK_PERM）等。

20、为什么 SYN 段不携带数据却要消耗一个序列号呢？

不占用序列号的段是不需要确认的（都没有内容确认个啥），比如 ACK 段。SYN 报文段需要对方的确认，因此需要占用一个序列号。

关于这一点，可以记住如下的规则：

但凡消耗序列号的报文，一定要对端确认，否则会重传直到指定次数为止。

21、为什么 FIN 段不携带数据却要消耗一个序列号呢？

如果发送 FIN 之后没有消耗序列号，那么无法分辨 ACK 是对最后一个 TCP 报文的确认还是 FIN 报文的确认。

和问题 20 一样，还是需要确认的问题。

22、如果客户端发出 SYN 包之后，久久没有收到服务端的 ACK 包会发生什么？

在客户端发出 SYN 包以后，便进入 SYN-SENT 的状态，如果没有收到服务端的 ACK，那么客户端便会一直维持在这个状态，多次重发 SYN 数据包，当重发达到一定次数时便会停止重发，反馈连接失败，Java 中就会报错：java.net.ConnectException: Connection timed out 的异常，这个重发的次数对于 Linux 系统可以查看这个文件 /proc/sys/net/ipv4/tcp_syn_retries，每一次发出 SYN 包后下一次发出的时间便会翻倍，假如 tcp_syn_retries 为 6，那么消耗的时间为 65s = 1s+2s+4s+8s+16s+32s。

23、为什么采用三次握手而不是两次握手？

一句话，为了防止已失效的连接请求报文到达服务器而造成服务器资源浪费的问题。

所谓防止已失效的连接请求报文是这样产生的。考虑一种正常情况。A 发出连接请求，但因连接请求报文丢失而未收到确认。于是 A 再重传一次请求连接。后来收到了确认，建立了连接。数据传输完毕后，就释放了连接。A 共发送了两个连接请求报文段。其中第一个丢失，第二个到达了 B。没有已失效的请求连接报文段。

现假定出现一种异常情况，即 A 发出的第一个请求连接报文段并没有丢失，而是在某些网络结点长时间滞留了，以至到连接释放以后的某个时间才到达 B。本来这是一个已失效的报文段。但 B 收到此失效的连接请求报文段后，就误认为是 A 又发出一次新的连接请求。于是就向 A 发出确认报文段，同意建立连接。假定不采用三次握手，那么只要 B 发出确认，新的连接就建立了。

由于现在 A 并没有发出建立请求的连接，因此不会理睬 B 的确认，也不会向 B 发送数据，但 B 却以为新的运输连接已经建立了，并一直等待 A 发来的数据。B 的许多资源就这样白白浪费了。

采用三次握手的办法可以防止上述现象发生。例如在刚才的情况下，A 不会向 B 的确认发出确认。B 由于收不到确认，就知道 A 并没有要求建立连接，所以就不会分配资源给这个连接。

为什么不是四次握手？

变成四次理论上完全可以，把三次握手的第二次的 SYN + ACK 拆成先回 ACK 包，再发 SYN 包就变成了「四次握手」。

24、描述一下 TCP 的四次挥手过程？挥手过程中客户端和服务端各自的状态变化是什么？

能够手动画出下面这张图。

1、客户端调用 close 方法，执行「主动关闭」，会发送一个 FIN 报文给服务端，从这以后客户端不能再发送数据给服务端了，客户端进入 FIN-WAIT-1 状态，FIN 报文其实就是将 FIN 标志位设置为 1。

FIN 段是可以携带数据的，比如客户端可以在它最后要发送的数据块可以捎带 FIN 段，当然也可以不携带数据。

客户端发送 FIN 包以后不能再发送数据给服务端，但是还可以接受服务端发送的数据，这个状态就是所谓的「半关闭（half-close）」。

主动发起关闭的一方称为主动关闭方，另外一方被称为被动关闭方。

2、服务端收到 FIN 包以后回复确认 ACK 报文给客户端，服务端进入 CLOSE_WAIT，客户端收到 ACK 以后进入 FIN-WAIT-2 状态。

3、服务端也没有数据要发送了，发送 FIN 报文给客户端，然后进入 LAST-ACK 状态，等待客户端的 ACK。

4、客户端收到服务端的 FIN 报文以后，回复 ACK 报文用来确认第三步里的 FIN 报文，进入 TIME_WAIT 状态，等待 2 个 2MSL 以后进入 CLOSED 状态。服务端收到 ACK 以后进入 CLOSED 状态。

25、为什么客户端发送最后一个确认包后还需要等待 2MSL（报文最大生存时间）时间？

1、数据报文可能在发送途中延迟但最终会到达，因此要等老的“迷路”的重复报文段在网络中过期失效，这样可以避免用相同源端口和目标端口创建新连接时收到旧连接姗姗来迟的数据包，造成数据错乱。

2、确保可靠实现 TCP 全双工终止连接。关闭连接的四次挥手中，最终的 ACK 由主动关闭方发出，如果这个 ACK 丢失，对端（被动关闭方）将重发 FIN，如果主动关闭方不维持 TIME_WAIT 直接进入 CLOSED 状态，则无法重传 ACK，被动关闭方因此不能及时可靠释放。

• 1 个 MSL 确保四次挥手中主动关闭方最后的 ACK 报文最终能达到对端
• 1 个 MSL 确保对端没有收到 ACK 重传的 FIN 报文可以到达

2MSL = 去向 ACK 消息最大存活时间（MSL) + 来向 FIN 消息的最大存活时间（MSL）

26、为什么挥手要四次，变为三次可以吗？

是有可能的。

我们知道，TCP 四次挥手里，第二次和第三次挥手之间，是有可能有数据传输的。第三次挥手的目的是为了告诉主动方：被动方没有数据要发了。

所以，在第一次挥手之后，如果被动方没有数据要发给主动方。第二和第三次挥手是有可能合并传输的。这样就出现了三次挥手。

上面提到的是没有数据要发的情况，如果第二、第三次挥手之间有数据要发，就不可能变成三次挥手了吗？

并不是。TCP 中还有个特性叫延迟确认。可以简单理解为：接收方收到数据以后不需要立刻马上回复 ACK 确认包。

在此基础上，不是每一次发送数据包都能对应收到一个 ACK 确认包，因为接收方可以合并确认。

而这个合并确认，放在四次挥手里，可以把第二次挥手、第三次挥手，以及他们之间的数据传输都合并在一起发送。因此也就出现了三次挥手。

27、简单描述一下 TCP 协议？（四个特点）

如果要用一句话来描述 TCP 协议，我想应该是：TCP 是一个可靠的（reliable）、面向连接的（connection-oriented）、基于字节流（byte-stream）、全双工的（full-duplex）协议。

面向连接：

面向连接的协议要求正式发送数据之前需要通过「握手」建立一个逻辑连接，结束通信时也是通过有序的四次挥手来断开连接。

可靠：

IP 是一种无连接、不可靠的协议：它尽最大可能将数据报从发送者传输给接收者，但并不保证包到达的顺序会与它们被传输的顺序一致，也不保证包是否重复，甚至都不保证包是否会达到接收者。

TCP 要想在 IP 基础上构建可靠的传输层协议，必须有一个复杂的机制来保障可靠性。 主要有下面几个方面：

• 对每个包提供校验和
• 包的序列号解决了接收数据的乱序、重复问题
• 超时重传
• 流量控制、拥塞控制

校验和：checksum，每个 TCP 包首部中都有两字节用来表示校验和，防止在传输过程中有损坏。如果收到一个校验和有差错的报文，TCP 不会发送任何确认直接丢弃它，等待发送端重传。

超时重传：超时重传 TCP 发送数据后会启动一个定时器，等待对端确认收到这个数据包。如果在指定的时间内没有收到 ACK 确认，就会重传数据包，然后等待更长时间，如果还没有收到就再重传，在多次重传仍然失败以后，TCP 会放弃这个包。

基于字节流：

TCP 是一种字节流协议，流的含义是没有固定的报文边界。

假设你调用 2 次 write 函数往 socket 里依次写 500 字节、800 字节。write 函数只是把字节拷贝到内核缓冲区，最终会以多少条报文发送出去是不确定的，如下图所示：

• 情况 1：分为两条报文依次发出去 500 字节 和 800 字节数据
• 情况 2：两部分数据合并为一个长度为 1300 字节的报文，一次发送
• 情况 3：第一部分的 500 字节与第二部分的 500 字节合并为一个长度为 1000 字节的报文，第二部分剩下的 300 字节单独作为一个报文发送
• 情况 4：第一部分的 400 字节单独发送，剩下100字节与第二部分的 800 字节合并为一个 900 字节的包一起发送
• 情况 N：还有更多可能的拆分组合

上面出现的情况取决于诸多因素：路径最大传输单元 MTU、发送窗口大小、拥塞窗口大小等。

当接收方从 TCP 套接字读数据时，它是没法得知对方每次写入的字节是多少的。接收端可能分2 次每次 650 字节读取，也有可能先分三次，一次 100 字节，一次 200 字节，一次 1000 字节进行读取。

全双工：

在 TCP 中发送端和接收端可以是客户端/服务端，也可以是服务器/客户端，通信的双方在任意时刻既可以是接收数据也可以是发送数据，每个方向的数据流都独立管理序列号、滑动窗口大小、MSS 等信息。

28、TCP 是如何解决网络包乱序、重复的问题的？

通过 TCP 报文的序列号保证了接收数据的乱序和重复问题。

假设我们往 TCP 套接字里写 3000 字节的数据导致 TCP发送了 3 个数据包，每个数据包大小为 1000 字节：第一个包序列号为 [11001)，第二个包序列号为 [10012001)，第三个包序号为 [2001~3001)。

假如因为网络的原因导致第二个、第三个包先到接收端，第一个包最后才到，接收端也不会因为他们到达的顺序不一致把包弄错，TCP 会根据他们的序号进行重新的排列然后把结果传递给上层应用程序。

如果 TCP 接收到重复的数据，可能的原因是超时重传了两次但这个包并没有丢失，接收端会收到两次同样的数据，它能够根据包序号丢弃重复的数据。

29、TCP 报文段中的端口号的作用是什么？

区分进程。

30、TCP 报文段中的序列号的作用是什么？

在 SYN 报文 中，序列号用于交换彼此的初始序列号，在其它报文中，序列号用于保证包的顺序。

31、TCP 中确认号的作用是什么？

告知对方下一个期望接收的序列号，小于此确认号的所有字节都已经收到。

32、TCP 协议的首部字段有哪些？

最好能够牢记下面这张图：

端口号：每个 TCP 报文段都包含源端口号和目的端口号，用于寻找发送端和接收端的应用进程，这两个端口号再加上 IP 首部的源 IP 地址和目的 IP 地址以及 TCP 协议，这五元组就确定了一个唯一的 TCP 连接。

序号：TCP 是面向字节流的协议，通过 TCP 传输的字节流的每个字节都分配了序列号，序列号（Sequence Number）指的是本报文段第一个字节的序列号。序列号是一个 32 位的无符号整数，达到 2^32 - 1 后循环到 0。

在 SYN 报文 中，序列号用于交换彼此的初始序列号，在其它报文中，序列号用于保证包的顺序。

因为网络层（IP 层）不保证包的顺序，TCP 协议可以利用序列号来解决网络包乱序、重复的问题，以保证数据包以正常的顺序组装传递给上层应用。

如果发送方发送的是四个报文，序列号分别是 1、2、3、4，但到达接收方的顺序是 2、4、3、1，接收方就可以通过序列号的大小顺序组装出原始的数据。

确认号：TCP 使用确认号（Acknowledgement number，ACK）来告知对方下一个期望接收的序列号，小于此确认号的所有字节都已经收到。

关于确认号有几个注意点：

• 不是所有的包都需要确认的
• 不是收到了数据包就立马需要确认的，可以延迟一会再确认
• ACK 包本身不需要被确认，否则就无穷无尽死循环了
• 确认号永远是表示小于此确认号的字节都已经收到

数据偏移（也叫首部长度）：部中的选项部分的长度是可变的，因此首部的长度也是可变的，所以需要这个字段来明确表示首部的长度，这个字段占 4bit，4 位的二进制数最大可以表示 15，而首部长度是以 4 个字节为一个单位的，因此首部的最大长度是 15*4 = 60 字节。

保留字段：占 6 位，未来可能有具体用途，目前默认值为 0。

TCP Flags：

• SYN（Synchronize）：用于发起连接数据包同步双方的初始序列号
• ACK（Acknowledge）：确认数据包
• RST（Reset）：这个标记用于强制断开连接，通常是之前建立的连接已经不在了、包不合法、或者实在无能为力处理
• FIN（Finish）：通知对方我发完了所有数据，准备断开连接，后面我不会再发数据给你了
• PSH（Push）：告知对方这些数据包收到以后应该马上交给上层应用，不能缓存起来

窗口大小：

可以看到用于窗口大小的 Window Size 只有 16 位，可能 TCP 协议设计者们认为 16 位的窗口大小已经够用了，也就是最大窗口大小为 65535 字节（64KB）。就像网传盖茨曾经说过：640KB 内存对于任何人都足够了一样。

自己挖的坑当然要自己填，因此 TCP 协议引入了 TCP 窗口缩放 选项作为窗口缩放的比例因子，比例因子值的范围是 0-14，其中最小值 0 表示不缩放，最大值 14。比例因子可以将窗口扩大到原来的 2 的 n 次方，比如窗口大小缩放前为 1050，缩放因子为 7，则真正的窗口大小为：1050 * 128 = 134400，如下图所示：

可选项：

常用的选项有以下几个：

MSS：最大段大小选项，是 TCP 允许的从对方接收的最大报文段
SACK：选择确认选项
Window Scale：窗口缩放选项

33、TCP 是如何保证可靠传输的？

• 对每个包提供校验和
• 包的序列号解决了接收数据的乱序、重复问题
• 超时重传
• 流量控制、拥塞控制

34、能不能说一下 TCP 的流量控制？

发送方不能无脑的发数据给接收方，要考虑接收方处理能力。如果一直无脑的发数据给对方，但对方处理不过来，那么就会导致触发重发机制，从而导致网络流量的无端的浪费。

为了解决这种现象发生，TCP 提供一种机制可以让「发送方」根据「接收方」的实际接收能力控制发送的数据量，这就是所谓的流量控制。

流量控制的底层实现机制是滑动窗口。

当发送端的滑动窗口变为 0 了，经过一段时间接收端从高负载中缓过来，可以处理更多的数据包，如果发送端不知道这个情况，它就会永远傻傻的等待了。于是乎，TCP 又设计了零窗口探测的机制（Zero window probe），用来向接收端探测，你的接收窗口变大了吗？我可以发数据了吗？

35、能不能说一下 TCP 的拥塞控制？

流量控制这种机制确实可以防止发送端向接收端过多的发送数据，但是它只关注了发送端和接收端自身的状况，而没有考虑整个网络的通信状况。于是出现了拥塞控制。

拥塞控制主要涉及到下面这几个算法：

• 慢启动（Slow Start）
• 拥塞避免（Congestion Avoidance）
• 快速重传（Fast Retransmit）和快速恢复（Fast Recovery）

为了实现上面的算法，TCP 的每条连接都有两个核心状态值：

• 拥塞窗口（Congestion Window，cwnd）
• 慢启动阈值（Slow Start Threshold，ssthresh）

拥塞窗口指的是在收到对端 ACK 之前自己还能传输的最大 MSS 段数。

它与前面介绍的接收窗口（rwnd）有什么区别呢？

• 接收窗口（rwnd）是接收端的限制，是接收端还能接收的数据量大小
• 拥塞窗口（cwnd）是发送端的限制，是发送端在还未收到对端 ACK 之前还能发送的数据量大小

拥塞窗口与前面介绍的发送窗口（Send Window）又有什么关系呢？

真正的发送窗口大小 = 「接收端接收窗口大小」 与 「发送端自己拥塞窗口大小」 两者的最小值

如果接收窗口比拥塞窗口小，表示接收端处理能力不够。如果拥塞窗口小于接收窗口，表示接收端处理能力 ok，但网络拥塞。

• 慢启动：拥塞窗口一开始是一个很小的值，然后每 RTT 时间翻倍
• 拥塞避免：当拥塞窗口达到拥塞阈值（ssthresh）时，拥塞窗口从指数增长变为线性增长
• 快速重传：发送端接收到 3 个重复 ACK 时立即进行重传，cwnd = cwnd/2、ssthresh = cwnd
• 快速恢复：当收到三次重复 ACK 时，进入快速恢复阶段，cwnd = cwnd/2、ssthresh = cwnd、cwnd = ssthresh + 3

36、能不能说一下 TCP 的重传机制？

TCP 针对数据包丢失的情况，会用重传机制解决。

常见的重传机制：

• 超时重传
• 快速重传
• SACK
• D-SACK

超时重传：重传机制的其中一个方式，就是在发送数据时，设定一个定时器，当超过指定的时间后，没有收到对方的 ACK 确认应答报文，就会重发该数据，也就是我们常说的超时重传。

快速重传：重传的时间间隔，要等几百毫秒才会进行第一次重传。聪明的网络协议设计者们想到了一种方法：「快速重传」。快速重传的含义是：当发送端收到 3 个或以上重复 ACK，就意识到之前发的包可能丢了，于是马上进行重传，不用傻傻的等到超时再重传。

SACK：为了解决不知道该重传哪些 TCP 报文，于是就有 SACK 方法。

D-SACK：Duplicate SACK 又称 D-SACK，其主要使用了 SACK 来告诉「发送方」有哪些数据被重复接收了。

37、在一个非常繁忙的服务器上，如果有大量 TIME_WAIT 状态的连接会怎么样呢？

首先要明确一点，在高并发的场景下，TIME_WAIT 连接存在，属于正常现象。

TIME_WAIT 状态存在的意义是：

• 可靠的实现 TCP 全双工的连接终止（处理最后 ACK 丢失的情况）
• 避免当前关闭连接与后续连接混淆（让旧连接的包在网络中消逝）

虽说是正常现象，但是凡事都有利弊，过多的 TIME_WAIT 状态 TCP 连接，有什么业务上的影响吗？

1、在高并发（几万 QPS）并且采用短连接方式进行交互的系统中运行一段时间后，系统中就会存在大量的 TIME_WAIT 状态，如果 TIME_WAIT 状态把系统所有可用端口都占完了且尚未被系统回收时，就会出现无法向服务端创建新的 socket 连接的情况。
每一个 TIME_WAIT 状态，都会占用一个「本地端口」，上限为 65535（16 bit）。
2、大量的 TIME_WAIT 状态也会系统一定的 fd，内存和 CPU 资源，当然这个量一般比较小，并不是主要危害。

38、TIME_WAIT 过多，其本质原因是什么？如何优化 TIME_WAIT 过多的问题？

本质原因是大量的短连接存在：

1. 比如 PHP FPM 服务连接 MySQL，当 QPS 过高时，会产生大量的 TIME_WAIT。
2. 又比如在 HTTP 请求中，Connection 被设置为了 close，此时基本会由「服务端」发起主动关闭连接，导致服务端产生大量的 TIME_WAIT。（现在的浏览器，HTTP 报文的请求头中，Connection 基本都设置为 keep-alive）

如何优化 TIME_WAIT 过多的问题？

1、使用连接池技术，减少短链接的使用；
2、如果你使用了短连接，那么可以增加服务器，让每台服务器各自承担一部分 TIME_WAIT 状态连接
3、还有好多教程说，修改 /etc/sysctl.conf 参数。

个人认为改这种参数治标不治本，不建议使用。因为 TIME_WAIT 本身是正常的状态，我们要去找到导致 TIME_WAIT 过多的原因，去优化短链接，去增加服务器数量等等。

39、TCP 的 Keepalive 和 HTTP 的 Keep-Alive 是一个东西吗？

HTTP 的 Keep-Alive 也叫 HTTP 长连接，该功能是由「应用程序」实现的，可以使得用同一个 TCP 连接来发送和接收多个 HTTP 请求/应答，减少了 HTTP 短连接带来的多次 TCP 连接建立和释放的开销。

TCP 的 Keepalive 也叫 TCP 保活机制，该功能是由「内核」实现的，当客户端和服务端长达一定时间没有进行数据交互时，内核为了确保该连接是否还有效，就会发送探测报文，来检测对方是否还在线，然后来决定是否要关闭该连接。

40、说一下滑动窗口？窗口大小由发送方决定还是接收方决定？

滑动窗口大小就是指无需等待确认应答，而可以继续发送数据的最大值，可以实现 TCP 的累计确认、流量控制的功能。

通常窗口的大小是由接收方的窗口大小来决定的。发送方发送的数据大小不能超过接收方的窗口大小，否则接收方就无法正常接收到数据。

41、TCP 流量控制和拥塞控制的区别是什么？

• 接收窗口（rwnd）是接收端的限制，是接收端还能接收的数据量大小
• 拥塞窗口（cwnd）是发送端的限制，是发送端在还未收到对端 ACK 之前还能发送的数据量大小

拥塞控制：是让网络能够承受现有的网络负荷，是一个全局性的过程，涉及所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。
流量控制：往往指点对点的通信量的控制，是个端到端的问题（接收端控制发送端），它所要做的是抑制发送端发送数据的速率，以便使接收端来及接收。

42、TCP 和 UDP 的区别？

1. TCP 面向连接；UDP 无连接。
2. 每一条 TCP 连接只能有两个端点，只能是一对一通信；UDP 支持一对一、一对多、多对一、多对多通信。
3. TCP 面向字节流；UDP 面向报文，对应用层交付的报文直接打包。
4. TCP 使用超时重传、流量控制、拥塞控制等保证可靠传输；UDP 尽最大努力交付，即不可靠传输，不使用流量控制和拥塞控制。
5. TCP 首部最小 20 字节，最大 60 字节；UDP 首部开销小，仅 8 个字节。

43、HTTP 和 HTTPS 的区别是什么？对称加密和非对称加密的区别？加密算法都有哪些？

常见的加密算法：对称加密、非对称加密、Hash 算法。

• 对称加密：加密和解密使用相同的秘钥。
• 非对称加密：加密和解密使用不同的秘钥，分别是公钥和私钥，公钥可以公开，私钥不可以公开。
• 哈希算法：通过 Hash 算法对对目标信息生成一段特定长度的唯一的 Hash 值，却不能通过这个 Hash 值重新获得目标信息。

HTTPS 协议由 HTTP 协议和 SSL 协议构建的可进行加密传输、身份认证的网络协议，比 HTTP 协议安全。防止数据在传输中被窃取、改变。

44、什么是跨域？如何解决跨域？

出于浏览器的同源策略限制，浏览器会拒绝跨域请求。

同源：如果两个页面拥有相同的协议（protocol），端口（port）和域名（domain），那么这两个页面就属于同一个源（origin）。

为什么浏览器要限制跨域访问呢？（同源策略确实能规避一些危险，不是说有了同源策略就安全，只是说同源策略是一种浏览器最基本的安全机制，毕竟能提高一点攻击的成本。其实没有刺不穿的盾，只是攻击的成本和攻击成功后获得的利益成不成正比。）

解决跨域问题的方法有哪些？

1、JSONP

使用方式就不赘述了。

优点是：兼容性好（兼容低版本 IE）

缺点是：1、JSONP 只支持 GET 请求；2、XMLHttpRequest 相对于 JSONP 有着更好的错误处理机制。

2、代理

例如 www.123.com/index.html 需要调用 www.456.com/server.php，可以写一个接口 www.123.com/server.php，由这个接口在后端去调用 www.456.com/server.php 并拿到返回值，然后再返回给 index.html，这就是一个代理的模式。相当于绕过了浏览器端，自然就不存在跨域问题。

3、CORS：后端修改响应 header

// 允许访问的来源
header('Access-Control-Allow-Origin:*');
// 允许访问的方式
header('Access-Control-Allow-Method:POST,GET');

45、DNS 协议的主要作用是什么？DNS 协议位于哪一层？DNS 用什么协议传输？

域名相比于 IP 更适合用户记忆，而 IP 更适合机器处理，DNS 协议的作用就是将主机名解析为 IP 地址。

DNS 协议位于应用层。

DNS 协议大多数情况下用 UDP 协议来进行传输。在两种情况下会使用 TCP 进行传输：

• 如果返回的响应超过 512 字节（UDP 最大只支持 512 字节的数据）
• 区域传送（区域传送是主域名服务器向辅助域名服务器传送变化的那部分数据）

DNS 是怎么查询的？

1. 浏览器拿到输入的域名后会先去浏览器的 DNS 缓存中查询是否有记录
2. 如果浏览器缓存有记录直接返回，否则去查询操作系统的缓存
3. 如果操作系统缓存中也没有记录就去查看本地的 host 文件
4. 如果本地的 host 文件也没有记录，就去本地的 DNS 服务查询
5. 如果本地的 DNS 服务也没有记录，就只能去根服务器查询了
6. 根服务器返回给本地 DNS 服务器查询域，然后本地 DNS 再次去查询
7. 本地 DNS 服务器把查询的结果返回给客户端，并且把结果缓存

46、常见的 HTTP 状态码都有哪些？301 和 302 的区别？什么情况下会出现 304 状态码？Nginx 499 状态码分析？什么情况下会出现 502 和 504？

• 200：OK，服务器已成功处理了请求
• 301：Moved Permanently，永久重定向
• 302：Found，临时重定向
• 304：Not Modified，当浏览器请求某一文件时，发现自己缓存的文件有 Last-Modified，就会在 httpRequest 里面添加消息头 If-Modified-Since 和 If-None-Match，服务器在收到 request 时，和服务器本地文件对比，如果没有更新，则仅仅返回一个响应头 Head（状态码 304，而没有响应体），客户端在收到这个响应时，就会从本地缓存加载请求的资源。
• 400：Bad Request，1、语义有误，当前请求无法被服务器理解。除非进行修改，否则客户端不应该重复提交这个请求。2、请求参数有误。
• 403：Forbidden，服务器理解客户端请求，但是拒绝处理此请求，通常是权限设置所致
• 404：Not Found，服务端没有客户端请求的资源
• 500：Internal Server Error，服务器内部错误，无法完成请求
• 502：Bad Gateway，充当网关或代理的服务器从远端服务器接收到了一个无效的请求
• 504：Gateway Time-out，充当网关或代理的服务器，未及时从远端服务器获取请求

301 和 302 的区别？

301 和 302 都是重定向，到底该用哪个？

• 301，代表永久重定向，也就是说第一次请求拿到长链接后，下次浏览器再去请求短链的话，不会向短网址服务器请求了，而是直接从浏览器的缓存里拿（前提不能设置浏览器禁用缓存 Disable cache），这样在 server 层面就无法获取到短网址的点击数了，如果这个链接刚好是某个活动的链接，也就无法分析此活动的效果。所以我们一般不采用 301。
• 302，代表临时重定向，也就是说每次去请求短链都会去请求短网址服务器（除非响应中用 Cache-Control 或 Expired 暗示浏览器缓存），这样就便于 server 统计点击数，所以虽然用 302 会给 server 增加一点压力，但在数据异常重要的今天，这点代码是值得的，所以推荐使用 302！

301 应用场景：域名到期不想继续用这个，换了个域名（永久性）
302 应用场景：做活动时候，从首页跳到活动页面（临时性）

Nginx 499 状态码分析？

当一个客户端关闭时，HTTP 不为这种情形定义代码。同时我们处理它的请求时，在一个客户端在我们尝试向其发送 HTTP 头之前关闭连接时，使用自己的代码（也就是 499 状态码）来记录这种情况。

总结一下就是：

• 499 状态码不是 HTTP 的标准代码
• 499 状态码是 Nginx 自己定义，用来 记录（你没看错，就是记录一下） 服务端向客户端发送 HTTP 请求头之前，客户端已经关闭连接的一种情况
• 最常见的场景就是 timeout 设置不合理，Nginx 把请求转发上游服务器，上游服务器慢吞吞的处理，客户端等不及了主动断开链接，Nginx 就负责记录了 499

记录 499 的情形：

• 有些接口确实慢：比如涉及到了慢 SQL 的问题，所以我们只需要将接口进行优化，优化至小于客户端可以等待的最长时间（最好是 500 毫秒以内）。所以如果客户端设置了超时时间，就会导致 499 问题，如果客户端没有设置超时时间，很有可能会导致 502 问题。
• Nginx 拦截导致：当两次请求 post 请求过快，间隔时间较短的话，Nginx 就会认为是不安全的连接，主动拒绝了客户端的连接。这种情况呢，我们就不让 nginx 关闭就可以了。设置 proxy_ignore_client_abort on; # 让代理服务端不要主动关闭客户端的连接。

什么情况下会出现 502 和 504？

502：

• Nginx 无法与 php-fpm 进行连接：php-fpm 没有启动，Nginx 无法将请求交给 php-fpm
• Nginx 在连接 php-fpm 一段时间后发现与 php-fpm 的连接被断开：php-fpm 运行脚本超时，php-fpm 终止了脚本的执行和执行脚本的 worker 进程，Nginx 发现自己与 php-fpm 的连接断开。

504：

504 即 Nginx 超过了自己设置的超时时间，不等待 php-fpm 的返回结果，直接给客户端返回 504 错误。但是此时 php-fpm 依然还在处理请求（在没有超出自己的超时时间的情况下）。

47、单机最多可以支撑多少 TCP 连接？

如何标识一个 TCP 连接？

系统用一个五元组来标识一个连接：服务器 IP + 服务器端口 + 协议（TCP / UDP） + 客户端 IP + 客户端端口。

端口号在 TCP、UDP 协议中占两个字节，意味着一台机器一共有 2^16 = 65536 个端口号可用。

当该机器作为 Client 时：

Client 在每次发起 TCP 连接请求时，通常会让系统选取一个空闲的本地端口（除非指定绑定哪个端口），端口 0 有特殊含义，所以如果机器作为 Client，理论上最多支持 65535 个 TCP 连接。

但是直到 Kernel4.2 版本，一个新的 socket option IP_BIND_ADDRESS_NO_PORT 的引入，上面最多支持 65535 的这个问题才得以解决。（解决的思路就是复用本地的端口）

当该机器作为 Server 时：

本机器的 IP、Port、协议（TCP）都确定了，因此在五元组中只剩下 Remote IP（也就是 Client IP）和 Remote Port（客户端 Port）是可变的，所以对于 IPV4，最大的 TCP 连接数约为 2 的 32 次方（IP 数）乘以 2 的 16 次方（Port 数），即约为 2^48。

但是上面的 2^48 只是理论上的单机最大连接数，在实际环境中最大连接数远不能达到理论上限，限制连接数的主要因素是内存和允许的文件描述符个数（每个 TCP 连接都要占用一定的内存，每个 TCP 连接都要占用一个 socket）。

对 Server 端，通过增加内存、修改最大文件描述符个数等参数，单机最大并发 TCP 连接数超过 10W 是没问题的，国外 Urban Airship 公司在产品环境中已做到 50W 并发。

48、如何解决 TCP 粘包问题？

粘包这个说法已经被诟病很久了，既然坊间流传这个说法咱们就沿用吧，关于这个问题比较准确的解释可以参考下面几点：

1. TCP 是字节流传输协议，是一种面向连接的、可靠的、基于字节流的传输层通信协议
2. TCP 没有包的概念，它只负责传输字节序列，所以不存在拆包粘包问题
3. 应该由应用层来维护消息和消息的边界，即需要一个应用层协议，比如 HTTP

所以，本质上这是一个没有正确使用 TCP 协议的而产生的问题。

通常来说，一般有下面几种方式解决：

1. 消息长度固定，提前确定包长度，读取的时候也安固定长度读取，适合定长消息包。
2. 使用特殊的字符或字符串作为消息的边界，例如 HTTP 协议的 header 以 \r\n 为字段的分隔符
3. 自定义协议，将消息分为消息头和消息体，消息头中包含表示消息总长度

49、HTTP 是无状态的协议，这里的无状态怎么理解？

HTTP 是无状态协议，是指协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息，则它必须重传，这样可能导致每次连接传送的数据量增大。另一方面，在服务器不需要先前信息时它的应答就较快。

50、建立 socket 都需要哪些步骤？

什么是 socket 呢？我们经常把 socket 翻译为套接字，socket 是在应用层和传输层之间的一个抽象层，它把复杂的 TCP/IP 协议族隐藏在 socket 接口后面，我们所说的 TCP/IP 协议是在操作系统内核实现的，而 socket 就是操作系统内核提供给应用层的一系列接口，它把 TCP/IP 层复杂的操作抽象为几个简单的接口供应用层调用已实现进程在网络中通信。

以使用 TCP 协议通信的 socket 为例，其交互流程大概是这样子的：

1. 服务端创建一个 socket、绑定地址、端口
2. 服务端阻塞，直到有客户端连接
3. 客户端创建一个 socket，向服务端发起连接
4. 服务端收到客户端连接请求，针对该连接创建一个新的 socket，这个新的 socket 和客户端的 socket 用于后面的数据传输
5. 客户端和服务端通过这一对 socket 进行数据传输

51、浏览器从输入 url 开始，到展示网页都经历了什么？

52、HTTP1.0、HTTP1.1、HTTP2.0 的区别？

HTTP1.1 相比于 HTTP1.0 的改进

HTTP1.0

client 的每次 HTTP 请求都需要和 server 建立一个 TCP 连接，server 响应完成断开 TCP 连接，这样无法复用 TCP 连接。

HTTP1.1

1. HTTP1.1 默认支持持久连接（增加了请求头 Connection: keep-alive），即一个 TCP 连接上可以传送多个 HTTP 请求和响应，从而复用 TCP 连接。
2. 增加管道机制（pipelining）。一个网页中含有多张图片，这多张图片可以基于一个 TCP 连接。HTTP1.1 允许 client 可以同时发送多个请求，无须等待上次请求的返回结果，但 server 必须按照 client 的请求顺序依次返回响应结果。
3. 增加 Host 请求头。比如 www.baidu.com 的 Host 是 www.baidu.com，xueshu.baidu.com 的 Host 是 xueshu.baidu.com。

HTTP2.0 相比于 HTTP1.1 的改进

1. 采用二进制格式而非文本格式。
2. 多路复用：在一个 TCP 连接里，client 和 server 都可以同时发送多个请求和响应，而且不用按照顺序一一对应。
3. 首部压缩
4. 服务端推送：服务端推送是一种在客户端请求之前发送数据的机制，当代网页使用了许多资源：HTML、样式表、脚本、图片等等，在 HTTP/1.x 中这些资源每一个都必须明确地请求，这可能是一个很慢的过程, 浏览器从获取 HTML 开始，然后在它解析和评估页面的时候，增量地获取更多的资源。

53、什么场景下用 UDP，为什么不用 TCP？

实时视频直播、手游等适合用 UDP，因为：

1. 直播、游戏的场景可以容忍视频卡顿、掉帧，而且 UDP 没有拥塞控制不会使源主机的发送速率降低（对实时应用很有用，如直播、实时视频会议等）
2. UDP 开销更小（UDP 的数据报相比于 TCP 的报文结构更小、而且 UDP 不需要建立连接的开销）

54、TCP 和 UDP 可以同时监听相同的端口吗？

我们可以在同一个端口上同时拥有 UDP 和 TCP 请求，因为每个请求都由源 IP，目标 IP，源端口，目标端口，PROTOCOL（协议可以是 TCP 或 UDP）所包含的五元组来标识。

所以只要协议不同，即使端口相同，操作系统有能力根据接受的 IP 数据包里面的 Protocol 字段判断这个报文是什么报文（是 TCP 还是 UDP）。

55、什么是半连接队列和全连接队列？

下面一图足以说明：

55、你管这破玩意儿叫 TCP？

• TCP 如何知道将数据包交给哪个进程？（传输层头部会封装源端口号和目的端口号）
• TCP 是如何防止丢包的？（1、A 怎么知道包丢了？答案：让 B 告诉 A，即 ACK 机制。2、丢了的包怎么办？答案：重传。）
• 什么是停止等待协议？（A 每发一个包，都必须收到来自 B 的确认，即 ACK，再发下一个包，否则在一定时间内没有收到确认，就重传这个包）
• 什么是可靠交付？（按照停止等待协议，A 给 B 发送数据包，虽然 A 无法保证 B 一定能收到数据包，但 A 能够确认 B 是否收到了包，收不到就重试，尽最大努力让这个通信变得可靠）
• 如何解决停止等待协议导致的效率过慢问题？（流水线方式，批量传包）
• 流水线方式导致了包的发送顺序和接收顺序无法保证一致，TCP 是怎么保证包的有序性的？（A 在发送的数据包中增加一个序号 seq，同时 B 在 ACK 包上增加一个确认号 ack，这样不但解决了停止等待协议的效率问题，也通过这样标序号的方式解决了顺序问题）
• 什么是累计确认或者累计应答？（比如 B 发了一个确认号为 ack = 3，它不仅仅代表 A 发送的序号为 2 的包收到了，还表示 2 之前的数据包都收到了）
• A 发送的数据包太快，而 B 的接收能力不足怎么办呢？（B 在每次发送数据包给 A 时，顺带传过来一个值，叫窗口大小，win，这个值就代表 B 的接收能力，同理，每次 A 给 B 发包时也带上自己的窗口大小，表示 A 的接收能力）
• B 告诉了 A 自己的窗口大小，A 怎么利用它去做 A 这边的发包的流量控制呢？（滑动窗口）
• 有的时候，不是 B 的接收能力不足，而是网络不太好，造成了网络拥塞怎么办？（拥塞控制：通过设置一定的窗口大小）
• A 怎么确定自己的拥塞窗口大小呢？（通过试探，不断地感知网络环境的好坏，进而确定自己的拥塞窗口大小）
• 拥塞控制和流量控制的区别是什么？（流量控制是受 B 的接收能力影响，而拥塞控制是受网络环境的影响）
• TCP 如何建立连接？（三次握手，需要详细描述过程）
• TCP 如何断开连接？（四次挥手，需要详细描述过程）
• 什么是 TCP 协议？（面向连接的、可靠的、基于字节流的传输层通信协议）
• 什么叫做基于字节流呢？（TCP 在建立连接时，需要告诉对方 MSS，即最大报文段大小，如果要发送的数据很大，在 TCP 层是需要按照 MSS 来切割成一个个的 TCP 报文段的，在切割的时候 TCP 不管原来的数据表示什么意思，把原来的数据当作一串毫无意义的字节，在想要切割的地方咔嚓来上一刀，然后标上序号，只要接收方再根据这个序号拼成最终想要的完整数据就行了）

传送门：leetcode-141 环形链表。

思路：

设置两个链表指针 fast、slow，初始值都指向链表头结点，然后两个指针都往后走，不同的是 slow 每次前进一步，即前进一个节点。fast 每次前进两步，如果存在环，两个指针必定相遇。

实现：

<?php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */

class Solution
{
    /**
     * @param ListNode $head
     * @return Boolean
     */
    function hasCycle($head)
    {
        $slow = $head;
        $fast = $head;

        while ($fast !== null && $fast->next !== null) {
            $fast = $fast->next->next;
            $slow = $slow->next;

            if ($fast === $slow) {
                return true;
            }
        }

        return false;
    }
}

传送门：leecode - 102 二叉树的层序遍历。

思路：和二叉树的最大深度中的 BFS 思路类似。

实现：

class Solution 
{
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) 
    {
        if ($root === null) return [];

        $curr = $root;
        $queue = [];
        array_push($queue, $curr);
        $res = [];

        while (!empty($queue)) {
            $tmpRes = [];
            $len = count($queue);

            while ($len > 0) {
                $node = array_shift($queue);
                $tmpRes[] = $node->val;

                if ($node->left !== null) {
                    array_push($queue, $node->left);
                }
                if ($node->right !== null) {
                    array_push($queue, $node->right);
                }
                $len--;
            }

            $res[] = $tmpRes;
        }

        return $res;
    }
}

传送门：剑指 Offer 24 - 反转链表。

思路：

迭代：考虑遍历链表，并在访问各节点时修改 next 引用指向。

复杂度分析：

• 时间复杂度 O(N)： 遍历链表使用线性大小时间。
• 空间复杂度 O(1)： 变量 prev 和 curr 使用常数大小额外空间。

实现：

class Solution
{
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head)
    {
        $curr = $head;
        $prev = null;
        while ($curr !== null) {
            $tmp = $curr->next;
            $curr->next = $prev;
            $prev = $curr;
            $curr = $tmp;
        }
        return $prev;
    }
}

先来看下栈和队列的数据结构特点：

传送门：剑指 Offer 09-用两个栈实现队列。

题目描述：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。（若队列中没有元素，deleteHead 操作返回 -1）

解析：

维护两个栈 stackIn 和 stackOut，其中 stackIn 负责入队操作，stackOut 负责出队操作。

如何入队？只要有新数据，就压入 stackIn。
如何出队？

• 如果 stackIn 和 stackOut 都为空，返回 -1。
• 如果 stackOut 为空，将 stackIn 所有数据压入 stackOut，弹出 stackOut 的栈顶并返回。
• 如果 stackOut 不为空，弹出 stackOut 的栈顶并返回。

代码实现：

<?php

class CQueue 
{
    // 入队栈
    private $stackIn;
    // 出队栈
    private $stackOut;
    
    function __construct() 
    {
        $this->stackIn = new SplStack();
        $this->stackOut = new SplStack();
    }

    /**
     * @param Integer $value
     * @return NULL
     */
    function appendTail($value) 
    {
        $this->stackIn->push($value);
    }

    /**
     * @return Integer
     */
    function deleteHead() 
    {
        if ($this->stackIn->isEmpty() && $this->stackOut->isEmpty()) {
            return -1;
        }
        if ($this->stackOut->isEmpty()) {
            while (!$this->stackIn->isEmpty()) {
                $this->stackOut->push($this->stackIn->pop());
            }
        }
        return $this->stackOut->pop();
    }
}

传送门：剑指 Offer 55 - II 平衡二叉树。

思路：

构造一个获取当前子树的深度的函数 maxDepth(root)，通过比较某子树的左右子树的深度差 abs($this->maxDepth($root->left) - $this->maxDepth($root->right)) <= 1 是否成立，来判断某子树是否是二叉平衡树。若所有子树都平衡，则此树平衡。

• abs($this->maxDepth($root->left) - $this->maxDepth($root->right)) <= 1：判断当前子树是否是平衡树；
• $this->isBalanced($root->left)： 先序遍历递归，判断当前子树的左子树是否是平衡树；
• $this->isBalanced($root->right)： 先序遍历递归，判断当前子树的右子树是否是平衡树；

实现：

class Solution 
{
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isBalanced($root) 
    {
        if ($root === null) return true;
        // 1、判断当前子树是否是平衡树；2、判断当前子树的左子树是否是平衡树；3、判断当前子树的右子树是否是平衡树；
        return abs($this->maxDepth($root->left) - $this->maxDepth($root->right)) <= 1 && $this->isBalanced($root->left) && $this->isBalanced($root->right);
    }

    function maxDepth($root)
    {
        if ($root === null) return 0;
        $leftMaxDepth = $this->maxDepth($root->left);
        $rightMaxDepth = $this->maxDepth($root->right);
        return max($leftMaxDepth, $rightMaxDepth) + 1;
    }
}

传送门：剑指 Offer 10 - II 青蛙跳台阶问题。

思路：

设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

• 当为 1 级台阶： 剩 n-1 个台阶，此情况共有 f(n-1) 种跳法；
• 当为 2 级台阶： 剩 n-2 个台阶，此情况共有 f(n-2) 种跳法。

f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，以上递推性质为斐波那契数列。本题可转化为求斐波那契数列第 n 项的值，与斐波那契数列等价，唯一的不同在于起始数字不同。

• 青蛙跳台阶问题： f(0)=1，f(1)=1，f(2)=2；
• 斐波那契数列问题： f(0)=0，f(1)=1，f(2)=1。

实现：

class Solution
{
    // 使用数组存储已经计算的结果，避免重复计算
    private $map = [];

    /**
     * @param Integer $n
     * @return Integer
     */
    function numWays($n)
    {
        if ($n === 0) return 1;

        if (isset($this->map[$n])) {
            return $this->map[$n];
        }
        if ($n <= 2) {
            $this->map[$n] = $n;
            return $n;
        }
        $this->map[$n] = $this->numWays($n - 1) + $this->numWays($n - 2);
        return $this->map[$n] % 1000000007;
    }
}

传送门：剑指 Offer 53 - I 在排序数组中查找数字 I。

思路：先通过二分查找找到下标，然后尝试往左、往右遍历，累加相等的次数。

实现：

class Solution
{
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function search($nums, $target)
    {
        $index = $this->binarySearch($nums, $target);
        if ($index === -1) {
            return 0;
        }
        $count = 0;
        // 往左遍历
        for ($i = $index; $i >= 0; $i--) {
            if ($nums[$i] != $target) break;
            if ($nums[$i] === $target) {
                $count++;
            }
        }
        // 往右遍历
        for ($i = $index + 1; $i < count($nums); $i++) {
            if ($nums[$i] != $target) break;
            if ($nums[$i] === $target) {
                $count++;
            }
        }
        return $count;
    }

    /**
     * 二分查找
     *
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function binarySearch($nums, $target)
    {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = floor(($left + $right) / 2);
            if ($nums[$mid] === $target) {
                return $mid;
            } elseif ($nums[$mid] > $target) {
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        }
        return -1;
    }
}

传送门：剑指 Offer 18 - 删除链表的节点。

思路：

实现：

class Solution
{
    /**
     * @param ListNode $head
     * @param Integer $val
     * @return ListNode
     */
    function deleteNode($head, $val)
    {
        if ($head->val === $val) {
            return $head->next;
        }
        $curr = $head;
        while ($curr) {
            if ($curr->val === $val) {
                $prev->next = $curr->next;
                return $head;
            }
            $prev = $curr;
            $curr = $curr->next;
        }
    }
}

传送门：剑指 Offer 10 - I 斐波那契数列。

实现：

class Solution 
{
    // 使用数组存储已经计算的结果，避免重复计算
    private $map = [];

    /**
     * @param Integer $n
     * @return Integer
     */
    function fib($n)
    {
        if (isset($this->map[$n])) {
            return $this->map[$n];
        }

        if ($n <= 1) {
            $this->map[$n] = $n;
            return $n;
        }
        $this->map[$n] = $this->fib($n - 1) + $this->fib($n - 2);
        return $this->map[$n] % 1000000007;
    }
}

传送门：leecode - 94 二叉树的中序遍历。

递归法：

class Solution
{
    private $list = [];

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root)
    {
        if ($root === null) return [];
        $this->inorderTraversal($root->left);
        $this->list[] = $root->val;
        $this->inorderTraversal($root->right);
        return $this->list;
    }
}

迭代法：

class Solution
{
    private $stack = [];
    private $list = [];

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root)
    {
        if ($root === null) return [];

        $curr = $root;

        while ($curr !== null || !empty($this->stack)) {
            // 不断往左子树方向走，每走一次就将当前节点保存到栈中
            while ($curr !== null) {
                array_push($this->stack, $curr);
                $curr = $curr->left;
            }
            $node = array_pop($this->stack);
            $this->list[] = $node->val;
            if ($node->right !== null) {
                $curr = $node->right;
            }
        }

        return $this->list;
    }
}

36 匹马分 6 个组，分别为 A、B、C、D、E、F 组。

第一轮，每个组各跑一次，取每组前三名，标识为 A1、A2、A3，B1、B2、B3，以此类推。

第二轮，每个组的第一名（A1~F1）拉出来跑一次，假设名次是：A1 第一名，B1 第二名，C1 第三名。

那么：

• 后三名及其所在组的其余组员均被淘汰（小组头名都没能进前三，当然是全部淘汰啦）
• 两轮全胜的 A1 已经提前夺冠了
• 由于 C1 的最好成绩也只能是第三名了，所以 C2、C3 也可以淘汰了

第三轮，A2、A3、B1、B2、B3、C1 六匹马跑，取前两名。

其中第一轮跑 6 次，第二轮第三轮都各只跑 1 次，一共 8 次。

前言：来自知乎的一道面试题。

传送门：剑指 Offer 53 - II 0～n-1 中缺失的数字。

思路：

排序数组中的搜索问题，首先想到二分法解决。

实现：

class Solution 
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function missingNumber($nums)
    {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = intval(floor(($left + $right) / 2));
            if ($nums[$mid] === $mid) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return $left;
    }
}

传送门：剑指 Offer 52 - 两个链表的第一个公共节点。

思路：剑指 Offer 52 - 两个链表的第一个公共节点（双指针，清晰图解）。

实现：

public class Solution 
{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) 
    {
        ListNode A = headA;
        ListNode B = headB;

        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        
        return A;
    }
}

传送门：leecode - 144 二叉树的前序遍历。

递归法：

class Solution
{
    private $list = [];

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function preorderTraversal($root)
    {
        if ($root === null) return [];
        $this->list[] = $root->val;
        $this->preorderTraversal($root->left);
        $this->preorderTraversal($root->right);
        return $this->list;
    }
}

公式如下：

前序遍历的递推公式：preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

要理解递归的思路并且熟练的使用它，就是要想清楚你想做什么，什么时候停止。我们并不需要太过于在意具体的递归过程，而是要想清楚让计算机干什么。计算机都可能溢出，用人脑去遍历就不现实了。

迭代法：

• 初始化栈，并将根节点入栈；
• 当栈不为空时：
  • 弹出栈顶元素 node，并将值添加到结果中；
  • 如果 node 的右子树非空，将右子树入栈；
  • 如果 node 的左子树非空，将左子树入栈；
  • 由于栈是先进后出的顺序，所以入栈时先将右子树入栈，这样使得前序遍历结果为根->左->右的顺序。

class Solution
{
    private $stack = [];

    private $list = [];

    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function preorderTraversal($root)
    {
        if ($root === null) return [];

        array_push($this->stack, $root);

        while (!empty($this->stack)) {
            $node = array_pop($this->stack);
            $this->list[] = $node->val;

            if ($node->right !== null) {
                array_push($this->stack, $node->right);
            }
            if ($node->left !== null) {
                array_push($this->stack, $node->left);
            }
        }

        return $this->list;
    }
}

传送门：两数之和。

暴力法：

function twoSum($nums, $target) {
    $len = count($nums);

    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            if ($nums[$i] + $nums[$j] === $target) {
                return [$i, $j];
            }
        }
    }
}

Map 法：

function twoSum($nums, $target) {
    $map = [];

    $len = count($nums);

    for ($i = 0; $i < $len; $i++) {
        // 当前数字和目标和的差值
        $diff = $target - $nums[$i];

        if (isset($map[$diff])) {
            return [$map[$diff], $i];
        }
        $map[$nums[$i]] = $i;
    }
}

传送门：剑指 Offer 03 - 数组中重复的数字。

思路 1：哈希表法。

class Solution
{
    function findRepeatNumber($nums) 
    {
        $map = [];

        foreach ($nums as $k => $v) {
            if (isset($map[$v])) {
                return $v;
            }
            $map[$v] = $v;
        }
    }
}

思路 2：原地交换。

题目说明尚未被充分使用，即 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义：数组元素的索引 和值是一对多的关系。
因此，可遍历数组并通过交换操作，使元素的索引与值一一对应（即 nums[i] = i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

class Solution
{
    function findRepeatNumber($nums)
    {
        $len = count($nums);
        $i = 0;
        while ($i < $len) {
            if ($nums[$i] === $i) {
                $i++;
                continue;
            }
            if ($nums[$nums[$i]] === $nums[$i]) {
                return $nums[$i];
            }

            // 交换
            $tmp = $nums[$nums[$i]];
            $nums[$nums[$i]] = $nums[$i];
            $nums[$i] = $tmp;
        }
    }
}

传送门：leetcode - 231 2 的幂。

方法 1：暴力法。

/**
 * @param Integer $n
 * @return Boolean
 */
function isPowerOfTwo($n) {
    if ($n === 1) return true;

    $res = 1;

    while ($res <= $n) {
        $res *= 2;
        if ($res === $n) return true;
    }

    return false;
}

方法 2：位运算法。

/**
 * @param Integer $n
 * @return Boolean
 */
function isPowerOfTwo($n) {
    return $n > 0 && ($n & ($n - 1)) === 0;
}

传送门：剑指 Offer 30 - 包含 min 函数的栈。

思路：

普通栈的 push() 和 pop() 函数的复杂度为 O(1)；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)。

本题难点： 将 min() 函数复杂度降为 O(1)，可通过建立辅助栈实现；

• 数据栈 A：栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
• 辅助栈 B ： 栈 B 中存储栈 A 中所有非严格降序的元素，则栈 A 中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 B 的栈顶元素即可。

因此，只需设法维护好栈 B 的元素，使其保持非严格降序，即可实现 min() 函数的 O(1) 复杂度。

实现：

<?php

class MinStack
{
    private $stack;
    private $help;

    /**
    * initialize your data structure here.
    */
    function __construct()
    {
        $this->stack = new SplStack();
        $this->help = new SplStack();
    }

    /**
    * @param Integer $x
    * @return NULL
    */
    function push($x)
    {
        $this->stack->push($x);
        if ($this->help->isEmpty() || $this->help->top() >= $x) {
            $this->help->push($x);
        }
    }

    /**
    * @return NULL
    */
    function pop()
    {
        if ($this->stack->isEmpty()) return;
        $element = $this->stack->pop();
        if ($element === $this->help->top()) {
            $this->help->pop();
        }
    }

    /**
    * @return Integer
    */
    function top()
    {
        return $this->stack->top();
    }

    /**
    * @return Integer
    */
    function min()
    {
        return $this->help->top();
    }
}

传送门：剑指 Offer 11 - 旋转数组的最小数字。

思路 1：暴力法。

class Solution 
{
    /**
     * @param Integer[] $numbers
     * @return Integer
     */
    function minArray($numbers) 
    {
        $min = $numbers[0];
        for ($i = 1; $i < count($numbers); $i++) {
            if ($numbers[$i] < $min) {
                return $numbers[$i];
            }
        }
        return $min;
    }
}

思路 2：二分法。

如下图所示，寻找旋转数组的最小元素即为寻找右排序数组的首个元素 nums[x]，称 x 为 旋转点 。

排序数组的查找问题首先考虑使用二分法解决，其可将遍历法的线性级别时间复杂度降低至对数级别 。

算法流程：

• 初始化： 声明 i, j 双指针分别指向 nums 数组左右两端；
• 循环二分： 设 m = (i + j) / 2 为每次二分的中点（ "/" 代表向下取整除法，因此恒有 i≤m<j ），可分为以下三种情况：
  • 当 nums[m] > nums[j] 时：m 一定在左排序数组中，即旋转点 x 一定在 [m + 1, j] 闭区间内，因此执行 i = m + 1；
  • 当 nums[m] < nums[j] 时： m 一定在右排序数组中，即旋转点 x 一定在[i, m] 闭区间内，因此执行 j = m；
  • 当 nums[m] = nums[j] 时： 无法判断 m 在哪个排序数组中，即无法判断旋转点 x 在 [i,m] 还是 [m + 1, j] 区间中。解决方案：执行 j = j - 1 缩小判断范围。
• 返回值： 当 i = j 时跳出二分循环，并返回旋转点的值 nums[i] 即可。

class Solution
{
    /**
     * @param Integer[] $numbers
     * @return Integer
     */
    function minArray($numbers)
    {
        $left = 0;
        $right = count($numbers) - 1;

        while ($left < $right) {
            $mid = floor(($left + $right) / 2);
            if ($numbers[$mid] > $numbers[$right]) {
                $left = $mid + 1;
            } elseif ($numbers[$mid] < $numbers[$right]) {
                $right = $mid;
            } else {
                $right--;
            }
        }

        return $numbers[$left];
    }
}

传送门：剑指 Offer 05 - 替换空格。

class Solution
{
    /**
     * @param String $s
     * @return String
     */
    function replaceSpace($s)
    {
        return implode('%20', explode(' ', $s));
    }
}

传送门：leetcode-876 链表的中间结点。

思路：用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

实现：

<?php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function middleNode($head)
    {
        $fast = $head;
        $slow = $head;

        while ($fast !== null && $fast->next !== null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
        }

        return $slow;
    }
}