国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<thead id="chsbq"><strong id="chsbq"><label id="chsbq"></label></strong></thead><s id="chsbq"></s>

<rp id="chsbq"></rp>

代碼隨想錄Day41-圖論：力扣第797m、200m、695m、1020m、130m題

2年前作者：豬扒已出閘分類：Toy博客閱讀(24)違法舉報

這篇具有很好參考價值的文章主要介紹了代碼隨想錄Day41-圖論：力扣第797m、200m、695m、1020m、130m題。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

797m. 所有可能的路徑

題目鏈接
代碼隨想錄文章講解鏈接

方法一：DFS

用時：11m43s

思路

時間復(fù)雜度： $\cdot 2^n)$ ，n是節(jié)點個數(shù)，最壞情況每個節(jié)點都可以去往任意一個在它后面的節(jié)點，那么第i個節(jié)點去到最后一個節(jié)點的路徑數(shù)就有 $2^{n-i-2}$ ，就是當前節(jié)點和最后一個節(jié)點必走，其他的節(jié)點有兩種選擇——走或不走。
空間復(fù)雜度： $O (n)$ 。

C++代碼

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;

    void backTracking(vector<vector<int>>& graph, int i) {
        if (i == graph.size() - 1) {
            res.push_back(path);
            return;
        }
        for (int j = 0; j < graph[i].size(); ++j) {
            path.push_back(graph[i][j]);
            backTracking(graph, graph[i][j]);
            path.pop_back();  // 回溯
        }
    }

public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0);
        backTracking(graph, 0);
        return res;
    }
};

方法二：BFS

用時：16m18s

思路

隊列中記錄的元素是路徑。

時間復(fù)雜度： $O ()$
空間復(fù)雜度： $O ()$

C++代碼

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        queue<vector<int>> que;
        vector<vector<int>> res;

        que.push({0});
        while (!que.empty()) {
            vector<int> path = que.front();
            que.pop();
            for (int i = 0; i < graph[path.back()].size(); ++i) {
                vector<int> tmp = path;
                tmp.push_back(graph[path.back()][i]);
                if (tmp.back() == graph.size() - 1) res.push_back(tmp);
                else que.push(tmp);
            }
        }
        return res;
    }
};

看完講解的思考

無。

代碼實現(xiàn)遇到的問題

無。

200m. 島嶼數(shù)量

題目鏈接
代碼隨想錄文章講解鏈接

方法一：DFS

用時：17m48s

思路

遍歷每個元素，若是陸地則使用DFS搜索與之相鄰的所有陸地，并使用一個二維數(shù)組記錄哪些陸地已經(jīng)遍歷過。
當遍歷到新的島嶼時，島嶼數(shù)加1。

時間復(fù)雜度： $\cdot n)$
空間復(fù)雜度： $\cdot n)$

C++代碼

class Solution {
private:
    int m;
    int n;
    int dir[4][2] = {0, -1, 1, 0, 0, 1, -1, 0};

    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        visited[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (!(nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) && !visited[nextx][nexty] && grid[nextx][nexty] == '1') dfs(grid, visited, nextx, nexty);
        }
    }
    
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int res = 0;

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

方法二：方法一優(yōu)化

思路

可以不用數(shù)組記錄哪些陸地訪問過，只用把訪問過的陸地置0即可。

時間復(fù)雜度： $\cdot n)$
空間復(fù)雜度： $\cdot n)$

C++代碼

class Solution {
private:
    int m;
    int n;
    int dir[4][2] = {0, -1, 1, 0, 0, 1, -1, 0};

    void dfs(vector<vector<char>>& grid, int x, int y) {
        grid[x][y] = '0';
        for (int i = 0; i < 4; ++i) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (!(nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) && grid[nextx][nexty] == '1') dfs(grid, nextx, nexty);
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int res = 0;

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

看完講解的思考

代碼實現(xiàn)遇到的問題

方法三：BFS

思路

時間復(fù)雜度： $\cdot n)$
空間復(fù)雜度： $O (min (m, n))$

C++代碼

class Solution {
private:
    int m;
    int n;
    int dir[4][2] = {0, -1, 1, 0, 0, 1, -1, 0};

    void bfs(vector<vector<char>>& grid, int x, int y) {
        queue<pair<int, int>> que;
        grid[x][y] = '0';
        que.push(pair<int, int>(x, y));
        while (!que.empty()) {
            pair<int, int> tmp = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int nextx = tmp.first + dir[i][0];
                int nexty = tmp.second + dir[i][1];
                if (!(nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) && grid[nextx][nexty] == '1') {
                    grid[nextx][nexty] = '0';
                    que.push(pair<int, int>(nextx, nexty));
                }
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int res = 0;

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

看完講解的思考

無。

代碼實現(xiàn)遇到的問題

無。

695m. 島嶼的最大面積

題目鏈接
代碼隨想錄文章講解鏈接

方法一：DFS

用時：16m39s

思路

當遇到陸地時，DFS該島嶼，記錄該島嶼的面積，并將遍歷過的陸地置零，最后返回最大的島嶼的面積。

時間復(fù)雜度： $\cdot n)$ 。
空間復(fù)雜度： $\cdot n)$ 。

C++代碼

class Solution {
private:
    int m;
    int n;
    int area;

    void dfs(vector<vector<int>>& grid, int x, int y) {
        grid[x][y] = 0;
        area += 1;
        if (x - 1 >= 0 && grid[x - 1][y] == 1) dfs(grid, x - 1, y);
        if (x + 1 < m && grid[x + 1][y] == 1) dfs(grid, x + 1, y);
        if (y - 1 >= 0 && grid[x][y - 1] == 1) dfs(grid, x, y - 1);
        if (y + 1 < n && grid[x][y + 1] == 1) dfs(grid, x, y + 1);
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    area = 0;
                    dfs(grid, i, j);
                    res = max(res, area);
                }
            }
        }
        return res;
    }
};

方法二：BFS

思路

時間復(fù)雜度： $\cdot n)$
空間復(fù)雜度： $O (min (m, n))$

C++代碼

class Solution {
private:
    int m;
    int n;
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    int bfs(vector<vector<int>>& grid, int x, int y) {
        int area = 1;
        queue<pair<int, int>> que;

        que.push(pair<int, int>(x, y));
        grid[x][y] = 0;
        while (!que.empty()) {
            pair<int, int> tmp = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int nextx = tmp.first + dir[i][0];
                int nexty = tmp.second + dir[i][1];
                if (!(nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) && grid[nextx][nexty] == 1) {
                    grid[nextx][nexty] = 0;
                    area += 1;
                    que.push(pair<int, int>(nextx, nexty));
                }
            }
        }
        return area;
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) res = max(res, bfs(grid, i, j));
            }
        }
        return res;
    }
};

看完講解的思考

無。

代碼實現(xiàn)遇到的問題

BFS時，元素入列的時候就要做標記，不能在元素出列的時候才做標記，不然會重復(fù)遍歷。

1020m. 飛地的數(shù)量

題目鏈接
代碼隨想錄文章講解鏈接

方法一：DFS

用時：20m42s

思路

在上一題695m的基礎(chǔ)上，加多一個變量用于記錄當前島嶼是否臨界，如果不是的話將島嶼的陸地數(shù)量記錄。

時間復(fù)雜度： $\cdot n)$ 。
空間復(fù)雜度： $\cdot n)$ 。

C++代碼

class Solution {
private:
    int m;
    int n;
    int num;
    bool flag;

    void dfs(vector<vector<int>>& grid, int x, int y) {
        grid[x][y] = 0;
        num += 1;
        if (x - 1 < 0) flag = true;
        else if (grid[x - 1][y] == 1) dfs(grid, x - 1, y);
        if (x + 1 >= m) flag = true;
        else if (grid[x + 1][y] == 1) dfs(grid, x + 1, y);
        if (y - 1 < 0) flag = true;
        else if (grid[x][y - 1] == 1) dfs(grid, x, y - 1);
        if (y + 1 >= n) flag = true;
        else if (grid[x][y + 1] == 1) dfs(grid, x, y + 1);
    }

public:
    int numEnclaves(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    num = 0;
                    flag = false;
                    dfs(grid, i, j);
                    if (!flag) res += num;
                }
            }
        }
        return res;
    }
};

方法二：BFS

思路

時間復(fù)雜度： $\cdot n)$ 。
空間復(fù)雜度： $O (min (m, n))$ 。

C++代碼

class Solution {
private:
    int m;
    int n;
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

    int bfs(vector<vector<int>>& grid, int x, int y) {
        int num = 1;
        queue<pair<int, int>> que;

        que.push(pair<int, int>(x, y));
        grid[x][y] = 0;
        while (!que.empty()) {
            pair<int, int> tmp = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int nextx = tmp.first + dir[i][0];
                int nexty = tmp.second + dir[i][1];
                if (nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) num = INT_MIN;
                else if (grid[nextx][nexty] == 1) {
                    grid[nextx][nexty] = 0;
                    ++num;
                    que.push(pair<int, int>(nextx, nexty));
                }
            }
        }
        return num;
    }

public:
    int numEnclaves(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) res += max(0, bfs(grid, i, j));
            }
        }
        return res;
    }
};

看完講解的思考

無。

代碼實現(xiàn)遇到的問題

無。

130m. 被圍繞的區(qū)域

題目鏈接
代碼隨想錄文章講解鏈接

方法一：DFS

用時：17m13s

思路

遍歷位于臨界的元素，若是’O’則將連通的’O’變成’H’，最后再將board中的所有’O’替換成’X’，‘H’替換成’O’，因為此時剩下的’O’是位于board內(nèi)部的無法連接到外部的元素，直接將其變成’X’，而’H’是可以連通到外部的’O’，將其變回’O’。

時間復(fù)雜度： $\cdot n)$ 。
空間復(fù)雜度： $\cdot n)$ 。

C++代碼

class Solution {
private:
    int m;
    int n;

    void dfs(vector<vector<char>>& board, int x, int y) {
        board[x][y] = 'H';
        if (x - 1 >= 0 && board[x - 1][y] == 'O') dfs(board, x - 1, y);
        if (x + 1 < m && board[x + 1][y] == 'O') dfs(board, x + 1, y);
        if (y - 1 >= 0 && board[x][y - 1] == 'O') dfs(board, x, y - 1);
        if (y + 1 < n && board[x][y + 1] == 'O') dfs(board, x, y + 1);
    }

public:
    void solve(vector<vector<char>>& board) {
        m = board.size();
        n = board[0].size();
        for (int i = 0; i < m; ++i) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }
        for (int i = 0; i < n; ++i) {
            if (board[0][i] == 'O') dfs(board, 0, i);
            if (board[m - 1][i] == 'O') dfs(board, m - 1, i);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'H') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
};

方法二：BFS

思路

就是遍歷的方法從DFS換成BFS，懶得寫了。

時間復(fù)雜度： $\cdot n)$ 。
空間復(fù)雜度： $O (min (m, n))$ 。

看完講解的思考

無。

代碼實現(xiàn)遇到的問題

無。

最后的碎碎念

就快要一刷完代碼隨想錄，沖！文章來源地址http://www.zghlxwxcb.cn/news/detail-738936.html

到了這里，關(guān)于代碼隨想錄Day41-圖論：力扣第797m、200m、695m、1020m、130m題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

代碼隨想錄第41天 | 動態(tài)規(guī)劃part03
● 343. 整數(shù)拆分 ● 96.不同的二叉搜索樹題目一 343. 整數(shù)拆分給定一個正整數(shù) n，將其拆分為至少兩個正整數(shù)的和，并使這些整數(shù)的乘積最大化。返回你可以獲得的最大乘積。示例 : 輸入: 10 輸出: 36 解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。說明: 你可以假設(shè) n 不小于 2 且不大于 5
2024年01月24日
瀏覽(26)
代碼隨想錄圖論
目錄 797.所有可能得路徑? 200.島嶼數(shù)量 695.島嶼的最大面積 1020.飛地的數(shù)量? 130.被圍繞的區(qū)域? 417.太平洋大西洋水流問題? 827.最大人工島 127.單詞接龍? 841.鑰匙和房間 463.島嶼的周長? 797. 所有可能的路徑中等給你一個有? n ?個節(jié)點的? 有向無環(huán)圖（DAG），請你找出所有從
2024年04月10日
瀏覽(23)
代碼隨想錄（番外）圖論1
1. 深度優(yōu)先搜索理論基礎(chǔ) 2. 所有可能的路徑 3. 廣度優(yōu)先搜索理論基礎(chǔ).md https://programmercarl.com/%E5%9B%BE%E8%AE%BA%E6%B7%B1%E6%90%9C%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 1. 深度優(yōu)先搜索理論基礎(chǔ) 總結(jié) 同理回溯算法，換湯不換藥二叉樹遞歸講解 (opens new window)中，給出了遞歸三部曲。回溯算
2024年04月28日
瀏覽(22)
代碼隨想錄（番外）圖論4
417. 太平洋大西洋水流問題那么我們可以反過來想，從太平洋邊上的節(jié)點逆流而上，將遍歷過的節(jié)點都標記上。從大西洋的邊上節(jié)點逆流而長，將遍歷過的節(jié)點也標記上。然后兩方都標記過的節(jié)點就是既可以流太平洋也可以流大西洋的節(jié)點。也就是說通過從兩邊的大洋開
2024年04月29日
瀏覽(15)
代碼隨想錄Day58
昨天因為志愿活動和筆試耽誤了一整天，今天繼續(xù)學(xué)習(xí)動規(guī)解決子序列問題。給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，\\\"ace\\\"是\\\"abcde\\\"的一個子序列，
2023年04月27日
瀏覽(97)
代碼隨想錄Day50
昨天因為準備面試所以咕咕了一天。今天繼續(xù)學(xué)習(xí)動規(guī)算法，盡管背包問題已經(jīng)結(jié)束但其中的各類思想仍需要進一步理解。你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩
2023年04月14日
瀏覽(93)
代碼隨想錄day59
647. 回文子串給你一個字符串? s ?，請你統(tǒng)計并返回這個字符串中? 回文子串 ?的數(shù)目。回文字符串 ?是正著讀和倒過來讀一樣的字符串。子字符串 ?是字符串中的由連續(xù)字符組成的一個序列。具有不同開始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會被視作不
2024年02月07日
瀏覽(87)
代碼隨想錄day44
完全背包其實就是每個物品可以使用無數(shù)次，給我們一個容器，裝滿這個容器的最大價值是多少。思路：如果求組合數(shù)就是外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包。如果求排列數(shù)就是外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品。完全背包的組合和排序 518. 零錢兌換 II 題目給你
2023年04月17日
瀏覽(91)
代碼隨想錄day01
● 思維不難，主要是考察對代碼的掌控能力 ● 內(nèi)存中的存儲方式：存放在連續(xù)內(nèi)存空間上的相同類型數(shù)據(jù)的集合 ● 數(shù)組可以通過下標索引獲取到下標對應(yīng)的數(shù)據(jù) ● 數(shù)組下標從0開始 ● 因為內(nèi)存空間地址連續(xù)，因此刪除或增加元素的時候，難免移動其他元素地址 ● Java中的
2024年02月13日
瀏覽(94)
代碼隨想錄day02
● 力扣題目鏈接 ● 給你一個按非遞減順序排序的整數(shù)數(shù)組 nums，返回每個數(shù)字的平方組成的新數(shù)組，要求也按非遞減順序排序。思路 ● 暴力排序，時間復(fù)雜度O(n + nlogn) ● 使用雙指針，時間復(fù)雜度O(n) 代碼 ● 力扣題目鏈接 ● 給定一個含有 n 個正整數(shù)的數(shù)組和一個正整
2024年02月13日
瀏覽(104)

<td id="ro9po"><dl id="ro9po"></dl></td>

<noscript id="ro9po"></noscript>