【LeetCode 热题 100】图论 专题(bfs,拓扑排序,Trie树 字典树)

这篇具有很好参考价值的文章主要介绍了【LeetCode 热题 100】图论 专题(bfs,拓扑排序,Trie树 字典树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

from: https://leetcode.cn/studyplan/top-100-liked/

bfs 具有 边权为1 的最短路性质
拓扑排序,入度
Trie树, 高效存储 字符串【见鬼,不知道为什么写错,需要掌握熟练度】


200. 岛屿数量【dfs / bfs】

dfs 写法,比较简洁

class Solution {
public:

    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
    int n, m;

    int numIslands(vector<vector<char>>& grid) {
        n = grid.size(), m = grid[0].size();
   
        int cnt = 0;
        for(int i = 0;i < n;i ++ ){
            for(int j = 0;j < m;j ++ ){
                if(grid[i][j] == '1') {
                    cnt ++ ;
                    dfs(i, j, grid);
                }
            }
        }
        return cnt;
    }

    void dfs(int x, int y,vector<vector<char>>& grid){
        grid[x][y] = '0';
        for(int i = 0;i < 4;i ++ ){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == '1') 
                dfs(a, b, grid);
        }
    };
};

bfs 写法,有最短路性质

#define x first
#define y second

class Solution {
public:
    int n, m;
    typedef pair<int,int> PII;
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;

        n = grid.size(), m = grid[0].size();

        int res = 0;
        for(int i =0;i<n;i++)
            for(int j=0;j<m;j++)
                if(grid[i][j] == '1')
                {
                    res ++;
                    bfs(i,j,grid);
                   
                }
        
        return res;
    }

    void bfs(int x,int y,vector<vector<char>>& grid)
    {
        queue<PII> q;
        q.push({x,y});
        grid[x][y] = '0';

        while(!q.empty())
        {
            auto t = q.front();
            q.pop();


            for(int i=0;i<4;i++)
            {
                int a = t.x + dx[i], b =t.y + dy[i]; // debug : 这里是新坐标的t.x 不是 x
                if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == '1')
                {
                    grid[a][b] = '0';
                    q.push({a,b});
                }
            }
        }
    }
};

994. 腐烂的橘子【bfs 具有 边权为1 的最短路性质】

bfs 具有 边权为1 的最短路性质

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        
        bool st[n][m];
        memset(st, 0, sizeof st);

        queue<pair<int,int>> q;
        int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

        for(int i = 0;i < n;i ++ ){
            for(int j = 0; j < m;j ++ ){
                if(grid[i][j] == 2) {
                    q.push({i, j});
                    st[i][j] = true;
                }
            }
        }

        int res = 0;
        while(q.size()){
            
            int k = q.size(); // debug: int k, 写成n 和 前面命名重复了!
            res ++ ;
            while(k -- ){
                auto t = q.front();
                q.pop();
                
                for(int i = 0;i < 4;i ++ ){
                    int a = t.first + dx[i], b = t.second + dy[i];
                    if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1 && !st[a][b]){
                        q.push({a, b});
                        grid[a][b] = 2;
                        st[a][b] = true;
                    }
                }
            }
            
        }

        for(int i = 0;i < n;i ++ ){
            for(int j = 0; j < m;j ++ ){
                if(grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        if(res == 0) return 0;
        return res - 1;
    }
};

207. 课程表【拓扑排序】

拓扑排序



class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 拓扑排序

        int d[numCourses];
        memset(d, 0, sizeof d);

        vector<int> g[numCourses];


        for(auto &c : prerequisites) {
            int a = c[0], b = c[1];
            g[a].push_back(b);
            d[b] ++ ;
        }

        queue<int> q;
        for(int i = 0;i < numCourses;i ++ ){
            if(d[i] == 0) q.push(i);
        }

        while(q.size()){
            int t = q.front();
            q.pop();

            for(auto to : g[t]){
                    d[to] -- ;
                    if(d[to] == 0) q.push(to);
            }
        }

        for(int i = 0;i < numCourses;i ++ ){
            if(d[i] != 0) return false;
        }
        return true;
    }
};

208. 实现 Trie (前缀树)【模板题】

模板题

数组写法,简洁,需要注意开的数组空间 N * 结点

const int N = 30010;

int tr[N * 26][26], idx;
int cnt[N * 26];

class Trie {
public:
    Trie() {
        idx = 0;
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
    }
    
    void insert(string word) {
        int p = 0;
        for(auto c : word){
            int u = c - 'a';
            if(!tr[p][u]) tr[p][u] = ++ idx;
            p = tr[p][u];
        }
        cnt[p] ++ ;
    }
    
    bool search(string word) {
        int p = 0;
        for(auto c : word){
            int u = c - 'a';
            if(!tr[p][u]) return false;
            p = tr[p][u];
        }
        return cnt[p] > 0;
    }
    
    bool startsWith(string prefix) {
        int p = 0;
        for(auto c : prefix){
            int u = c - 'a';
            if(!tr[p][u]) return false;
            p = tr[p][u];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

指针写法文章来源地址https://www.toymoban.com/news/detail-635154.html

class Trie {
public:


    struct Node
    {
        bool is_end;
        Node *son[26];

        Node()
        {
            is_end = false;
            for(int i=0;i<26;i++) son[i] = NULL;
        }
    }*root;


    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        auto *p = root;
        for(auto c : word)
        {
            int u = c - 'a';
            if(p->son[u] == NULL) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto *p = root;
        for(auto c : word)
        {
            int u = c - 'a';
            if(p->son[u] == NULL) return false;
            p = p->son[u];
        }
        return p->is_end;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto *p = root;
        for(auto c : prefix)
        {
            int u = c - 'a';
            if(p->son[u] == NULL) return false;
            p = p->son[u]; 
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

到了这里,关于【LeetCode 热题 100】图论 专题(bfs,拓扑排序,Trie树 字典树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 热题100——链表专题(一)

    2.俩数相加(题目链接) 思路:这题题目首先要看懂,以示例1为例  即  342+465=807,而产生的新链表为7-0-8. 可以看成简单的从左向右,低位到高位的加法运算,4+6=10,逢10进1,新链表第三位为3+4+1(第二位进的1),需要注意的的点是当9-9-9和9-9-9-9相加,相当于9-9-9-0和9-9-9-9相加

    2024年02月03日
    浏览(42)
  • LeetCode 热题100——栈与队列专题(三)

    20.有效的括号(题目链接) 思路: 1)括号的顺序匹配:用栈实现,遇到左括号入,遇到右括号出(保证所出的左括号与右括号对应),否则顺序不匹配。 2)括号的数量匹配: 1左括号大于右括号:用栈实现,遇到左括号入,遇到右括号出,遍历完字符数组,此时栈不为空,

    2024年02月04日
    浏览(46)
  • 算法沉淀——BFS 解决拓扑排序(leetcode真题剖析)

    Breadth-First Search (BFS) 在拓扑排序中的应用主要是用来解决有向无环图(DAG)的拓扑排序问题。拓扑排序是对有向图中所有节点的一种线性排序,使得对于每一条有向边 (u, v),节点 u 在排序中都出现在节点 v 的前面。如果图中存在环路,则无法进行拓扑排序。 BFS 解决拓扑排序

    2024年02月21日
    浏览(40)
  • 【LeetCode 热题 100】矩阵 专题(大多原地算法,需要一定思维)

    解题思路 在 代码注释中!

    2024年02月15日
    浏览(51)
  • 拓扑排序算法 -- dfs、bfs

    210. 课程表 II 该题用到「拓扑排序」的算法思想,关于拓扑排序,直观地说就是,让你把⼀幅图「拉平」,⽽且这个「拉平」的图⾥⾯,所有箭头⽅向都是⼀致的,⽐如上图所有箭头都是朝右的。 很显然,如果⼀幅有向图中存在环,是⽆法进⾏拓扑排序的,因为肯定做不到所

    2024年02月10日
    浏览(42)
  • 【图论】Leetcode 208. 实现 Trie (前缀树)【中等】

    Trie (发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。 请你实现 Trie 类: Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word 。 boolean

    2024年04月16日
    浏览(58)
  • 图论应用——拓扑排序

    拓扑排序的原理和宽度优先搜索差不多

    2024年04月26日
    浏览(56)
  • 【图论】拓扑排序

     拓扑排序是一种对有向无环图(DAG)进行排序的算法,使得图中的每个顶点在排序中都位于其依赖的顶点之后。它通常用于表示一些任务之间的依赖关系,例如在一个项目中,某些任务必须在其他任务之前完成。 拓扑排序的步骤如下: 找到入度为0的顶点:入度是指指向某

    2024年02月11日
    浏览(38)
  • 【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)

    有向图(Directed Graph),也被称为有向图形或方向图,是一种图的类型。在有向图中,图中的边具有方向,从一个顶点指向另一个顶点。 在有向图中,每个顶点表示一个实体,而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系

    2024年02月09日
    浏览(50)
  • 第三章 图论 No.13拓扑排序

    拓扑序和DAG有向无环图联系在一起,通常用于最短/长路的线性求解 裸题:1191. 家谱树 1191. 家谱树 - AcWing题库 差分约束+拓扑排序:1192. 奖金 1192. 奖金 - AcWing题库 由于图中所有边权都是正数,可以直接使用topsort求解差分约束问题 根据题意,要求一个最小值,使用最长路求解

    2024年02月12日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包