Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In Valine:

Longest Consecutive Sequence 求最长连续序列, $O(n)$复杂度

解题思路：

  1. hash来记录是否使用过，以某个元素为中心，向两侧扩展
  2. 带size的并查集
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
class Solution {
public:
    unordered_map<int,int> father_map;//节点-父节点
    unordered_map<int,int> child_count;// 节点-子节点个数
    int longestConsecutive(vector<int>& nums) {
        int res = 1;
        if( nums.size() == 0) return 0;
        for(int i = 0;i < nums.size();i++)
        {
            father_map[nums[i]] = nums[i];
            child_count[nums[i]] = 1;
        }
        for(int i = 0;i < nums.size();i++)
        {
             if( father_map.find(nums[i]+1) != father_map.end())
             {
                 res = max (res,mergexy(nums[i],nums[i]+1));
             }
        }
        return res;
    }
    int getfather(int i)
    {
        if( father_map[i] == i)
        {
            return i;
        }
        else
        {
            father_map[i] = getfather(father_map[i]);
            return father_map[i] ;
        }
    }
    int mergexy(int x,int y)
    {
        x = getfather(x);
        y = getfather(y);
        if( x == y )
        {
            return child_count[x];
        }
        else
        {
            father_map[y] = x; 
            child_count[x] +=child_count[y];
            return child_count[x];
        }
    }
};

Posted on In Valine:

跳表是一种随机化数据结构，

其随机化体现在插入元素的时候元素所占有的层数完全是随机的，层数是通过随机算法(随机化思想)产生的。

改变索引构建策略，有效平衡执行效率与内存消耗

使用场景：

  1. Redis ZSET实现
  2. LevelDB选用SkipList来实现memory table

参考：https://segmentfault.com/a/1190000020596941

Posted on In Valine:

并查集是一个代码很简单、但技巧性极强的数据结构，我们需要知道并查集的最重要特性：

能够在近乎$O(1)$的时间复杂度内完成元素归属集合以及元素合并的操作。

通常我们利用数组来实现并查集，并经常会通过路径压缩技巧来进行性能优化。

我们在图的连通性判定、最小生成树-kraskal等问题中可以看到常规并查集的应用。另外，我们有时候需要额外维护size、distance等额外属性去解决更多的问题。这种技巧也需要掌握。

将多个集合合并成没有交集的集合

给定一个字符串的集合，格式如：{aaa， bbb，ccc}，{bbb，aaa,ddd}，{eeefff}，{ggg}，{dddhhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaabbbcccdddhhh}，{eeefff}，{ggg}。
（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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
并查集 —— 模板题 AcWing 836. 合并集合, AcWing 837. 连通块中点的数量
(1)朴素并查集：

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);


(2)维护size的并查集：

int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

Posted on In Valine:

SplayTree，一种二叉查询树，与红黑树类似，是一种自调整的二叉树，

但是调整过程不仅仅发生在插入和删除，SplayTree中对节点访问都是通过splay操作完成节点的定位，查询、插入都是通过splay操作得到节点位置，每个splay操作都将进行对节点进行调整，将目标节点调整至树根，频繁访问的节点，调整到离根近的位置上，加快查询速度，反之“冷”节点的查询会耗时多。

按照8-2原则，假如程序80%的查询量中，频繁被查询到的数据仅仅是总数据的20%，那么将数据放入SplayTree中提供查询，对“热”数据的查询会大大加速，这样子会大大降低这80%查询量所需要的时间。

事物总有其缺陷的一面，SplayTree也是如此，倘若访问“冷”节点，这时的代价可能是O(n)，但是对于“热”节点，甚至可以达到O(1)。

Squid中SplayTree应用于ACL，所谓ACL即访问控制列表，用户通过配置文件配置的ACL元素(例如：http_accessacl1,acl2,acl3，这里的acl1，acl2，acl3就是acl元素)，在内存中使用两种方式组织，一种是SplayTree，另一种是链表。采用的SplayTree组织ACL的种类有：DSTIP、SRCIP、用户认证、DSTDOMAIN等，原因很简单，这些元素访问非常频繁，假如元素很多时，链表查询的代价是O(n)，让这些类型ACL元素放入SplayTree中，那么查询时间就是可以做到O(log(n))，甚至是O

理论依据：局部性原理

参考：
http://blog.csdn.net/yykxx/article/details/8679017

Posted on In Valine:

Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。

Merkle Tree

Posted on Edited on In Valine:

heap

red-black

更加平衡，没有极端；

avl

过于平衡，查询性能最好，但是维护成本过高；

treap

splay-tree

区间树

区间树是在平衡树基础上进行扩展得到的支持以区间为元素的动态集合的操作，其中每个节点的关键值是区间的左端点。

区间树

线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 [1]
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。

对编号连续的一些点进行修改或者统计操作，修改和统计的复杂度都是$O(log2(n))$

参考：https://blog.csdn.net/zearot/article/details/48299459

用线段树解题，关键是要想清楚每个节点要存哪些信息（当然区间起终点，以及左右子节点指针是必须的），

以及这些信息如何高效更新，维护，查询。不要一更新就更新到叶子节点，那样更新效率最坏就可能变成O(n)的了。

先建树，然后插入数据，然后更新，查询

树状数组（binary indexed tree）

树状数组所能解决的典型问题就是存在一个长度为n的数组，我们如何高效进行如下操作：

  • update(idx, delta)：将num加到位置idx的数字上。

  • prefixSum(idx)：求从数组第一个位置到第idx（含idx）个位置所有数字的和。

  • rangeSum(from_idx, to_idx)：求从数组第from_idx个位置到第to_idx个位置的所有数字的和

Posted on In Valine:

m叉树中的m具体取决于一个Page的大小，例如4K

如果一个Node的子节点数量超过m，则分裂；如果小于m，会考虑合并

有一根双向链表来连接所有的叶节点

B+优势：

  • 查询效率更加稳定，所有数据的查找均是从根节点到叶子节点。

MongoDB采用B树，聚合文档，没有范围查找需要。

Posted on In Valine:

字典树(Trie)，顾名思义是以树结构来模拟字典。

回想我们查字典的过程，比如查找”man”，先翻到字典m部分，再翻第二个字母a和第三个字母n，一共查找3次。

查找次数最多是等于个单词的长度。插入查找单词的时间复杂度时$O(m)$，此外有公共前缀的单词只需存一次公共前缀，节省了空间，也可理解为前缀树。

字典树应用

  • 字符串检索
    1. 查询检索字符串
  • 词频统计
    1. 统计一个单词出现了多少次
  • 字符串排序
    1. 字典树建好后，先序遍历就得到了排序。
  • 前缀匹配
    1. 根据前缀，用于搜索提示等
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
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

Posted on Edited on In Valine:

跟字符串关联很大的数据结构包括

  1. Trie
  2. 后缀树
  3. 后缀数组(Suffix Array)

后缀树建树的时间和空间成本都很高。后缀数组和后缀自动机可以看作是对后缀树时间和空间上的优化，通过映射关系避免建树和提高树节点重复利用率。

跟字符串相关的hash算法

  • P进制hash（滚动哈希）
    1. 例如：构造哈希比较前缀和后缀，快速判断回文串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
字符串哈希 —— 模板题 AcWing 841. 字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

跟字符串有关系的技巧

  1. 翻手定则
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
class Solution {
public:
    void reverse(string& s, int i, int j) {
        while (i < j) {
            swap(s[i++], s[j--]);
        }
    }

    string trans(string s, int n) {
        int begin = 0;
        for (int i = 0; i < s.length();) {
            if (s[i] == ' ') {
                reverse(s, begin, i - 1);
                i++;
                begin = i;
            }
            else {
                i++;
            }
        }
        reverse(s, begin, s.length() - 1);

        reverse(s, 0, s.length() - 1);

         for (int i = 0; i < s.length(); ++i) {
             if (s[i] >= 'a' && s[i] <= 'z') {
                 s[i] = 'A' + (s[i] - 'a');
             } else if (s[i] >= 'A' && s[i] <= 'Z') {
                 s[i] = 'a' + (s[i] - 'A');
             }  
         }
        return s;
    }
};

字符串匹配算法

Posted on Edited on In Valine:

分类
单调递增栈，栈顶元素最大
单调递减栈，栈顶元素最小

一般套路

如果找右边更大的元素，则从前到后构造从底到顶的递减栈;
如果找右边更小的元素，则从前到后构造从底到顶的递增栈;
如果找左边更大的元素，则从后到前构造从底到顶的递减栈;
如果找左边更小的元素，则从后到前构造从底到顶的递增栈;

举一个例子: n个整数的无序数组，找到每个元素后面比它大的第一个数，要求时间复杂度为O(N)。右边比我更大的问题

栈里面存的是啥？
存的是还没有算出来的元素，为啥没有算出来呢，因为还没有遇到比栈顶元素更大的。并且栈顶元素是最小的，所以当前元素也不会大于栈里面的其他元素。

什么时候可以算出来？
后面遇到比栈顶更大的元素，这时候就出栈，并更新数据。

遍历到最后，栈里面还有啥内容？
整个列表中没有比这些元素更大的元素。

1
2
3
4
5
6
7
8
9
10

//单调栈 —— 模板题 AcWing 830. 单调栈
//常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> dailyTemperatures(vector<int>& t) {
    int n = t.size();
    stack<int> s;
    int top = 0;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && t[i] > t[top = s.top()]){
            t[top] = i - top;
            s.pop();
        }

        s.push(i); //压入了一个更小的，递减栈
    }


    while (!s.empty()) {
        t[s.top()] = 0;
        s.pop();
    }
    return t;
}