一、codetest1

4.3约笔试，两道题，一道考察算法，一道考察深度学习框架，两小时，线下做。

二、codetest2

手写代码，检测链表中是否有环，这个比较简单，和leetcode的一个题目是一样的，因为我写得太快了，就被加了点难度，如果一个链表中有环，那么判断哪个节点是环的进入节点。

方法一：哈希表

思路及算法

最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

复杂度分析

• 时间复杂度：O(N)O(N)，其中 NN 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

• 空间复杂度：O(N)O(N)，其中 NN 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

方法二：快慢指针

思路及算法

本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
细节

• 为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head（即与「乌龟」和「兔子」中的叙述相同）？
  观察下面的代码，我们使用的是 while 循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行。因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，这样我们就可以使用 while 循环了。

• 当然，我们也可以使用 do-while 循环。此时，我们就可以把快慢指针的初始值都置为 head。

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        
        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        
        return True

复杂度分析

• 时间复杂度：O(N)O(N)，其中 NN 是链表中的节点数。
  当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
  当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 NN 轮。
• 空间复杂度：O(1)O(1)。我们只使用了两个指针的额外空间。

手写代码，判断一个无序数组中，最长的连续相同的元素个数，这个也挺简单的，就是注意一下跳出的时候最后一次有没有进行比较就行了，面试官说看你思路清晰，经常刷题吧，勉强算你过了吧。

三、codetest3

题目1：
A为一个十进制数（以整数为例），k位，k<100。求B使得B为大于A的最小整数，且A各位的和等于B各位的和。

---

题目2：
给一定数量的信封，带有整数对 (w, h) 分别代表信封宽度和高度。一个信封的宽高均大于另一个信封时可以放下另一个信封。求最大的信封嵌套层数。
样例
给一些信封 [[5,4],[6,4],[6,7],[2,3]] ，最大的信封嵌套层数是 3([2,3] => [5,4] => [6,7])。

---

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

前言

image.png

动态规划

image.png

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) {
            return 0;
        }
        
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        });

        vector<int> f(n, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (envelopes[j][1] < envelopes[i][1]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        return *max_element(f.begin(), f.end());
    }
};

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        f = [1] * n
        for i in range(n):
            for j in range(i):
                if envelopes[j][1] < envelopes[i][1]:
                    f[i] = max(f[i], f[j] + 1)
        
        return max(f)

复杂度分析

• 时间复杂度：O(n^2)，其中 nn 是数组 \textit{envelopes}envelopes 的长度，排序需要的时间复杂度为O(nlogn)，动态规划需要的时间复杂度为 O(n^2)O，前者在渐近意义下小于后者，可以忽略。
• 空间复杂度：O(n)O(n)，即为数组 ff 需要的空间。

基于二分查找的动态规划

image.png

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) {
            return 0;
        }
        
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        });

        vector<int> f = {envelopes[0][1]};
        for (int i = 1; i < n; ++i) {
            if (int num = envelopes[i][1]; num > f.back()) {
                f.push_back(num);
            }
            else {
                auto it = lower_bound(f.begin(), f.end(), num);
                *it = num;
            }
        }
        return f.size();
    }
};

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        f = [envelopes[0][1]]
        for i in range(1, n):
            if (num := envelopes[i][1]) > f[-1]:
                f.append(num)
            else:
                index = bisect.bisect_left(f, num)
                f[index] = num
        
        return len(f)

复杂度分析

• 时间复杂度：O(nlogn)，其中 nn 是数组 \textit{envelopes}envelopes 的长度，排序需要的时间复杂度为O(nlogn)，动态规划需要的时间复杂度同样为 O(nlogn)。

• 空间复杂度：O(n)，即为数组 ff 需要的空间。

from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        size = len(envelopes)
        #print(envelopes)
        if size < 2:  # if the size of envelopes is smaller than 2, return
            return size
        envelopes.sort(key=lambda x: x[0])  # sort the envelopes according the width
        dp = [1 for _ in range(size)]  #record the number of envelope layers
        #print(dp)
        for i in range(1, size):
            for j in range(i):
                # compare the width and length of envelopes
                if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

if __name__ == '__main__':
    envelopes = [[5,4],[6,4],[6,7],[2,3],[99,100]]  #input the matrix of envelopes
    solution = Solution()
    res = solution.maxEnvelopes(envelopes)
    print("The maximum envelope nesting layer is %d" %(res))

四、codetest4

反向部分链表元素（LeetCode中等难度；仅可通过常规的链表指针操作实现、仅可遍历一次、不可通过交换链表指向的值来完成）。
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

前言

链表的操作问题，一般而言面试（机试）的时候不允许我们修改节点的值，而只能修改节点的指向操作。思路通常都不难，写对链表问题的技巧是：一定要先想清楚思路，并且必要的时候在草稿纸上画图，理清「穿针引线」的先后步骤，然后再编码。

方法一：穿针引线

我们以下图中黄色区域的链表反转为例。

image.png

使用「206. 反转链表」的解法，反转 left 到 right 部分以后，再拼接起来。我们还需要记录 left 的前一个节点，和 right 的后一个节点。如图所示：

image.png

算法步骤：

• 先将待反转的区域反转；

• 把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。

  
  image.png
  

  说明：编码细节我们不在题解中介绍了，请见下方代码。思路想明白以后，编码不是一件很难的事情。这里要提醒大家的是，链接什么时候切断，什么时候补上去，先后顺序一定要想清楚，如果想不清楚，可以在纸上模拟，让思路清晰。

class Solution {
private:
    void reverseLinkedList(ListNode *head) {
        // 也可以使用递归反转一个链表
        ListNode *pre = nullptr;
        ListNode *cur = head;

        while (cur != nullptr) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
    }

public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;

        ListNode *pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode *rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode->next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode *leftNode = pre->next;
        ListNode *curr = rightNode->next;

        // 注意：切断链接
        pre->next = nullptr;
        rightNode->next = nullptr;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre->next = rightNode;
        leftNode->next = curr;
        return dummyNode->next;
    }
};

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        def reverse_linked_list(head: ListNode):
            # 也可以使用递归反转一个链表
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next

        # 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        # 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        # 建议写在 for 循环里，语义清晰
        for _ in range(left - 1):
            pre = pre.next

        # 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        right_node = pre
        for _ in range(right - left + 1):
            right_node = right_node.next
        # 第 3 步：切断出一个子链表（截取链表）
        left_node = pre.next
        curr = right_node.next

        # 注意：切断链接
        pre.next = None
        right_node.next = None

        # 第 4 步：同第 206 题，反转链表的子区间
        reverse_linked_list(left_node)
        # 第 5 步：接回到原来的链表中
        pre.next = right_node
        left_node.next = curr
        return dummy_node.next

复杂度分析

• 时间复杂度：O(N)O(N)，其中 NN 是链表总节点数。最坏情况下，需要遍历整个链表。
• 空间复杂度：O(1)O(1)。只使用到常数个变量。

方法二：一次遍历「穿针引线」反转链表（头插法）

方法一的缺点是：如果 left 和 right 的区域很大，恰好是链表的头节点和尾节点时，找到 left 和 right 需要遍历一次，反转它们之间的链表还需要遍历一次，虽然总的时间复杂度为 O(N)O(N)，但遍历了链表 22 次，可不可以只遍历一次呢？答案是可以的。我们依然画图进行说明。
我们依然以方法一的示例为例进行说明。

image.png

整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

image.png
下面我们具体解释如何实现。使用三个指针变量 pre、curr、next 来记录反转的过程中需要的变量，它们的意义如下：

• curr：指向待反转区域的第一个节点 left；
• next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
• pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

第 1 步，我们使用 ①、②、③ 标注「穿针引线」的步骤。

image.png

操作步骤：

• 先将 curr 的下一个节点记录为 next；
• 执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
• 执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
• 执行操作 ③：把 pre 的下一个节点指向 next。
  第 1 步完成以后「拉直」的效果如下：
  image.png
  第 2 步，同理。同样需要注意 「穿针引线」操作的先后顺序。
  image.png
  第 2 步完成以后「拉直」的效果如下：
  image.png
  第 3 步，同理。
  image.png
  第 3 步完成以后「拉直」的效果如下：
  image.png

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummyNode->next;
    }
};

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # 设置 dummyNode 是这一类问题的一般做法
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        for _ in range(left - 1):
            pre = pre.next

        cur = pre.next
        for _ in range(right - left):
            next = cur.next
            cur.next = next.next
            next.next = pre.next
            pre.next = next
        return dummy_node.next

复杂度分析：

• 时间复杂度：O(N)O(N)，其中 NN 是链表总节点数。最多只遍历了链表一次，就完成了反转。
• 空间复杂度：O(1)O(1)。只使用到常数个变量。

五、codetest5

卷积加速

1、常规for循环

这样会引入串行for循环逐一像素进行操作，然后在每一个窗口大小的矩阵上进行卷积运算，效率太低。下面扩展到3通道卷积操作，利用numpy切片同时计算3个通道。

def convolve2d(arr, kernel, stride=1, padding='same'):
    '''
    Using convolution kernel to smooth image

    Parameters
    ===========
    arr: 3D array or 3-channel image
    kernel: Filter matrix
    stride: Stride of scanning
    padding: padding mode
    '''
    h, w, channel = arr.shape
    k = kernel.shape[0]
    r = int(k/2)
    kernel_r = np.rot90(kernel,k=2,axes=(0,1))
    # padding outer area with 0
    padding_arr = np.zeros([h+k-1,w+k-1,channel])
    padding_arr[r:h+r,r:w+r] = arr 
    new_arr = np.zeros(arr.shape)
    for i in range(r,h+r,stride):
        for j in range(r,w+r,stride): 
            roi = padding_arr[i-r:i+r+1,j-r:j+r+1]
            new_arr[i-r,j-r] = np.sum(np.sum(roi*kernel_r,axis=0),axis=0)
    return new_arr[::stride,::stride]


if __name__=='__main__':
    A = np.arange(1,10001).reshape((100,100,1))
    print(A.shape)
    kernel = np.arange(1,10).reshape((3,3,1))/45
    # convert to 3-channels
    A3 = np.concatenate((A, 2*A, 3*A), axis=-1)
    k3 = np.concatenate((kernel, kernel, kernel), axis=-1)

    t1 = time.time()
    for i in range(100):
        A1 = convolve2d(A3,kernel,stride=2).astype(np.int)
    t2 = time.time()
    print(t2-t1)

###output
(100, 100, 1)
3.2025175

虽然不用循环计算多个通道，单通道与多通道耗时相同，但是依然需要for循环来滑动窗口kernel，对于大图片速度很慢，需要进一步将外层循环替代。

向量化索引运算

image.png

def convolve2d_vector(arr, kernel, stride=1, padding='same'):
    h, w, channel = arr.shape[0],arr.shape[1],arr.shape[2]
    k = kernel.shape[0]
    r = int(k/2)
    kernel_r = np.rot90(kernel,k=2,axes=(0,1))
    # padding outer area with 0
    padding_arr = np.zeros([h+k-1,w+k-1,channel])
    padding_arr[r:h+r,r:w+r] = arr 
    new_arr = np.zeros(arr.shape)

    vector = np.array(list(itertools.product(np.arange(r,h+r,stride),np.arange(r,w+r,stride))))
    vi = vector[:,0]
    vj = vector[:,1]  
    def _convolution(vi,vj):
        roi = padding_arr[vi-r:vi+r+1,vj-r:vj+r+1]
        new_arr[vi-r,vj-r] = np.sum(np.sum(roi*kernel_r,axis=0),axis=0)
    vfunc = np.vectorize(_convolution)    
    vfunc(vi,vj)
    return new_arr[::stride,::stride]

看来简单地使用 np.vectorize(）并没有实现向量化展开，必须对原图的存储结构进行重新排列和扩展才能真正地利用向量化机制，即将窗口滑动转换为真正的矩阵运算。

矩阵乘法运算

正常的三通道卷积

image.png

转换为矩阵相乘，对kernel和原图进行重新排列：

image.png
将卷积运算转化为矩阵乘法，从乘法和加法的运算次数上看没什么差别，但是转化成矩阵后，可以在连续内存和缓存上操作，而且有很多库提供了高效的实现方法（BLAS、MKL），numpy内部基于MKL实现运算的加速。图像展开消耗了更多的内存，以空间换时间，另一方面，展开成矩阵形式可以转换成CUDA代码使用GPU加速。
image.png

上图展示了3通道卷积的展开过程，RGB通道首位拼接，矩阵乘法运算后的结果是三个通道卷积结果的累加，这里有所不同，我们需要单独输出每个通道的卷积结果而不累加，与原图像大小相同，见下图。

image.png
二维矩阵乘法采用np.dot()函数，而高维数组乘法运算采用np.matmul()函数。高维数组（n>2）相乘须满足以下两个条件：

两个n维数组的前n-2维必须完全相同。例如（3,2,4,2）（3,2,2,3）前两维必须完全一致；
最后两维必须满足二阶矩阵乘法要求。例如（3,2,4,2）（3,2,2,3）的后两维可视为（4,2）x（2,3）满足矩阵乘法。
先利用reshape将kernel展开为(1,k*k,c)，再用转置函数transpose将channel前置，照此方法循环展开image矩阵。numpy的广播规则会将kernel的第一个维度补齐，所以输入kernel可以是1通道的（三通道共用一个卷积核）。

def convolve2d_vector(arr, kernel, stride=1, padding='same'):
    h, w, channel = arr.shape[0],arr.shape[1],arr.shape[2]
    k, n = kernel.shape[0], kernel.shape[2]
    r = int(k/2)
    #重新排列kernel为左乘矩阵，通道channel前置以便利用高维数组的矩阵乘法
    matrix_l = kernel.reshape((1,k*k,n)).transpose((2,0,1))
    padding_arr = np.zeros([h+k-1,w+k-1,channel])
    padding_arr[r:h+r,r:w+r] = arr
    #重新排列image为右乘矩阵，通道channel前置
    matrix_r = np.zeros((channel,k*k,h*w))
    for i in range(r,h+r,stride):
        for j in range(r,w+r,stride): 
            roi = padding_arr[i-r:i+r+1,j-r:j+r+1].reshape((k*k,1,channel)).transpose((2,0,1))
            matrix_r[:,:,(i-r)*w+j-r:(i-r)*w+j-r+1] = roi[:,::-1,:]        
    result = np.matmul(matrix_l, matrix_r)
    out = result.reshape((channel,h,w)).transpose((1,2,0))
    return out[::stride,::stride]

if __name__=='__main__':
    N=1000
    A = np.arange(1,N**2+1).reshape((N,N,1))
    print(A.shape)
    kernel = np.arange(3**2).reshape((3,3,1))/45
    # convert to 3-channels
    A3 = np.concatenate((A, 2*A, 3*A), axis=-1)
    k3 = np.concatenate((kernel, kernel, kernel), axis=-1)

    t1 = time.time()
    for i in range(1):
        B1 = convolve2d(A,kernel,stride=2).astype(np.int)
    t2 = time.time()
    print(t2-t1)

    t1 = time.time()
    for i in range(1):
        B2 = convolve2d_vector(A,kernel,stride=2).astype(np.int)
    t2 = time.time()
    print(t2-t1)
    print(B1.all()==B2.all())

###output
(1000, 1000, 1)
4.517540216445923
0.8763346672058105
True

可以看到运算结果与convolve2d滑动卷积的结果一致，且速度提升了5倍左右。速度主要瓶颈还是来自image的展开操作，这里还是滑动窗口扫描实现的，for循环内部进行了局部拷贝操作，是串行的，数组切片和矩阵运算部分是并行的。

总结

在CPU程序上优化卷积运算，numpy库是个不错的选择，初始算法将三通道计算和求和过程并行化，获得了接近3倍的加速。转换为矩阵/多维数组乘法后，速度进一步提升了5倍。在python中用多线程和多进程的方式加速for循环效果并不理想，CPU程序上创建和启动多线程开销很大，进程和线程通信、传递数据消耗了大部分时间，总体速度不升反降。

六、codetest6 sigmoid 反向传播

class Network(object):
...
   def backprop(self, x, y):
        """Return a tuple "(nabla_b, nabla_w)" representing the
        gradient for the cost function C_x.  "nabla_b" and
        "nabla_w" are layer-by-layer lists of numpy arrays, similar
        to "self.biases" and "self.weights"."""
        nabla_b = [np.zeros(b.shape) for b in self.biases]
        nabla_w = [np.zeros(w.shape) for w in self.weights]
        # feedforward
        activation = x
        activations = [x] # list to store all the activations, layer by layer
        zs = [] # list to store all the z vectors, layer by layer
        for b, w in zip(self.biases, self.weights):
            z = np.dot(w, activation)+b
            zs.append(z)
            activation = sigmoid(z)
            activations.append(activation)
        # backward pass
        delta = self.cost_derivative(activations[-1], y) * \
            sigmoid_prime(zs[-1])
        nabla_b[-1] = delta
        nabla_w[-1] = np.dot(delta, activations[-2].transpose())
        # Note that the variable l in the loop below is used a little
        # differently to the notation in Chapter 2 of the book.  Here,
        # l = 1 means the last layer of neurons, l = 2 is the
        # second-last layer, and so on.  It's a renumbering of the
        # scheme in the book, used here to take advantage of the fact
        # that Python can use negative indices in lists.
        for l in xrange(2, self.num_layers):
            z = zs[-l]
            sp = sigmoid_prime(z)
            delta = np.dot(self.weights[-l+1].transpose(), delta) * sp
            nabla_b[-l] = delta
            nabla_w[-l] = np.dot(delta, activations[-l-1].transpose())
        return (nabla_b, nabla_w)

...

    def cost_derivative(self, output_activations, y):
        """Return the vector of partial derivatives \partial C_x /
        \partial a for the output activations."""
        return (output_activations-y) 

def sigmoid(z):
    """The sigmoid function."""
    return 1.0/(1.0+np.exp(-z))

def sigmoid_prime(z):
    """Derivative of the sigmoid function."""
    return sigmoid(z)*(1-sigmoid(z))

https://zhuanlan.zhihu.com/p/78713744
https://zhuanlan.zhihu.com/p/260109670