日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
一篇學(xué)會檢測循環(huán)依賴

本文轉(zhuǎn)載自微信公眾號「一個搬磚的胖子」，作者一個搬磚的胖子。轉(zhuǎn)載本文請聯(lián)系一個搬磚的胖子公眾號。

前言

今天為CodeTop補充的題目是檢測循環(huán)依賴。

來看一下幾篇面經(jīng)的原文敘述

  • 循環(huán)依賴檢測。如，[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false，[['A', 'B'], ['B', 'C'], ['C', 'A']] => true(2021.4 字節(jié)跳動-幸福里-后端)[2]
  • 手撕代碼：小王寫了一個makefile，其中有n個編譯項編號為0~n-1，他們互相之間有依賴關(guān)系。請寫一個程序解析依賴，給出一個可行的編譯順序。(2021.03 字節(jié)跳動-系統(tǒng)部-后端)[3]

有的面試官要求判斷是否有循環(huán)依賴;有的則要求給出一個可行的順序。

解決這類問題的利器就是——拓?fù)渑判颉?/p>

只要你會BFS，會層次遍歷二叉樹。

你很快就能掌握拓?fù)渑判虻膶懛ā?/p>

題目描述

現(xiàn)有n個編譯項，編號為0 ~ n-1。給定一個二維數(shù)組，表示編譯項之間有依賴關(guān)系。如[0, 1]表示1依賴于0。

若存在循環(huán)依賴則返回空;不存在依賴則返回可行的編譯順序。

題目分析

若給定一個依賴關(guān)系是[[0,2],[1,2],[2,3],[2,4]]，如圖所示

可以看出，它們之間不存在循環(huán)依賴。

可行的編譯序列是[0,1,2,3,4]，也可以是[1,0,2,4,3]等。

拓?fù)渑判蚩梢郧筮@樣的一個序列?？梢钥闯觯@個序列結(jié)果可能不唯一。

拓?fù)渑判蛩惴ㄟ^程：

  1. 選擇圖中一個入度為0的點，記錄下來
  2. 在圖中刪除該點和所有以它為起點的邊
  3. 重復(fù)1和2，直到圖為空或沒有入度為0的點。

用下圖舉個例子，看看拓?fù)渑判蛩惴ǖ倪^程。res用于存儲結(jié)果序列。

圖片入度為0的點有兩個，我們?nèi)芜x一個。比如選擇點0，記錄至res;刪除點0及以它為起點的邊。

然后選擇點1，同樣記錄下來;刪除點1及以它為起點的邊。

入度為0的點現(xiàn)在只有點2，把它記錄下來;刪除點2及以它為起點的邊。

同理。選擇點3，記錄下來;刪除點3及以它為起點的邊。

選擇點4，記錄下來;刪除點4及以它為起點的邊。

圖為空，算法結(jié)束。

最終，res存儲的就是拓?fù)渑判虻慕Y(jié)果，即題目中的可行編譯順序。

如果圖中存在循環(huán)依賴呢?

例如依賴關(guān)系是[[0,1],[1,2],[2,1]，如圖所示。

按照拓?fù)渑判虻乃惴?，找到入度?的點0存下來，然后刪除。

然后就沒有入度為0的點了，算法結(jié)束!

我們發(fā)現(xiàn)，可以使用res.size() == n 來判斷圖中是否有環(huán)。其中，n為點的個數(shù)。

這就是拓?fù)渑判蛩惴ā?/p>

代碼實現(xiàn)應(yīng)該就很好理解了~我們借助BFS來實現(xiàn)拓?fù)渑判颍犃兄写鎯θ攵葹?的點。

下面我提供C++和Python兩個版本的代碼。推薦大家背下來，背一些模板代碼是很有必要的。

如果你感覺拓?fù)渑判驔]問題了，去嘗試做Leetcode210. 課程表 II吧~

PS：之前沒接觸過圖的同學(xué)，可能不太理解參考代碼中存儲圖結(jié)構(gòu)的g。其實很簡單，對于下圖來說。

 
 
 
 
    
  
  
  
  
  1. g = [[2]     #表示0->2 
    2.   
  
  
  
  2.      [2]     #表示1->2 
    3.   
  
  
  
  3.      [3, 4]  #表示2->3,2->4 
    4.   
  
  
  
  4.      []      #表示沒有以3為起點的邊 
    5.   
  
  
  
  5.      []]     #表示沒有以4為起點的邊 
    6.

參考代碼

C++ 版本

 
 
 
 
    
  
  
  
  
  1. vector haveCircularDependency(int n, vector> &prerequisites) { 
    2.   
  
  
  
  2.     vector> g(n); //鄰接表存儲圖結(jié)構(gòu) 
    3.   
  
  
  
  3.     vector indeg(n); //每個點的入度 
    4.   
  
  
  
  4.     vector res; //存儲結(jié)果序列 
    5.   
  
  
  
  5.     for(int i = 0; i < prerequisites.size(); i ++) { 
    6.   
  
  
  
  6.         int a = prerequisites[i][0], b = prerequisites[i][1];  
    7.   
  
  
  
  7.         g[a].push_back(b); 
    8.   
  
  
  
  8.         indeg[b] ++; 
    9.   
  
  
  
  9.     } 
    10.   
  
  
  
  10.     queue q; 
    11.   
  
  
  
  11.     //一次性將入度為0的點全部入隊 
    12.   
  
  
  
  12.     for(int i = 0; i < n; i ++) { 
    13.   
  
  
  
  13.         if(indeg[i] == 0) q.push(i); 
    14.   
  
  
  
  14.     } 
    15.   
  
  
  
  15.     while(q.size()) { 
    16.   
  
  
  
  16.         int t = q.front(); 
    17.   
  
  
  
  17.         q.pop(); 
    18.   
  
  
  
  18.         res.push_back(t); 
    19.   
  
  
  
  19.         //刪除邊時，將終點的入度-1。若入度為0，果斷入隊 
    20.   
  
  
  
  20.         for(int i = 0; i < g[t].size(); i ++) { 
    21.   
  
  
  
  21.             int j = g[t][i]; 
    22.   
  
  
  
  22.             indeg[j] --; 
    23.   
  
  
  
  23.             if(indeg[j] == 0) { 
    24.   
  
  
  
  24.                 q.push(j); 
    25.   
  
  
  
  25.             } 
    26.   
  
  
  
  26.         } 
    27.   
  
  
  
  27.     } 
    28.   
  
  
  
  28.     if(res.size() == n) return res; 
    29.   
  
  
  
  29.     else return {}; 
    30.   
  
  
  
  30. } 
    31.

Python 版本

 
 
 
 
    
  
  
  
  
  1. def haveCircularDependency(self, n: int, prerequisites): 
    2.   
  
  
  
  2.     g = [[]for i in range(n)] #鄰接表存儲圖結(jié)構(gòu) 
    3.   
  
  
  
  3.     indeg = [0 for i in range(n)] #每個點的入度 
    4.   
  
  
  
  4.     res = [] #存儲結(jié)果序列 
    5.   
  
  
  
  5.     q = deque() 
    6.   
  
  
  
  6.     #將依賴關(guān)系加入鄰接表中g(shù)，并各個點入度 
    7.   
  
  
  
  7.     for pre in prerequisites: 
    8.   
  
  
  
  8.         a, b = pre[0], pre[1] 
    9.   
  
  
  
  9.         g[a].append(b) 
    10.   
  
  
  
  10.         indeg[b] += 1 
    11.   
  
  
  
  11.     #一次性將入度為0的點全部入隊 
    12.   
  
  
  
  12.     for i in range(n): 
    13.   
  
  
  
  13.         if indeg[i] == 0: 
    14.   
  
  
  
  14.             q.append(i) 
    15.   
  
  
  
  15.     while q: 
    16.   
  
  
  
  16.         t = q.popleft() 
    17.   
  
  
  
  17.         res.append(t) 
    18.   
  
  
  
  18.         #刪除邊時，將終點的入度-1。若入度為0，果斷入隊 
    19.   
  
  
  
  19.         for j in g[t]: 
    20.   
  
  
  
  20.             indeg[j] -= 1 
    21.   
  
  
  
  21.             if indeg[j] == 0: 
    22.   
  
  
  
  22.                 q.append(j) 
    23.   
  
  
  
  23.     if len(res) == n: 
    24.   
  
  
  
  24.         return res 
    25.   
  
  
  
  25.     else: 
    26.   
  
  
  
  26.         return [] 
    27.

文章名稱：一篇學(xué)會檢測循環(huán)依賴
網(wǎng)頁URL：http://m.5511xx.com/article/coddpsp.html