当前位置：首页>后端>正文

【算法训练营学习笔记-Week06】一遍不懂就多刷几遍

后端2024-04-03 06:16:43

字典树(Trie )

温故知新:

树的定义
二叉树，前中序列遍历，层次遍历
DFS和BFS
二叉搜索树(BFS)定义，左子树都小于根，右子树都大于根，中序遍历是有序序列

实际问题：搜索引擎中自动联想

定义: 多叉树，常用于搜索引擎的文本词频统计，用于最大新都减少不必要的字符串比较，查找效率高于哈希表

基本性质:

节点本身不存完整单词
从根节点到某一节点，路径上经过的字符链接起来，为该节点对应的字符串
每个节点的所有子节点路径代表的字符串都不相同

注意，图中的to, ted, tea 并不实际存在，只是表示按照路径查找之后连接后的单词

字典树

核心思想:

空间换时间（树的每层至少存在26个分支）
利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的

Trie模板

class Trie(object):
    
    def __init__(self): 
        self.root = {} 
        self.end_of_word = "#" 
        
    def insert(self, word): 
        node = self.root 
        for char in word: 
            node = node.setdefault(char, {}) 
        node[self.end_of_word] = self.end_of_word 

    def search(self, word): 
        node = self.root 
        for char in word: 
            if char not in node: 
                return False 
            node = node[char] 
        return self.end_of_word in node 

    def startsWith(self, prefix): 
        node = self.root 
        for char in prefix: 
            if char not in node: 
                return False 
            node = node[char] 
        return True

实现字典树: 看题解，临摹一种写法，不必要自己去创造（除非你想）.动态采用字典数据结构（哈希表）

单词搜索: 无论是1还是2，都很经典, 要学习计算时间复杂度（这是面试的最高难度）

并查集

直接套用模板即可，常用来解决组团和配对问题(Group or not?)

属于

基本操作

makeSet(s): 新建一个新的并查集，包括s个元素集合
unionSet(x,y): 合并元素x和元素y，要求x和y所在集合不相交，如果相交则不合并
find(x): 找到元素x所在集合的代表，该操作也可以用来判断两个元素是否位于同一个集合，只要将他们各自的代表比较一下就可以

路径压缩

代码模板: Python

def init(p): 
    # for i = 0 .. n: p[i] = i; 
    p = [i for i in range(n)] 

def union(self, p, i, j): 
    p1 = self.parent(p, i) 
    p2 = self.parent(p, j) 
    p[p1] = p2 
    
def parent(self, p, i): 
    root = i 
    while p[root] != root: 
        root = p[root] 
    while p[i] != i: # 路径压缩 ?
        x = i; i = p[i]; p[x] = root 
    return root

struct DSU
{
    std::vector<int> data;
    
    void init(int n) { data.assign(n, -1); }
    
    bool unionSet(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (data[y] < data[x])
            {
                std::swap(x, y);
            }
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }

    bool same(int x, int y) { return root(x) == root(y); }

    int root(int x) { return data[x] < 0 x : data[x] = root(data[x]); }

    int size(int x) { return -data[root(x)]; }
};

//https://leetcode-cn.com/problems/friend-circles/solution/547-by-ikaruga/

朋友圈：每个人都是一个人，然后根据好友关系矩阵，如果M[i][j]==1, 就合并，最后统计孤立的集合。

高级搜索

不要死磕，多过遍数（你不是一个人懵逼）

初级搜索改进

不重复(斐波那契)、剪枝（括号生成）
双向搜索，启发式搜索（优先级搜索）

剪枝

括号生成: 剪枝体现在右括号一定要小于左括号。而不是生成所有可能后，再去判断是否符合要求

思考题: DP如何解决括号生成的问题。

N皇后问题: 剪枝体现在，发现col, row diagonal只要存在皇后，立马放弃（剪枝），而不是先把所有可能都生成之后，才去判断当前布局是否符合要求。

数独问题: 剪枝体现在对行、列、块进行判断，用于判断是否合法，不符合就不再递归。更好的操作，预先扫描数组，记录每行、每列、每个方块的可填数组，记录哪些位置需要进行填写。

双向BFS

先默写BFS模板代码

def BFS(graph, start, end):
    visited = set()
    queue = []
    queue.append[start]
    while queue: #不为空
        # 处理
        node = queue.pop()
        visited.add(node)

        process(node)
        nodes = generate_related_nodes(node)
        queue.push(nodes)
    #other process work
    ...

双向BFS就是从A和L分别往中间搜索，两个人在中间碰头

双向BFS

单词接龙（硅谷非常高频）

双向模板

def dBFS(graph, start, end):
    visited = set()
    front = []
    back = []
    front.append(start)
    back.append(end)
    while front and back:
        nodes = set()
        for node in front:
            visited.add(node) #加入访问
            process(node) # 处理当前node
            nodes.append(generate_related_nodes(node)) #获取子节点
        front = nodes
        # 从较小的set开始
        if len(back) < len(front):
            front, back = back, front
    ...

是否双向BFS一定要用set？

很多时候，双向BFS的队列底层数据结构会用set，特别是那种左边动一步，右边动一步，每次就把所有一层的节点处理完，生成新的一层的节点的情况，用set能更好的判断对面的节点是否也在当前的节点里有。

启发式搜索

不需要着急学习这一块，注意多过遍数（你不是一个人一脸懵逼的听完第一遍）

启发式搜索（Heuristic Search, A*）,Heuristic指的是根据某一些条件，我们不断的优化搜索方向，本质上用的就是利用优先级进行查找。

def AstarSearch(graph, start, end):

    pq = collections.priority_queue() # 优先级 —> 估价函数
    pq.append([start]) 
    visited.add(start)

    while pq: 
        node = pq.pop() # can we add more intelligence here ?
        visited.add(node)

        process(node) 
        nodes = generate_related_nodes(node) 
         unvisited = [node for node in nodes if node not in visited]
        pq.push(unvisited)

核心是在定义在估价函数, h(n)。

一些相似度度量方法：https://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/

二进制矩阵的最短路径，估计函数，曼哈顿距离

滑动谜题: 经典题目是 8 puzzles