一、数组

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。且数组内存空间连续。

数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效

1. 问题：大多数编程语言，数组下标为什么从 0 开始？

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k * type_size

但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：a[k]_address = base_address + (k-1)*type_size

对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

一、广度优先遍搜索

（Breadth-First-Search）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// 使用邻接表作为基础存储结构
class Graph {
private:
    int n;
    std::vector<std::list<int>> abj;
public:
    Graph(int count) : n(count), abj(count, std::list<int>()) {}
    void addNode(int left, int right) {
        abj[left].push_back(right);
        abj[right].push_back(left);
    }
    void bfs(int start, int end) {
        if (start == end) return;
        std::queue<int> qu;
        qu.push(start);
        std::vector<bool> visited(n, false);
        visited[start] = true; 
        std::vector<int> prev(n, -1);
        while (!qu.empty()) {
            int tmp = qu.front();
            qu.pop();
            for (auto x = abj[tmp].begin(); x != abj[tmp].end(); x++) {
                if (!visited[*x]) {
                    prev[*x] = tmp;
                    if ((*x) == end) {
                        print(prev, start, end);
                        return;
                    }
                    visited[*x] = true;
                    qu.push(*x);
                }
            }
        }
    }
private: 
    void print(std::vector<int>& prev, int start, int end) {
        if (prev[end] != -1 && start != end) {
            print(prev, start, prev[end]);
        }
        std::cout << end << " ";
    }
};

• visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q]会被设置为 true。

一、贪心

贪心算法解决问题的步骤

1. 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
2. 每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
3. 举几个例子看下贪心算法产生的结果是否是最优的。

贪心算法

贪心算法是一种在每一步选择中都采取在“当前状态“下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法

贪心和动态规划的区别：
贪心算法和动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规则则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能

贪心：当下做局部最优判断
回溯：能够回退
动态规划：最优判断+回退

应用场景：贪心法可以解决一些最优花的问题，如：求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案
一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及所求得得答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别明确的问题。

适用于贪心算法的场景：问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。

递归算法

python 代码模版

1
2
3
4
5
6
7
8
9
10
11
12
13

def recursion(level, param1, param2, ...):
    # recursion terminator
    if level > MAX_LEVEL:
        process_result
        return
    
    # process logic in current level
    process(level, data...)

    # drill down
    self.recursion(level+1, p1, ...)

    # reverse the current level status if needed

注意点

初级搜索

1. 朴素搜索
2. 优化方式：不重复(fibonacci)、剪枝(生成括号问题)
3. 搜索方向：DFS、BFS

跳表

跳表的查询时间复杂度是 logn

空间复杂度是 n 。假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，依次类推。这种每两个节点抽出一个索引，空间复杂度是 O(n)。如果每三个节点抽出一个索引，就是 O(n/2)

一、跳表索引动态更新

如果两个索引之间的节点过多，就会出现跳表退化成单链表的情况；跳表是通过随机函数来维护前面提到的“平衡性”。

当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢？

我们通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值 K，那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。

1. 后端服务器设计的时候，后端服务不应该保存客户端的状态。要考虑到服务端发送连接给客户端了，此时服务端挂了，服务端此时就不知道此连接的信息是否发送成功。导致出现问题。

go sync.pool 的实现
https://www.cyhone.com/articles/think-in-sync-pool/#:~:text=sync.Pool%20%E6%98%AFGolang%20%E5%86%85%E7%BD%AE,%E5%88%9B%E5%BB%BA%E7%9A%84%20gin.Context%20%E5%AF%B9%E8%B1%A1%E3%80%82

https://younghz.github.io/%E9%AB%98%E5%B9%B6%E5%8F%91%E7%B3%BB%E7%BB%9F%E7%BC%93%E5%AD%98%E8%AE%BE%E8%AE%A1

高并发系统缓存设计

核心问题：如何同时满足高时效性和数据准确性

• 为什么有些对数据实时性，准确性要求极高的系统，不能使用缓存？
  答：数据实时性，准确性要求极高的系统 ， 举个例子的话，就想到了银行的存取款系统，这系统如果使用读缓存， 用户会疯掉。 因为钱转过来了却需要一段时间以后看到，如果使用写缓存，银行会疯掉，因为多存储的不一致性会让很多数据丢失。所以对于实时性准确性要求极高的系统，无论访问量多大，最多采用排队的异步方式，而不能使用缓存提高效率