Neo's Blog

链表，作为一种最简单的数据组织方式，在平常工作中用处非常广泛。

关于链表，你一定要知道的

链表的常见技巧

1. 链表中的哨兵节点
2. 快慢指针
3. 基于递归的反转问题

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
43
44
45
46
47
48
49

//单链表 —— 模板题 AcWing 826. 单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

//双链表 —— 模板题 AcWing 827. 双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

链表相关的经典题目

数组，作为一种最简单的数据组织方式，在平常工作中用处非常广泛。

关于数组你一定要知道的

数组的常见技巧

• 自Hash

本质：把数组当作hash

给出的数组中每个元素的范围都是 [1, n]，并且要求的空间复杂度是$O(1)$

可以考虑：原地修改数组又叫自Hash，其本质上就是把数组当作hash

修改方法：取反，总之需要有办法来识别打了标记的元素

对元素打标记时，打的标记需尽量保存信息(对相反数取绝对值，就能够还原原始内容），不可影响问题的求解。

• 原地交换

还有另外一种技巧，我们称之为原地交换，其基本要求在于：

每一个元素都需要有对应的坑位，如果我们在他对应的坑位上的话，就进行swap；如此往复

1）检查某一个元素是否在他期望出现的位置上

2）如果在了，就啥也不做

3）如果不在，就与目标位置上的元素进行替换（替换之后，新的元素又不满足了，那我们就继续）

数组相关的经典题目

Pattern: Cyclic Sort 循环排序

参考：
https://blog.csdn.net/weixin_43989102/article/details/111397072

bloom Filter 布隆过滤器
K个hash函数，当写入一个key的时候，设置H1(key), H2(key)…Hk(key)为1。当需要check key是否存在的时候，依次检测H1(key)…Hk(key)是否均为1，如果其中一个不为1，则表示key不存在；否则认为key存在。

注意：有错误判断的可能性，所以仅仅适用于允许一定错误率的场景。

应用：

1. 爬虫程序url是否处理过
2. 黑名单,垃圾邮件过滤
3. 是否关注、判断用户关系（如果出现误判，顶多会多回源一次数据库）
4. 【TODO，没看明白】Bloom filter在重复数据删除中的应用。主流的重复数据删除技术的基本原理是对文件进行定长或变长分块，然后利用hash函数计算数据块指纹，如果两个数据块指纹相同则认为是重复数据块（同样这里存在数据碰撞问题），只保存一个数据块副本即可，其他相同数据块使用该副本索引号表示，从而实现数据缩减存储空间并提高存储效率。

hash实现

开放定址法：适合数据量小，装载因子小的场景

拉链法：适合存储大对象、大数据量的散列表，更加灵活，有更多的优化策略

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

一般哈希 —— 模板题 AcWing 840. 模拟散列表
(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

hash使用场景

• RPC负载均衡
• 数据分片，分布式存储，例如一致性hash

特殊hash

1. 自hash， 用数组自身作为hash的container；
2. 位图
3. 布隆过滤器，多hash
4. 地理坐标hash， geo hash，二维转一维。

相关题目

10亿url按照计数排序

思路：

hash统计次数，然后单机排序、或者多机器归并排序

找出字符数组中只出现三次，且最早出现完三次的字符（eg：aabcbba输出b）

思路：

hashmap

数据结构实现

Hashmap是用hash算法实现的，我们通过put一个key和value进行存储，用get（key）来获取，在传入key时，hashmap会根据key.hashCode（）计算出hash值存储到bucket里面，当发生hash值相同，也就是hash冲突时，会使用链表+红黑树存储相同的hash值的value，如果冲突少，就用链表，冲突多，就用红黑树

Hashmap扩容：

·HashMap 初始化大小是 16 ，扩容因子默认0.75（可以指定初始化大小，和扩容因子）
·存的对象负载因子0.75（默认）大于总量就要扩容，扩容是键值重新排布，重新对底层数组容量取余分布
·JDK1.8之前是数组+链表结构、JDK1.8及之后是数组+链表+红黑树
·HashMap集合可以存储null键和null值

java数据结构对比

hashMap 数组 + 链表 （冲突链表过长时，转为红黑树）线程不安全 允许null\null 不可以有序遍历

hashTable 线程安全，通过synchronized 不允许null\null 不可以有序遍历

treeMap 红黑树 线程不安全 可以有序遍历

unsorted_hash

比特位计数 - 题目描述

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

比特位计数 - 代码实现

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

class Solution {
public:
    /*
    int lowbit(int n) {
        return n & (~n);
    }
    */
    vector<int> countBits(int num) {
        vector<int> dp(num + 1);
        for (int i = 1; i <= num; ++i) {
            dp[i] = dp[i & i - 1] + 1; //每次n&n-1会抹掉最后一个1
        }

        return dp;
    }
};

缺失的第一个正数 - 题目描述

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

缺失的第一个正数 - 总体思路

本地交换法不太容易想到，所以该题目定级为困难。题目让我们找缺失的第一个正数？

我们不妨做一下逆向思考，假设一个正数都不缺失呢？我们会得到什么？ 一般情况下，我们的元素下标与元素的值会一一对应，从1到N。

所以，我们考虑尝试着把一个元素i都找到他对应的位置i上，如果位置i被占了，我也强制把位置i的元素移走，重复整个过程。

缺失的第一个正数 - 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        //1~N
        //一定可以为i找到一个合适的坑；
       for (int i = 1; i <= n; ++i) {
           int x = nums[i - 1];
            while (x >= 1 && x <= n && x != nums[x - 1]) {
                swap(nums[x - 1], nums[i - 1]);
                x = nums[i - 1];
            }
       }

       for (int i = 1; i <= n; ++i) {
           if (nums[i - 1] != i) {
               return i;
           }
       }

       return n + 1;
    }
};

逆序第m～n个元素

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* successor;

    //非递归实现
    ListNode* reverseN(ListNode* head, int n) {
        ListNode* pre = NULL;
        auto cur = head;
        while (cur && n > 0) {
            auto next = cur->next; //记录下一个cur
            cur->next = pre; //核心步骤---操作cur的next指针，让其指向pre；
            pre = cur;  //记录前一个
            cur = next; //给下一个cur赋值
            n--;
        }

        head->next = cur;
        return pre;
    }

    ListNode* reverseN(ListNode* head, int n) {
        if (!head) return head;
        //base 
        if (n == 1) {
            successor = head->next; //这一步特别关键，记录当前元素的后继节点，则外面会使用。
            return head;
        }

        //子问题-下一个节点
        auto x = reverseN(head->next, n - 1);
        //head->next 是递归之前的头，也就是递归之后的尾巴
        (head->next)->next = head;
        head->next = successor;
        return x;
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //base
        if (m == 1) {
            return reverseN(head, n);
        }

        auto x = reverseBetween(head->next, m - 1, n - 1);
        head->next = x;
        return head; //返回的是头
    }
};

每K个反转一次，剩余不到k个，不用反转。

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head, ListNode* tail) {
        if (head == tail) return head;

        auto x = reverse(head->next, tail);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head) return head;

        auto p = head;
        ListNode* pre = NULL;
        for (int i = 0; i < k; ++i) { 
            //base 不足k个
            if (!p) return head;
            pre = p;
            p = p->next;
        }

        //反转
        reverse(head, pre);

        auto x = reverseKGroup(p, k);
        head->next = x;
        return pre;
    }
};

支持最大值的队列 - 题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

1 <= push_back,pop_front,max_value的总操作数 <= 10000

1 <= value <= 10^5

支持最大值的队列-实现思路

首先，默写下普通队列的模版：

1
2
3
4
5
6
7
8
9

int q[N];
int hh = 0;
int tt = -1;
//push
q[++tt] = x;
//pop
q[hh++];
//is empty
hh > tt;

其次，默写下单调队列的模版：

1
2
3
4
5

for (int i = 0; i < n; ++i) {
    while (tt >= hh && check_out(q[hh])) hh++; //判断是否滑出窗口
    while (tt >= hh && check(q[tt])) tt--;
    q[++tt] = i;
}

最后为什么会想到单调队列？

一句话：如果一个后入队的元素比我还大，那么我永无出头之日！

支持最大值的队列-代码实现

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
43
44
45

 class MaxQueue {
public:
    MaxQueue() {
        memset(q, 0, sizeof(q));
        hh = 0;
        tt = -1;
    }
    
    int max_value() {
        if (dq.size()) return q[dq.front()];
        else return -1;
    }
    
    void push_back(int value) {
        q[++tt] = value;
        //if (dq.size() && value >= q[dq.front()]) dq.clear();
        while (dq.size() && value > q[dq.back()]) dq.pop_back();
        dq.push_back(tt);
    }
    
    int pop_front() {
       if (tt < hh) return -1;

       //当前的hh
       if (dq.size() && dq.front() == hh) {
           dq.pop_front();
       }

       return q[hh++];
    }

private:
    int q[10010];
    int hh; //队头
    int tt; //队尾
    std::deque<int> dq;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

什么是熵？(Entropy)

熵，代表了一个系统的混乱程度。一个系统越混乱，其熵越大。一个封闭系统的熵随着时间推移，会一直变大，且不可逆。

什么是信息熵？(Information Entropy)

一条信息的信息量大小和它的不确定性有直接的关系。不确定性越大，其信息量越大。我们用信息熵被用来计算信息量，其计算公式如下：
H(x) = -∑p(xi)log(p(xi)) (i=1,2,..n) （其中p(x)是x事件出现的概率），信息熵的单位是bit。

获得了新的信息后，不确定性减少，信息熵降低。

问题的解空间与信息熵的关系

这里提一个很重要的概念：问题的解空间。什么是问题的解空间呢？所有可能成为问题最优解的解所构成的空间。问题的解空间越大，不确定性就越大，问题就“越混乱”，熵也就越高。

计算机求解问题的过程是怎样的呢？计算机算法在执行的过程中，获取更多信息，将要解决的问题的信息熵减小，直到减到0，该问题就被解决了。

每一个问题都有一个固有的初始信息熵，这个初始信息熵的大小也就决定了这个问题的复杂程度。例如，N皇后这个问题就比“从N个数中找到最大值”问题更难，因为前者的解空间更大，有更多的可能性。

不同的算法为什么执行时间差别那么大？

同一个问题，有不同的解法，也就会产生不同的解空间。

一开始的时候，要解决的问题信息熵很大，不确定性就越大。从信息熵的角度来看，就是把这个问题的熵将为0的过程。
什么是问题的求解呢？
计算机算法是如何获取新的信息的呢？ 信息获取的越快，
举个例子，从N个数中找到某一个数这个问题。一开始这个问题有N种可能性，
搜索空间就是你算法的自变量构成的空间，而求解问题的解空间是你问题的解构成的空间。所以当你算法的自变量范围和求解问题的解范围相同时，这两个空间就是相同的。但是在很多时候，它们并不相同。这是因为求解的问题往往存在约束。大多数情况下，我们在处理约束时，都是采用惩罚函数的方式。这相当于我们把求解问题对解的约束放在了目标函数上。由此，变相地放大了自变量的空间，也就是算法的搜索空间。

让我们结合几个例子来

常见问题的解空间有多大

子集问题
$2^k$

组合问题

排列问题
n!

参考文章：
https://stonema.github.io/2018/03/27/大话交叉熵/

一条信息的信息量大小和它的不确定性有直接的关系。比如说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，我们不需要太多的信息就能把它搞清楚。所以，从这个角度，我们可以认为，信息量的度量就等于不确定性的多少。（摘自数学之美）

香浓指出的信息熵的计算公式如下（本文的对数一律以2为准）

H(x) = -∑p(xi)log(p(xi)) (i=1,2,..n) （其中p(x)是x事件出现的概率）单位为bit
算法时间复杂度，与信息熵

数学之美里是用赛后怎么知道32个球队里谁是冠军来讲解了这个信息熵的概念。

当概率相等时，每次询问用折半查找的原理（如“冠军队伍在1-16吗？”）可以减少一半的队伍，这样就需要5次就能知道结果了。这里就是log32 = 5

而使用信息熵计算信息量，的确也是5。但是为什么信息熵这个公式会代表信息量呢

按我的理解，在等概率事件里，1/p(x) 代表那一次所有可能出现的量、在球队问题里，就是32种可能性。

而等概率事件里，因∑p（xi） = 1，所以信息熵可以看成

信息熵H(x)= -∑p(xi)log(p(xi)) (i=1,2,..n) = -log(p(i)) = -（- log（1/p(x)））= log（1/p(x)）

也就是说等概率事件里的信息量可以看成

H（x）= log（所有可能性）

为了加深对信息量的定义的理解，再回到上述32个球队的问题，我们已经知道他的信息量是5Bit

问过一次之后，我们可以知道冠军在哪16个队伍中，也就是说我们获得了1bit的信息后不确定性减少，等于信息熵变成了log16 = 4bit =5bit -1bit

而最大熵模型呢？它的原理就是保留全部的不确定性，将风险降到最少。

最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。我们常说，“不要把所有的鸡蛋放在一个篮子里”，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。

也就是说发现不确定信息的时候，不要对不确定的产物任何主观假设使他们的概率分布均匀，则能获得最客观的结果。而这时风险会最小，我们就可以用这个结果来进行最客观的决策。数学上来说貌似就是最优下界吧。这种策略的本质可以概括成“让未知世界无机可乘”。它是没有“弱点的”，答案的任何一个分支都是等概率的。反之，一旦某个分支蕴含的可能性更多，当情况落到那个分支上的时候你就郁闷了。二分搜索为什么好，就是因为它每次都将可能性排除一半并且无论如何都能排除一半（它是最糟情况下表现最好的）。（摘自mindhacks快排为什么那么快）

我再用算法的时间复杂度说明一下最大熵原理吧，用几个主流的算法对n个数据进行排序时间复杂度基本上都是从O（nlogn）到O（n2）。而一般情况下为什么O（nlogn）最优呢，因为n个数据的先后顺序是随机的，我们可以看做不确定性相等，则可以用最大熵原理获得最优(最稳定)结果。则信息熵则为

H(x)= log（所有可能性）= log（n！） 而n—>00 则log（n！）近似于lognn= nlogn

假设我们每次能获得1bit数据，就至少需要获得（nlogn）bit数据才能取消信息的不确定性，也就是要比较nlogn次。但因为各种排序算法策略不同，我们不可能每次都能获得1bit数据，所以按照信息熵的定义这是理论上最优的结果。而最佳的排序算法就是要每次获得1bit数据，越接近于1则越有效。

而TopLanguage那个帖子里也说了，虽然快排和堆排序两个是都是时间复杂度O（nlogn）的算法,但是快速排序一般都会比堆排序快，就是因为堆排序每次获取的平均信息量比快排来的低。

而上面，我们根本没提到具体算法，就算到了最优的时间复杂度。在实际生活中很多时候我们虽然不会想到具体的策略，但我们至少可以知道极限在哪里，可以知道还有没有提高余地。任何排序和猜数字的算法可以理解为通过获得信息量去消减原来的熵。（这句摘自eric的话）

什么叫状态空间树？

就是问题的解空间树，分为子集树和排列树

当所给的问题是从n个元素的集合S中找到S满足某种性质的子集时，相应的解空间树称为子集树。

当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。

子集树和排列树的不同是每一步的选择策略不同。子集树每一步对应的是对应的元素的选择或不选择，排列树每一步对应的是剩下的元素选择其中一个。一个的可搜索的解为2**n，一个为n！，因此，一个高效的回溯法算法必须依赖于剪枝函数来避免无效搜索。

面对许多实际问题时，需要求解满足特定条件的全部解或最优解，如著名的N皇后问题和旅行售货员问题。
此类问题，一般没有特定的计算规则用于解题，通常我们采用试探性的方法，在包含问题所有可能解的解空间树中，将所有可能的结果搜索一遍，从而获得我们期望的那一个解，或者是那一些解，一般就是满足一定条件的最优解，或是全部解。那么这里用到的解空间树是什么呢？

解空间树：
依据待解问题的特性，用树结构表示问题的解结构，用叶子表示所有问题所有可能解的一棵树。

解空间树的建立：
就是将问题求解的一系列判断决策过程及各种可能的结果用树型结构呈现。
事实上，我们解题的过程是一个不断判断决策的过程，我们把每一步判断决策的过程对应于解空间树的一个分支结点，而各种可能的不同结果，则对应得到结点的每一个孩子及各棵子树，而一系列判断决策的解题过程，就对应着解空间树的生长过程；而问题最终所有可能的解，都会呈现在这棵解空间树的叶子上。

让我们先思考下我们之前做过的算法题都有哪些种类？

解空间树T

回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。它们在问题的解空间树T上搜索的方法不同，适合解决的问题也就不同。一般情况下，回溯法的求解目标是找出T中满足约束条件的所有解的方案，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。相对而言，分支限界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。

发现当考虑了所有的操作时，还要对操作所得状态进行判断，是否已出现过，来避免重复搜索。这道题我纠结了好久，就是因为我想通过限制操作来避免出现重复状态，而出现重复状态的情况有很多，很难考虑全面。其实判断状态是否重复我之前也都做过，就是在搜索迷宫的过程中，操作就是移动的方向，而状态就是位置，为了避免重复搜索就在地图上做标记，当时这样做的时候觉得顺理成章，不过在这题里，却并没有能直接这样做。
总结下，在搜索整个解空间时，首先是考虑所有的 操作，然后通过保存已出现 状态，来防止重复搜索。如果很容易通过对操作进行限制来防止状态的重复出现，或是保存状态所需的内存空间过大的话，那就不宜保存状态。

a computational problem is a problem that a computer might be able to solve or a question that a computer may be able to answer.
A computational problem can be viewed as an infinite collection of instances together with a, possibly empty, set of solutions for every instance. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n.

A decision problem is a computational problem where the answer for every instance is either yes or no.

In a search problem, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.

决策问题，给定一个正整数n，确定n是否是素数。

搜索问题，找到一个正整数的所有非朴素因子。

A counting problem asks for the number of solutions to a given search problem. For example, a counting problem associated with factoring is

“Given a positive integer n, count the number of nontrivial prime factors of n.”

An optimization problem asks for finding a “best possible” solution among the set of all possible solutions to a search problem.

求这n个实数在数轴上相邻2个数之间的最大差值，

In a function problem a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem, that is, it isn’t just “yes” or “no”. One of the most famous examples is the traveling salesman problem:

“Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city.”
It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.

我们要解决一个

当不确定性降到了0，问题就解决了。

信息：

熵：

高熵特征，低熵特征

熵增定律

多做一步的目的是为了减少更多的不确定性。