更多干貨就在我的個(gè)人博客 BlackBlog.tech 歡迎關(guān)注！
也可以關(guān)注我的csdn博客：黑哥的博客
謝謝大家！

LeetCode Everyday!
我們繼續(xù)LeetCode之旅，這一篇再完成十個(gè)題，我們就進(jìn)入下一個(gè)章節(jié)。做了一段時(shí)間LeetCode。感覺真的挺不錯(cuò)的，以前數(shù)據(jù)結(jié)構(gòu)課上的很多內(nèi)容又回以前來(lái)了。LeetCode很適合鍛煉基礎(chǔ)功，題目也很清晰。很不錯(cuò)。建議各位如果有時(shí)間，可以從中級(jí)算法開始練習(xí)。一日一題，都會(huì)有很大提升。

給個(gè)目錄：
LeetCode638 大禮包
LeetCode542 01矩陣
LeetCode529 掃雷游戲
LeetCode547 朋友圈
LeetCode576 出界的路徑數(shù)
LeetCode721 賬戶合并
LeetCode743 網(wǎng)絡(luò)延遲時(shí)
LeetCode785 判斷二分圖
LeetCode841 鑰匙和房間
LeetCode207 課程表

LeetCode638 大禮包

題目

在LeetCode商店中， 有許多在售的物品。

然而，也有一些大禮包，每個(gè)大禮包以優(yōu)惠的價(jià)格捆綁銷售一組物品。

現(xiàn)給定每個(gè)物品的價(jià)格，每個(gè)大禮包包含物品的清單，以及待購(gòu)物品清單。請(qǐng)輸出確切完成待購(gòu)清單的最低花費(fèi)。

每個(gè)大禮包的由一個(gè)數(shù)組中的一組數(shù)據(jù)描述，最后一個(gè)數(shù)字代表大禮包的價(jià)格，其他數(shù)字分別表示內(nèi)含的其他種類物品的數(shù)量。

任意大禮包可無(wú)限次購(gòu)買。

示例 1:

輸入: [2,5], [[3,0,5],[1,2,10]], [3,2]
輸出: 14
解釋: 
有A和B兩種物品，價(jià)格分別為￥2和￥5。
大禮包1，你可以以￥5的價(jià)格購(gòu)買3A和0B。
大禮包2， 你可以以￥10的價(jià)格購(gòu)買1A和2B。
你需要購(gòu)買3個(gè)A和2個(gè)B， 所以你付了￥10購(gòu)買了1A和2B（大禮包2），以及￥4購(gòu)買2A。

示例 2:

輸入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
輸出: 11
解釋: 
A，B，C的價(jià)格分別為￥2，￥3，￥4.
你可以用￥4購(gòu)買1A和2B，也可以用￥9購(gòu)買2A，2B和1C。
你需要買1A，2B和1C，所以你付了￥4買了1A和1B（大禮包1），以及￥3購(gòu)買1B， ￥4購(gòu)買1C。
你不可以購(gòu)買超出待購(gòu)清單的物品，盡管購(gòu)買大禮包2更加便宜。

說(shuō)明:

最多6種物品， 100種大禮包。
每種物品，你最多只需要購(gòu)買6個(gè)。
你不可以購(gòu)買超出待購(gòu)清單的物品，即使更便宜。

C++代碼

class Solution {
public:
//判斷是否能夠放入當(dāng)前這個(gè)禮包
    bool valid(vector<int> special_single, vector<int> needs){
        for(int i=0;i<needs.size();i++){
            if(special_single[i]>needs[i]) return false;
        }
        return true;
    }

    int shoppingOffers(vector<int> &price, vector<vector<int>> &special, vector<int> &needs) {
        int min_money = 0; //表示最小值
        //如果全部買單獨(dú)的物品
        for(int i=0;i<needs.size();i++){
            min_money += price[i] * needs[i];
        }
        //遍歷所有禮包
        for(int i=0;i<special.size();i++){
            if(valid(special[i],needs)){
                //如果禮包可以購(gòu)買的話
                vector<int> new_needs; //新建一個(gè)數(shù)組 表示新的needs
                for(int j=0;j<needs.size();j++)
                    new_needs.push_back(needs[j]-special[i][j]); //新的needs = 舊的needs - 禮包中物品的個(gè)數(shù)
                int money_tmp = shoppingOffers(price,special,new_needs) + special[i].back(); //將當(dāng)前禮包的幾個(gè)加到money_temp上，同時(shí)繼續(xù)遍歷
                min_money = min(min_money,money_tmp); //最后求出最低價(jià)格
            }
        }
        return min_money;//返回最低價(jià)格
    }
};

體會(huì)

這個(gè)題不難，但鑒于我摳腳的水平，竟然做了很久。我們采取這樣的思路，首先單獨(dú)買下所有的產(chǎn)品，計(jì)算出價(jià)格，之后我們遍歷禮包進(jìn)行搜索，在搜索的過程中每次都要更新needs，這樣可以實(shí)現(xiàn)零售+禮包的方式，每次記錄下禮包的價(jià)格，搜索結(jié)束后，找到最小的價(jià)格，返回。

LeetCode542 01矩陣

題目

給定一個(gè)由 0 和 1 組成的矩陣，找出每個(gè)元素到最近的 0 的距離。

兩個(gè)相鄰元素間的距離為 1 。

示例 1:
輸入:

0 0 0
0 1 0
0 0 0

輸出:

0 0 0
0 1 0
0 0 0

示例 2:
輸入:

0 0 0
0 1 0
1 1 1

輸出:

0 0 0
0 1 0
1 2 1

注意:

給定矩陣的元素個(gè)數(shù)不超過 10000。
給定矩陣中至少有一個(gè)元素是 0。
矩陣中的元素只在四個(gè)方向上相鄰: 上、下、左、右。

C++代碼

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        queue<pair<int,int>> que;
        //將矩陣中所有的0 坐標(biāo)入列， 將所有的1設(shè)置為INT_MAX
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++)
                if(matrix[i][j]==0) que.push(make_pair(i,j));
                else if(matrix[i][j]==1) matrix[i][j] = INT_MAX;
        }
        
        //循環(huán)直到隊(duì)列為空
        while(!que.empty()){
            auto q = que.front(); //將隊(duì)列的首元素取出來(lái)
            que.pop(); //隊(duì)首出列
            vector<pair<int,int>> dirs ={{0,1},{0,-1},{1,0},{-1,0}}; //四個(gè)方向的坐標(biāo)
            //對(duì)四個(gè)方向進(jìn)行嘗試
            for(auto dir : dirs){
                //計(jì)算新的坐標(biāo)
                int x = q.first + dir.first;
                int y = q.second + dir.second;
                //如果x，y超過邊界 或者 x y的數(shù)值比當(dāng)前小 則不用更新
                if(x<0 || x>matrix.size()-1 || y<0 || y>matrix[0].size()-1 || matrix[x][y]<= matrix[q.first][q.second]) continue;
                //更新當(dāng)前位置的 數(shù)據(jù) ?？梢岳斫鉃樯疃?                matrix[x][y] = matrix[q.first][q.second] + 1;
                //將更新后的點(diǎn)存入隊(duì)列
                que.push({x,y});
            }
        }
        return matrix;
    }
};

體會(huì)

這個(gè)題，開始我嘗試用dfs去解答，如果使用dfs，需要遍歷每一個(gè)為1的點(diǎn)，非常耗時(shí)間，最終超時(shí)了。這個(gè)中周圍距離的題目，使用bfs是更好的方式。
bfs的思路是逐層更新，首先我們將所有的1都改為無(wú)窮大。從一個(gè)0開始，逐層向外更新，每次只考慮周圍的四個(gè)節(jié)點(diǎn)，如果目標(biāo)節(jié)點(diǎn)的值大于源節(jié)點(diǎn)的值，就證明我們給目標(biāo)節(jié)點(diǎn)找到了一條更短的路，我們更新目標(biāo)節(jié)點(diǎn)，否則目標(biāo)節(jié)點(diǎn)保持不變。bfs需要使用隊(duì)列進(jìn)行存儲(chǔ)，先將所有的0入列，作為起點(diǎn)，之后每次更新過的節(jié)點(diǎn)都要入列，用來(lái)實(shí)現(xiàn)祝層向外的效果。

給一個(gè)DFS超時(shí)的代碼 T.T

void dfs(vector<vector<int>> &matrix,vector<vector<bool>> visited,int depth,int x,int y,int src_x,int src_y){
    if(x>matrix.size()-1 || x<0 || y>matrix[0].size()-1 ||y<0 || visited[x][y]) return;
    if(matrix[x][y]==0) {
        if(depth<matrix[src_x][src_y]) matrix[src_x][src_y] = depth;
        visited[x][y]= false;
        return;
    }
    visited[x][y]= true;
    dfs(matrix,visited,depth+1,x,y+1,src_x,src_y);
    dfs(matrix,visited,depth+1,x,y-1,src_x,src_y);
    dfs(matrix,visited,depth+1,x+1,y,src_x,src_y);
    dfs(matrix,visited,depth+1,x-1,y,src_x,src_y);

}

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {

    vector<vector<bool>> visited(matrix.size(),vector<bool>(matrix[0].size(),false));

    for(int i=0;i<matrix.size();i++)
        for(int j=0;j<matrix[0].size();j++)
            if(matrix[i][j]==1) matrix[i][j]=INT_MAX;

    for(int i=0;i<matrix.size();i++)
        for(int j=0;j<matrix[0].size();j++) {
            dfs(matrix, visited, 0, i, j, i, j);
        }
    return matrix;
}

LeetCode529 掃雷游戲

題目

讓我們一起來(lái)玩掃雷游戲！

給定一個(gè)代表游戲板的二維字符矩陣。 'M' 代表一個(gè)未挖出的地雷，'E' 代表一個(gè)未挖出的空方塊，'B' 代表沒有相鄰（上，下，左，右，和所有4個(gè)對(duì)角線）地雷的已挖出的空白方塊，數(shù)字（'1' 到 '8'）表示有多少地雷與這塊已挖出的方塊相鄰，'X' 則表示一個(gè)已挖出的地雷。

現(xiàn)在給出在所有未挖出的方塊中（'M'或者'E'）的下一個(gè)點(diǎn)擊位置（行和列索引），根據(jù)以下規(guī)則，返回相應(yīng)位置被點(diǎn)擊后對(duì)應(yīng)的面板：

如果一個(gè)地雷（'M'）被挖出，游戲就結(jié)束了- 把它改為 'X'。
如果一個(gè)沒有相鄰地雷的空方塊（'E'）被挖出，修改它為（'B'），并且所有和其相鄰的方塊都應(yīng)該被遞歸地揭露。
如果一個(gè)至少與一個(gè)地雷相鄰的空方塊（'E'）被挖出，修改它為數(shù)字（'1'到'8'），表示相鄰地雷的數(shù)量。
如果在此次點(diǎn)擊中，若無(wú)更多方塊可被揭露，則返回面板。

示例 1:

輸入: 

[['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'M', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E'],
 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

輸出: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

示例 2:

輸入: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'M', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

Click : [1,2]

輸出: 

[['B', '1', 'E', '1', 'B'],
 ['B', '1', 'X', '1', 'B'],
 ['B', '1', '1', '1', 'B'],
 ['B', 'B', 'B', 'B', 'B']]

注意:

輸入矩陣的寬和高的范圍為 [1,50]。
點(diǎn)擊的位置只能是未被挖出的方塊 ('M' 或者 'E')，這也意味著面板至少包含一個(gè)可點(diǎn)擊的方塊。
輸入面板不會(huì)是游戲結(jié)束的狀態(tài)（即有地雷已被挖出）。
簡(jiǎn)單起見，未提及的規(guī)則在這個(gè)問題中可被忽略。例如，當(dāng)游戲結(jié)束時(shí)你不需要挖出所有地雷，考慮所有你可能贏得游戲或標(biāo)記方塊的情況。

C++代碼

class Solution {
public:
    void dfs(vector<vector<char>>& board,vector<int> click){
        int x = click[0];
        int y = click[1];
        int width = board[0].size();
        int height = board.size();
        //周圍八個(gè)格子的坐標(biāo)
        vector<pair<int,int>> dirs ={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        if(x<0 || x>height-1 || y<0 || y>width-1) return;
        int mine_count = 0;
        遍歷周圍八個(gè)格子同時(shí)記錄雷的個(gè)數(shù)
        for( auto dir : dirs){
            int x_new = x+dir.first;
            int y_new = y+dir.second;
            if(x_new<0 || x_new>height-1 || y_new<0 || y_new>width-1) continue;
            if(board[x_new][y_new] == 'M' || board[x_new][y_new] == 'X' ) mine_count++;
        }
        //如果雷的個(gè)數(shù)不為0 這個(gè)位置填上雷的個(gè)數(shù)
        if(mine_count!=0) board[x][y] = mine_count +'0';
        else { //否則這個(gè)位置填上 B 并繼續(xù)dfs
            board[x][y] = 'B';
            for(auto dir :dirs){
                int new_x = x + dir.first;
                int new_y = y +dir.second;
                if(new_x>=0 && new_x<height && new_y>=0 && new_y<width && board[new_x][new_y]=='E') //如果即將遍歷的點(diǎn)是 E 才遍歷，如果是B證明遍歷過了，防止死循環(huán)
                    dfs(board,{x+dir.first,y+dir.second});
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if(board[click[0]][click[1]]=='M') board[click[0]][click[1]]='X';
        else dfs(board,click);
        return board;
    }
};

體會(huì)

比較經(jīng)典的體會(huì)，dfs算法完成掃雷。從給定的點(diǎn)開始dfs遍歷，每到打一個(gè)新點(diǎn)，檢查周圍八個(gè)位置的雷的個(gè)數(shù)，如果雷的個(gè)數(shù)不為0，這個(gè)點(diǎn)設(shè)置為數(shù)字，否則這個(gè)點(diǎn)就是B。如果這個(gè)點(diǎn)是B則繼續(xù)dfs周圍的八個(gè)點(diǎn)，搜索的時(shí)候要注意 下一個(gè)點(diǎn)是E才搜索，不然會(huì)陷入死循環(huán)。

LeetCode547 朋友圈

題目

班上有 N 名學(xué)生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我們可以認(rèn)為 A 也是 C 的朋友。所謂的朋友圈，是指所有朋友的集合。

給定一個(gè) N * N 的矩陣 M，表示班級(jí)中學(xué)生之間的朋友關(guān)系。如果M[i][j] = 1，表示已知第 i 個(gè)和 j 個(gè)學(xué)生互為朋友關(guān)系，否則為不知道。你必須輸出所有學(xué)生中的已知的朋友圈總數(shù)。

示例 1:

輸入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
輸出: 2 
說(shuō)明：已知學(xué)生0和學(xué)生1互為朋友，他們?cè)谝粋€(gè)朋友圈。
第2個(gè)學(xué)生自己在一個(gè)朋友圈。所以返回2。

示例 2:

輸入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
輸出: 1
說(shuō)明：已知學(xué)生0和學(xué)生1互為朋友，學(xué)生1和學(xué)生2互為朋友，所以學(xué)生0和學(xué)生2也是朋友，所以他們?nèi)齻€(gè)在一個(gè)朋友圈，返回1。

注意：

N 在[1,200]的范圍內(nèi)。
對(duì)于所有學(xué)生，有M[i][i] = 1。
如果有M[i][j] = 1，則有M[j][i] = 1。

C++代碼

class Solution {
public:
    int dfs(vector<vector<int>> M, vector<bool> &visited, int p) {
        if(visited[p]) return 0; //如果當(dāng)前節(jié)點(diǎn)被訪問過 直接結(jié)束
        else {
            visited[p] = true; //將當(dāng)前節(jié)點(diǎn)標(biāo)記為訪問過
            int count =1;
            for (int i = 0; i < M.size(); i++) {//遍歷 找到當(dāng)前這個(gè)人的朋友
                if (M[p][i] == 1 && !visited[i] && i != p) { //如果M數(shù)組值為1 且這個(gè)人不是自己 就是朋友
                    count += dfs(M, visited, i); //接著找朋友
                }
            }
            return count; //最后返回一共找了幾次朋友 雖然并不需要這個(gè)值 只要有朋友就可以了
        }
    }
    int findCircleNum(vector<vector<int>>& M) {
        int py = 0; //朋友圈的個(gè)數(shù)
        vector<bool> visited(M.size(), false);//初始化一個(gè)visited數(shù)組 用于記錄訪問的情況
        for(int i=0;i<M.size();i++)
            if(dfs(M,visited,i)) py++;//如果dfs的結(jié)果不是0，證明存在朋友圈。
        return py;
    }
};

體會(huì)

題目挺經(jīng)典的，一道dfs無(wú)回溯題目。將這個(gè)題目仔細(xì)解讀一下，就可以發(fā)現(xiàn)我們需要求朋友關(guān)系圖中的連通分量。采用dfs算法，對(duì)每一個(gè)人都進(jìn)行搜索，如果找到了朋友，就把朋友作為起點(diǎn)繼續(xù)搜索。使用visited數(shù)組記錄每個(gè)人被訪問的狀態(tài)。dfs返回值為int，只要存在朋友圈，返回值就不為0，否則返回0，證明沒有找到朋友圈。

LeetCode576 出界的路徑數(shù)

題目

給定一個(gè) m × n 的網(wǎng)格和一個(gè)球。球的起始坐標(biāo)為 (i,j) ，你可以將球移到相鄰的單元格內(nèi)，或者往上、下、左、右四個(gè)方向上移動(dòng)使球穿過網(wǎng)格邊界。但是，你最多可以移動(dòng) N 次。找出可以將球移出邊界的路徑數(shù)量。答案可能非常大，返回 結(jié)果 mod 109 + 7 的值。

示例 1：

輸入: m = 2, n = 2, N = 2, i = 0, j = 0
輸出: 6

示例 2：

輸入: m = 1, n = 3, N = 3, i = 0, j = 1
輸出: 12

說(shuō)明:

球一旦出界，就不能再被移動(dòng)回網(wǎng)格內(nèi)。
網(wǎng)格的長(zhǎng)度和高度在 [1,50] 的范圍內(nèi)。
N 在 [0,50] 的范圍內(nèi)。

C++代碼

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        vector<vector<vector<int>>> dp(N+1,vector<vector<int>>(m,vector<int>(n,0))); //新建一個(gè)dp數(shù)組
        //dp[k][i][j]表示剩余k步時(shí)，起點(diǎn)在[i,j]時(shí)的出度數(shù)
        for(int k=1;k<=N;k++){
            for(int x=0;x<m;x++){
                for(int y=0;y<n;y++){
                    long long v1,v2,v3,v4;
                    if(x==0)   v1=1;else v1 = dp[k-1][x-1][y]; //沒有到達(dá)最頂 就向上移動(dòng)一位
                    if(x==m-1) v2=1;else v2 = dp[k-1][x+1][y]; //沒有到達(dá)最底 就向下移動(dòng)一位
                    if(y==0)   v3=1;else v3 = dp[k-1][x][y-1]; //沒有到達(dá)最左 就向左移動(dòng)一位
                    if(y==n-1) v4=1;else v4 = dp[k-1][x][y+1]; //沒有到達(dá)最右 就向右移動(dòng)一位
                    dp[k][x][y] = (v1+v2+v3+v4)%1000000007;//dp[k][i][j] 講就是將四個(gè)方向的出度進(jìn)行求和
                }
            }
        }
        return dp[N][i][j];
    }
};

體會(huì)

這個(gè)題其實(shí)不是搜索題，是一道DP題。我也寫了一份暴搜的代碼，運(yùn)行沒問題，但是肯定會(huì)超時(shí)。底下有這份代碼。
DP的思路就是將大問題劃分為小問題，列出狀態(tài)轉(zhuǎn)移方程。這道題 問題[k][i][j]：表示剩余k步時(shí)，起點(diǎn)在[i,j]的出屆數(shù)，這個(gè)問題可以轉(zhuǎn)化為 剩余k-1步，起點(diǎn)[i,j]四個(gè)方向各點(diǎn)出屆數(shù)的和。所以狀態(tài)轉(zhuǎn)移方程 dp[k][i][j] = dp[k-1][i-1][j] + dp[k-1][i+1][j] + dp[k-1][i][j-1] + dp[k-1][i][j+1]，編程實(shí)現(xiàn)即可。

附：暴搜代碼：

int res = 0;
int findPaths(int m, int n, int N, int i, int j) {
    dfs(m,n,N,i,j,0);
    return res;
}
void dfs(int m,int n,int N,int i, int j,int now){
    if(i<0 || i>m-1 || j<0 || j>n-1){
        res ++;
        return;
    }
    if(now == N) return;
    dfs(m,n,N,i+1,j,now+1);
    dfs(m,n,N,i-1,j,now+1);
    dfs(m,n,N,i,j+1,now+1);
    dfs(m,n,N,i,j-1,now+1);
}

LeetCode721 賬戶合并

題目

給定一個(gè)列表 accounts，每個(gè)元素 accounts[i] 是一個(gè)字符串列表，其中第一個(gè)元素 accounts[i][0] 是 名稱 (name)，其余元素是 emails 表示該帳戶的郵箱地址。

現(xiàn)在，我們想合并這些帳戶。如果兩個(gè)帳戶都有一些共同的郵件地址，則兩個(gè)帳戶必定屬于同一個(gè)人。請(qǐng)注意，即使兩個(gè)帳戶具有相同的名稱，它們也可能屬于不同的人，因?yàn)槿藗兛赡芫哂邢嗤拿Q。一個(gè)人最初可以擁有任意數(shù)量的帳戶，但其所有帳戶都具有相同的名稱。

合并帳戶后，按以下格式返回帳戶：每個(gè)帳戶的第一個(gè)元素是名稱，其余元素是按順序排列的郵箱地址。accounts 本身可以以任意順序返回。

例子 1:

Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation: 
  第一個(gè)和第三個(gè) John 是同一個(gè)人，因?yàn)樗麄冇泄餐碾娮余]件 "johnsmith@mail.com"。 
  第二個(gè) John 和 Mary 是不同的人，因?yàn)樗麄兊碾娮余]件地址沒有被其他帳戶使用。
  我們可以以任何順序返回這些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
  ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然會(huì)被接受。

注意：

accounts的長(zhǎng)度將在[1，1000]的范圍內(nèi)。
accounts[i]的長(zhǎng)度將在[1，10]的范圍內(nèi)。
accounts[i][j]的長(zhǎng)度將在[1，30]的范圍內(nèi)。

C++代碼

class Solution {
public:
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    map<string,string> root;
    map<string,string> owner;
    map<string,set<string>> m;
    vector<vector<string>> res;

    //初始化root 與 owner，開始時(shí) 每一個(gè)元素都是自己的根節(jié)點(diǎn)
    for(int i=0;i<accounts.size();i++){
        for(int j=0;j<accounts[i].size();j++){
            root[accounts[i][j]] = accounts[i][j];
            owner[accounts[i][j]] =accounts[i][0];
        }
    }
    
    //連接同源節(jié)點(diǎn)
    for(int i=0;i<accounts.size();i++){
        string tmp = find(accounts[i][1],root);
        for(int j=2;j<accounts[i].size();j++){
            root[find(accounts[i][j],root)] = tmp;
        }
    }
    
    //根據(jù)root制作m，m中的每一個(gè)元是一個(gè)獨(dú)立樹
    for(int i=0;i<accounts.size();i++){
        for(int j=1;j<accounts[i].size();j++)
            m[find(accounts[i][j],root)].insert(accounts[i][j]);
    }
    
    //通過m得到最后res
    for(auto key : m){
        vector<string> one(key.second.begin(), key.second.end());
        one.insert(one.begin(),owner[key.first]);
        res.push_back(one);
    }

    return res;
}
    //遞歸查詢根節(jié)點(diǎn)
    string find(string str,map<string,string>&root){
        if(str == root[str])
            return str;
        else return find(root[str],root);
    }
};

體會(huì)

這個(gè)題還是值得一講的。這是一道運(yùn)用并查集的題型。最小生成樹、親戚關(guān)系的判定、確定無(wú)向圖的連通子圖個(gè)數(shù)、最小公共祖先問題等，都要用到并查集。我們將題目給的樣例簡(jiǎn)化成如下，進(jìn)行講解。

J:A B
J:C
J:B D
M:E

首先，初始化root owner。初始化的root中 每一個(gè)節(jié)點(diǎn)都是自己的根節(jié)點(diǎn).

root:        owner:        m:
A:A          A:J
B:B          B:J
C:C          C:J
D:D          D:J
E:E          E:M 

根據(jù)account連接同源節(jié)點(diǎn)得到

root:        owner:        m:
A:A          A:J
B:A          B:J
C:C          C:J
D:A          D:J
E:E          E:M 

可以看到，現(xiàn)在的root中，非源節(jié)點(diǎn)的節(jié)點(diǎn)已經(jīng)連接到了其源節(jié)點(diǎn)。這個(gè)效果來(lái)自于find的遞歸查詢。
通過root建立m

root:        owner:        m:
A:A          A:J           A:ABD
B:A          B:J           C:C
C:C          C:J           E:E
D:A          D:J
E:E          E:M 

源節(jié)點(diǎn)相同的節(jié)點(diǎn)已經(jīng)形成了一棵樹。
通過m與owner便可構(gòu)建出最后的答案。

LeetCode743 網(wǎng)絡(luò)延遲時(shí)

題目

有 N 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，標(biāo)記為 1 到 N。

給定一個(gè)列表 times，表示信號(hào)經(jīng)過有向邊的傳遞時(shí)間。 times[i] = (u, v, w)，其中 u 是源節(jié)點(diǎn)，v 是目標(biāo)節(jié)點(diǎn)， w 是一個(gè)信號(hào)從源節(jié)點(diǎn)傳遞到目標(biāo)節(jié)點(diǎn)的時(shí)間。

現(xiàn)在，我們向當(dāng)前的節(jié)點(diǎn) K 發(fā)送了一個(gè)信號(hào)。需要多久才能使所有節(jié)點(diǎn)都收到信號(hào)？如果不能使所有節(jié)點(diǎn)收到信號(hào)，返回 -1。

注意:

N 的范圍在 [1, 100] 之間。
K 的范圍在 [1, N] 之間。
times 的長(zhǎng)度在 [1, 6000] 之間。
所有的邊 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 1 <= w <= 100。

C++代碼

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        queue<int> q;
        vector<int> each_time(N+1,INT_MAX); //each_time表示從K到每個(gè)節(jié)點(diǎn)的最短距離，初始化為INT_MAX
        each_time[K] = 0; //到自己的距離為0
        each_time[0] = 0; //0不存在 置為0
        //隊(duì)列模擬bfs算法
        q.push(K);
        while(!q.empty()){
            int curr = q.front();
            for(auto i:times){
                //如果 目標(biāo)節(jié)點(diǎn)的值 大于 當(dāng)前節(jié)點(diǎn)+當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑 就更新目標(biāo)節(jié)點(diǎn)，并把目標(biāo)節(jié)點(diǎn)放入隊(duì)列
                if(curr == i[0] && each_time[i[1]]>each_time[i[0]]+i[2])
                {
                    q.push(i[1]);
                    each_time[i[1]] = each_time[i[0]] + i[2];
                }
            }
            q.pop();
        }
        int ans=0;
        //從所有的最短路徑中 找出最大的
        for(auto a: each_time){
            ans = max(a,ans);
        }
        return (ans == INT_MAX) ? -1 : ans; //輸出-1還是輸出最大值
    }
};

體會(huì)

本題題目可以化簡(jiǎn)為求單源最短路徑中的最大值。我們可以使用Dijkstra算法求出單源最短路徑，再求最大值，但是這樣速度比較慢。這個(gè)題我采用BFS算法，速度要快一些。思路很簡(jiǎn)單，初始節(jié)點(diǎn)入隊(duì)列，在 times 中查找初始節(jié)點(diǎn)的目標(biāo)節(jié)點(diǎn)，并對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行更新。//如果目標(biāo)節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)+路徑長(zhǎng)度就更新目標(biāo)節(jié)點(diǎn)，并把目標(biāo)節(jié)點(diǎn)放入隊(duì)列。這個(gè)思路跟Dijkstra是一樣的。最后輸出所有最短路徑中的最大值就可以，輸出時(shí)注意判斷是否有解。

LeetCode785 判斷二分圖

題目

給定一個(gè)無(wú)向圖graph，當(dāng)這個(gè)圖為二分圖時(shí)返回true。

如果我們能將一個(gè)圖的節(jié)點(diǎn)集合分割成兩個(gè)獨(dú)立的子集A和B，并使圖中的每一條邊的兩個(gè)節(jié)點(diǎn)一個(gè)來(lái)自A集合，一個(gè)來(lái)自B集合，我們就將這個(gè)圖稱為二分圖。

graph將會(huì)以鄰接表方式給出，graph[i]表示圖中與節(jié)點(diǎn)i相連的所有節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都是一個(gè)在0到graph.length-1之間的整數(shù)。這圖中沒有自環(huán)和平行邊： graph[i] 中不存在i，并且graph[i]中沒有重復(fù)的值。

示例 1:

輸入: [[1,3], [0,2], [1,3], [0,2]]
輸出: true
解釋: 
無(wú)向圖如下:
0----1
|    |
|    |
3----2
我們可以將節(jié)點(diǎn)分成兩組: {0, 2} 和 {1, 3}。

示例 2:

輸入: [[1,2,3], [0,2], [0,1,3], [0,2]]
輸出: false
解釋: 
無(wú)向圖如下:
0----1
| \  |
|  \ |
3----2
我們不能將節(jié)點(diǎn)分割成兩個(gè)獨(dú)立的子集。

注意:

graph 的長(zhǎng)度范圍為 [1, 100]。
graph[i] 中的元素的范圍為 [0, graph.length - 1]。
graph[i] 不會(huì)包含 i 或者有重復(fù)的值。
圖是無(wú)向的: 如果j 在 graph[i]里邊, 那么 i 也會(huì)在 graph[j]里邊。

C++代碼

class Solution {
public:
    bool dfs(vector<vector<int>>& graph,vector<int> &color,int pos,int c){
        color [pos] =c;//將當(dāng)前點(diǎn)的顏色標(biāo)記為 c
        for(int i=0;i<graph[pos].size();i++){ //尋找當(dāng)前點(diǎn)的鄰居
            if(color[graph[pos][i]] == c) return false; //如果當(dāng)前點(diǎn)的鄰居的顏色也是c 則證明重復(fù) 返回
            if(color[graph[pos][i]] == 0 && !dfs(graph,color,graph[pos][i],-c)) return false; //如果該鄰居的還沒上色 則給他上-c色，dfs下去，如果全部上色成功，則返回true
        }
        return true;
    }
    bool isBipartite(vector<vector<int>>& graph) {
        vector<int> color(graph.size(),0);
        //遍歷所有節(jié)點(diǎn) 防止出現(xiàn)圖不連通的情況
        for(int i=0;i<graph.size();i++){
            if(color[i] == 0){
                //如果當(dāng)前點(diǎn)沒有上色，則從該點(diǎn)開始上色 初始顏色為1
                if(!dfs(graph,color,i,1)){
                    return false;
                }
            }
        }
        return true;
    }
};

體會(huì)

判斷二分圖，我們利用染色的方式來(lái)解決。使用dfs，對(duì)每一個(gè)節(jié)點(diǎn)先染上C色，判斷他的鄰居節(jié)點(diǎn)，如果顏色也是C，證明沖突，返回false；如果鄰居節(jié)點(diǎn)沒有染色，則嘗試給鄰居染上-c色，逐層dfs，如果全部染色成功，返回true。
注意，這個(gè)題需要對(duì)所有的節(jié)點(diǎn)都嘗試dfs，因?yàn)椴皇敲恳唤M輸入的圖都是連通的。

LeetCode841 鑰匙和房間

題目

有 N 個(gè)房間，開始時(shí)你位于 0 號(hào)房間。每個(gè)房間有不同的號(hào)碼：0，1，2，...，N-1，并且房間里可能有一些鑰匙能使你進(jìn)入下一個(gè)房間。

在形式上，對(duì)于每個(gè)房間 i 都有一個(gè)鑰匙列表 rooms[i]，每個(gè)鑰匙 rooms[i][j] 由 [0,1，...，N-1] 中的一個(gè)整數(shù)表示，其中 N = rooms.length。 鑰匙 rooms[i][j] = v 可以打開編號(hào)為 v 的房間。

最初，除 0 號(hào)房間外的其余所有房間都被鎖住。

你可以自由地在房間之間來(lái)回走動(dòng)。

如果能進(jìn)入每個(gè)房間返回 true，否則返回 false。

示例 1：

輸入: [[1],[2],[3],[]]
輸出: true
解釋:  
我們從 0 號(hào)房間開始，拿到鑰匙 1。
之后我們?nèi)?1 號(hào)房間，拿到鑰匙 2。
然后我們?nèi)?2 號(hào)房間，拿到鑰匙 3。
最后我們?nèi)チ?3 號(hào)房間。
由于我們能夠進(jìn)入每個(gè)房間，我們返回 true。

示例 2：

輸入：[[1,3],[3,0,1],[2],[0]]
輸出：false
解釋：我們不能進(jìn)入 2 號(hào)房間。

提示：

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房間中的鑰匙數(shù)量總計(jì)不超過 3000。

C++代碼

class Solution {
public:
    void dfs(vector<vector<int>> &rooms,vector<int> &visited,int room){
        if(visited[room]) return; //如果當(dāng)前節(jié)點(diǎn)被訪問 就返回
        visited[room] = 1; //將當(dāng)前節(jié)點(diǎn)設(shè)置為訪問
        for(int i=0;i<rooms[room].size();i++){ //遍歷當(dāng)前節(jié)點(diǎn)的鄰居
            dfs(rooms,visited,rooms[room][i]);
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<int> visited(rooms.size(),0); //建立一個(gè)visited數(shù)組
        dfs(rooms,visited,0); //從0點(diǎn)開始查詢
        if(find(visited.begin(),visited.end(),0)==visited.end()) return true; //如果所有的節(jié)點(diǎn)都被訪問了 就返回true 反之false
        else return false;
    }
};

體會(huì)

經(jīng)典dfs無(wú)回溯題目，直接按思路寫就可以，沒有難度。具體內(nèi)容請(qǐng)看注釋。當(dāng)我看到通過率時(shí)46.6%時(shí)，我就感覺可以1A了。哈哈哈哈哈

LeetCode207 課程表

題目

現(xiàn)在你總共有 n 門課需要選，記為 0 到 n-1。

在選修某些課程之前需要一些先修課程。 例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個(gè)匹配來(lái)表示他們: [0,1]

給定課程總量以及它們的先決條件，判斷是否可能完成所有課程的學(xué)習(xí)？

示例 1:

輸入: 2, [[1,0]] 
輸出: true
解釋: 總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0。所以這是可能的。

示例 2:

輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成?課程 0；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1。這是不可能的。

說(shuō)明:

輸入的先決條件是由邊緣列表表示的圖形，而不是鄰接矩陣。詳情請(qǐng)參見圖的表示法。
你可以假定輸入的先決條件中沒有重復(fù)的邊。
提示:

這個(gè)問題相當(dāng)于查找一個(gè)循環(huán)是否存在于有向圖中。如果存在循環(huán)，則不存在拓?fù)渑判?，因此不可能選取所有課程進(jìn)行學(xué)習(xí)。
通過 DFS 進(jìn)行拓?fù)渑判?- 一個(gè)關(guān)于Coursera的精彩視頻教程（21分鐘），介紹拓?fù)渑判虻幕靖拍睢?br> 拓?fù)渑判蛞部梢酝ㄟ^ BFS 完成。

C++代碼

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        map<int,vector<int>> linkGraph;
        vector<int> in(numCourses,0);
        vector<int> out(numCourses,0);
        vector<int> visited(numCourses,0);
        //構(gòu)造圖的鄰接表
        for(auto p:prerequisites){
            linkGraph[p.first].push_back(p.second);
            in[p.second]++;
            out[p.first]++;
        }
        queue<int> que;

        //將所有入度為0的點(diǎn) 放入隊(duì)列中
        for(int i=0;i<in.size();i++)
            if(in[i]==0) que.push(i);

        while(!que.empty()){
            int tmp = que.front(); // 去除隊(duì)列首元素
            que.pop();
            for(auto i : linkGraph[tmp]){ //刪除該節(jié)點(diǎn) 要將與其連接的節(jié)點(diǎn)的入度都-1
                in[i]--;
                if(in[i]==0){ //如果入度為0 添加進(jìn)隊(duì)列
                    que.push(i);
                }
            }
        }
        if(*max_element(in.begin(),in.end())==0) return true; //入度全為0 證明 環(huán)
        else return false;
    }
};

體會(huì)

這一份應(yīng)該是網(wǎng)上本題最清晰簡(jiǎn)單的解法了?？疾焱?fù)渑判?，第一次坐到這個(gè)問題。去一個(gè)圖是否是拓?fù)淇膳诺姆椒ň蛢煞N，DFS每次刪去出度為0的節(jié)點(diǎn)，BFS每次刪去入度為0的節(jié)點(diǎn)，最終判斷是否所有的出度/入度都為0，如果都為0，證明無(wú)環(huán)，拓?fù)淇膳拧?br> 思路：將邊緣列表轉(zhuǎn)換為臨接表，同是記錄下每一個(gè)節(jié)點(diǎn)的入度。
將所有入度為0的節(jié)點(diǎn)，入隊(duì)。
每次取出隊(duì)首元素，刪除它，將其連接節(jié)點(diǎn)的入度-1，如果入度為0的話，放入隊(duì)列中，重復(fù)此過程。
最后判斷所有的入度是否都是0，都是則無(wú)環(huán)，輸出。