Data Structures Advanced

sliding window

//通过两层for循环改进算法
for (i = 0, i < n; ++i) {
    while (j < n) {
        if (满足条件) {
            j++;
            更新j状态
        } else if (不满足条件) {
            break;
        }
    }
    //更新i状态
}

• 在一维字符串或者数组中找到符合条件的字串
• 前向型指针题目
• 窗口类
• remove nth node from end of list
• Minimum size subarray sum
• Longest substring without rapeating characters
• Minimum window substring
• Longest Substring with at most k distinct characters
• Longest Repeating Character Replacement
• Longest Turbulent subarray
• 快慢类
• find the middle of the linked list
• linked list cycle 1 and 2
• 优化类型

1. 优化思想通过两层for循环而来
2. 外层指针依然是一次遍历
3. 内层指针证明是否需要退回

• two pointers题型分类

1. 前向型
   1. 窗口型
   2. 快慢型
2. 相向型
3. 两个数组

• 第k大或者第k小问题

Union Find 并查集

• 一种用来解决集合查询合并的数据结构 支持O(1) find and O(1) union，O(n) space

1. 检查两个元素是否属于同一集合
2. 合并两个集合，将root node指向另一个root node

• 可以使用array或者哈希表实现Union find
• 查找 find O(n) time

public int find(int x) {
    if (father[x] == x) {
    return x;
    }
    return find(father[x]);
}

• 合并 union, O(n) time, 之合并两个root nodes，不管child nodes

public void union(int a, int b) {
    int root_a = find(a);
    int root_b = find(b);
    // 如果两个root nodes已经相等，则两个集合已经合并，不需要再操作
    if (root_a != root_b) {
    father[root_a] = root_b; // 将root_a指向root_b
    }
}

• 路径压缩：将find和union的时间复杂度变成O(1)
• 在查找元素的father的时候，第一次需要O(n)的时间，但是当找到最终的father时，将每一个路径中的father都更新成最终的father，以后在查找路径中的father就只需要O(1)

public int find(int x) {
    if (father[x] == x) {
        return x;
    }
    return father[x] = find(father[x]); // 将当前点的father更新为最终father
}

1. Connecting graph 3
2. Connecting cities with minimum costs
3. Number of Operations to Make Network Connected
4. The Earliest Moment When Everyone Become Friends
5. Lexicographically Smallest Equivalent String
6. Number of Islands II

• Union find问题总结
• 原生操作
  1. 查询两个元素是否在用一个集合内。
  2. 合并两个元素所在的集合
• 派生操作
  1. 查询某个元素所在集合的元素个数。
  2. 查询当前集合的个数

Trie

• 常见考点
• 1. Trie直接实现
• 2. 利用Trie前缀特性解题
• 3. 矩阵类里面，字符串一个一个字符，深度优先遍历的问题
• Trie和Hash拥有相同的时间复杂度，但是Trie的空间复杂度更小

1. Implement Trie
2. Add and search word
3. word search 2 -> Trie + DFS

Heap

• Trapping rain water 2
• 怎么通过Trapping rain water 1拓展到这道题的思路
• 怎么样想到利用heap？
• 怎么想到由外向内遍历？
• Find Median from Data Stream
• Sliding Window Median