偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

一篇學(xué)會檢測循環(huán)依賴

開發(fā) 前端
現(xiàn)有n個編譯項,編號為0 ~ n-1。給定一個二維數(shù)組,表示編譯項之間有依賴關(guān)系。如[0, 1]表示1依賴于0。若存在循環(huán)依賴則返回空;不存在依賴則返回可行的編譯順序。

[[396795]]

本文轉(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)依賴;有的則要求給出一個可行的順序。

解決這類問題的利器就是——拓撲排序。

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

你很快就能掌握拓撲排序的寫法。

題目描述

現(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]等。

拓撲排序可以求這樣的一個序列??梢钥闯?,這個序列結(jié)果可能不唯一。

拓撲排序算法過程:

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

用下圖舉個例子,看看拓撲排序算法的過程。res用于存儲結(jié)果序列。

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

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

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

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

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

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

最終,res存儲的就是拓撲排序的結(jié)果,即題目中的可行編譯順序。

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

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

按照拓撲排序的算法,找到入度為0的點0存下來,然后刪除。

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

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

這就是拓撲排序算法。

代碼實現(xiàn)應(yīng)該就很好理解了~我們借助BFS來實現(xiàn)拓撲排序,隊列中存儲入度為0的點。

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

如果你感覺拓撲排序沒問題了,去嘗試做Leetcode210. 課程表 II吧~

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

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

參考代碼

C++ 版本

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

Python 版本

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

 

 

責任編輯:武曉燕 來源: 一個搬磚的胖子
相關(guān)推薦

2024-04-15 08:17:21

Spring依賴注入循環(huán)依賴

2022-01-02 08:43:46

Python

2022-11-09 11:02:00

2022-02-07 11:01:23

ZooKeeper

2021-07-02 09:45:29

MySQL InnoDB數(shù)據(jù)

2021-07-06 08:59:18

抽象工廠模式

2023-01-03 08:31:54

Spring讀取器配置

2021-07-05 22:11:38

MySQL體系架構(gòu)

2021-05-11 08:54:59

建造者模式設(shè)計

2022-08-26 09:29:01

Kubernetes策略Master

2022-08-23 08:00:59

磁盤性能網(wǎng)絡(luò)

2023-11-28 08:29:31

Rust內(nèi)存布局

2021-09-28 08:59:30

復(fù)原IP地址

2021-10-14 10:22:19

逃逸JVM性能

2022-04-12 08:30:52

回調(diào)函數(shù)代碼調(diào)試

2021-07-16 22:43:10

Go并發(fā)Golang

2023-03-13 21:38:08

TCP數(shù)據(jù)IP地址

2021-10-27 09:59:35

存儲

2022-10-20 07:39:26

2023-11-01 09:07:01

Spring裝配源碼
點贊
收藏

51CTO技術(shù)棧公眾號