柚子快報(bào)激活碼778899分享：算法 拓?fù)渑判驅(qū)ｎ}篇

http://yzkb.51969.com/

目錄

前言

課程表

課程表II

課程表IV

火星詞典

前言

拓?fù)渑判蚴侵笇?duì)一個(gè)有向無(wú)環(huán)圖的節(jié)點(diǎn)進(jìn)行排序之后得到的序列，如果存在一條從節(jié)點(diǎn)A指向節(jié)點(diǎn)B的邊，那么在拓?fù)渑判虻男蛄兄泄?jié)點(diǎn)A出現(xiàn)在節(jié)點(diǎn)B的前面。一個(gè)有向無(wú)環(huán)圖可以有一個(gè)或多個(gè)拓?fù)渑判蛐蛄?，但無(wú)向圖或有向圖都不存在拓?fù)渑判颉?/p>

一種常用的拓?fù)渑判蛩惴ㄊ敲看螐挠邢驘o(wú)環(huán)圖中取出一個(gè)入度為0的節(jié)點(diǎn)添加到拓?fù)渑判蛐蛄兄?，然后刪除該節(jié)點(diǎn)及所有以他為起點(diǎn)的邊。重復(fù)這個(gè)步驟，直到圖為空或圖中不存在入度為0的節(jié)點(diǎn)。如果最終圖為空，那么圖是有向無(wú)環(huán)圖，此時(shí)就找到了該圖的一個(gè)拓?fù)渑判蛐蛄?。如果最終圖不為空并且已經(jīng)不存在入度為0的節(jié)點(diǎn)，那么該圖一定有環(huán)。

課程表

題目

思路

首先先建圖，可以采用鄰接矩陣或者鄰接表建圖，解題時(shí)采用鄰接表來(lái)建圖，并統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度，然后掃描所有節(jié)點(diǎn)的入度，將入度尾0的節(jié)點(diǎn)加入到隊(duì)列中，取出隊(duì)頭元素，將該節(jié)點(diǎn)加入數(shù)組中，并將以該節(jié)點(diǎn)為起始點(diǎn)的邊的終點(diǎn)的入度-1，如果有節(jié)點(diǎn)的入度為0，就將該節(jié)點(diǎn)加入隊(duì)列中，最后，如果數(shù)組的大小和課程數(shù)目不相等，說(shuō)明存在環(huán)，不能修完課程；否則能修完課程。

代碼

class Solution {

public:

bool canFinish(int numCourses, vector>& prerequisites) {

vector in(numCourses);

vector> vv(numCourses);

vector v;

for(auto it:prerequisites){

vv[it[1]].push_back(it[0]);

in[it[0]]++;

}

queue q;

for(int i=0;i

if(in[i]==0) q.push(i);

while(!q.empty()){

int ret=q.front();

q.pop();

v.push_back(ret);

for(int x:vv[ret])

if(--in[x]==0)

q.push(x);

}

if(v.size()==numCourses) return true;

else return false;

}

};

課程表II

題目

思路

這道題和上一道題其實(shí)是一樣的，只不過是問題不同而已，解決方法還是首先先建圖，可以采用鄰接矩陣或者鄰接表建圖，解題時(shí)采用鄰接表來(lái)建圖，并統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度，然后掃描所有節(jié)點(diǎn)的入度，將入度尾0的節(jié)點(diǎn)加入到隊(duì)列中，取出隊(duì)頭元素，將該節(jié)點(diǎn)加入數(shù)組中，并將以該節(jié)點(diǎn)為起始點(diǎn)的邊的終點(diǎn)的入度-1，如果有節(jié)點(diǎn)的入度為0，就將該節(jié)點(diǎn)加入隊(duì)列中，最后，如果數(shù)組的大小和課程數(shù)目不相等，說(shuō)明存在環(huán)，不能修完課程；否則能修完課程。

代碼

class Solution {

public:

vector findOrder(int numCourses, vector>& prerequisites) {

unordered_map> hash;

vector in(numCourses);

vector ret;

for(auto it:prerequisites){

hash[it[1]].push_back(it[0]);

in[it[0]]++;

}

queue q;

for(int i=0;i

if(in[i]==0) q.push(i);

while(!q.empty()){

int top=q.front();q.pop();

ret.push_back(top);

for(int x:hash[top])

if(--in[x]==0)

q.push(x);

}

if(ret.size()==numCourses) return ret;

else return {};

}

};

// class Solution {

// public:

// vector findOrder(int numCourses, vector>& prerequisites) {

// vector in(numCourses);

// vector> vv(numCourses);

// vector ret;

// for(auto it:prerequisites){

// vv[it[1]].push_back(it[0]);

// in[it[0]]++;

// }

// queue q;

// for(int i=0;i

// if(in[i]==0) q.push(i);

// while(!q.empty()){

// int top=q.front();q.pop();

// ret.push_back(top);

// for(int x:vv[top])

// if(--in[x]==0)

// q.push(x);

// }

// if(ret.size()==numCourses) return ret;

// else return {};

// }

// };

課程表IV

題目

思路

雖然這道題和前兩道題看起來(lái)是一樣的，但是這道題比前兩道題要難一些，因?yàn)閷?duì)于每一遍掃描到的入度為0的節(jié)點(diǎn)，這些節(jié)點(diǎn)之間是沒有先決條件關(guān)系的，如果還用之前的解法，會(huì)把每一遍掃描到的入度為0的節(jié)點(diǎn)賦予先決條件，因此我們需要使用別的方法。

下面，先使用鄰接表建圖，然后掃描每個(gè)節(jié)點(diǎn)，進(jìn)行深度優(yōu)先遍歷，如果該節(jié)點(diǎn)沒有被遍歷過，則遍歷以該節(jié)點(diǎn)為起始點(diǎn)的所有邊的終點(diǎn)，依舊是判斷該節(jié)點(diǎn)有沒有被遍歷過，如果沒有被遍歷過，則遍歷以該節(jié)點(diǎn)為起始點(diǎn)的所有邊的終點(diǎn)，然后將鄰接矩陣中的起始點(diǎn)到終點(diǎn)的值置為true，然后遍歷所有終點(diǎn)，看是否存在以終點(diǎn)為起始點(diǎn)的點(diǎn)，然后將鄰接矩陣中起始點(diǎn)到終點(diǎn)的終點(diǎn)的值置為isPre[pos][i]=isPre[pos][i]|isPre[x][i]。

代碼

class Solution {

public:

vector checkIfPrerequisite(int numCourses, vector>& prerequisites, vector>& queries) {

vector> edges(numCourses);

vector vis(numCourses,false);

vector> isPre(numCourses,vector(numCourses,false));

for(auto& p:prerequisites)

edges[p[0]].push_back(p[1]);

for(int i=0;i

dfs(edges,isPre,vis,i);

vector res;

for(auto& query:queries)

res.push_back(isPre[query[0]][query[1]]);

return res;

}

void dfs(vector>& edges,vector>& isPre,vector& vis,int pos){

if(vis[pos]) return;

vis[pos]=true;

for(int x:edges[pos]){

dfs(edges,isPre,vis,x);

isPre[pos][x]=true;

for(int i=0;i

isPre[pos][i]=isPre[pos][i]|isPre[x][i];

}

}

};

//chatGpt的答案

// class Solution {

// public:

// vector checkIfPrerequisite(int numCourses, vector>& prerequisites, vector>& queries) {

// vector> adjacencyList(numCourses);

// vector> successors(numCourses);

// vector visited(numCourses, false);

// unordered_map topoOrderIndex; // Store the index of each course in topological order

// queue q;

// // Construct adjacency list and initialize in-degree counts

// vector inDegree(numCourses, 0);

// for (const auto& prerequisite : prerequisites) {

// int course = prerequisite[0];

// int prerequisiteCourse = prerequisite[1];

// adjacencyList[course].push_back(prerequisiteCourse);

// inDegree[prerequisiteCourse]++;

// }

// // Perform topological sort and record the order

// for (int i = 0; i < numCourses; ++i) {

// if (inDegree[i] == 0) {

// q.push(i);

// }

// }

// int topoIndex = 0;

// while (!q.empty()) {

// int current = q.front();

// q.pop();

// topoOrderIndex[current] = topoIndex++;

// for (int successor : adjacencyList[current]) {

// if (--inDegree[successor] == 0) {

// q.push(successor);

// }

// successors[current].push_back(successor);

// }

// }

// // Handle queries

// vector results;

// for (const auto& query : queries) {

// int courseA = query[0];

// int courseB = query[1];

// bool isPrerequisite = dfs(courseA, courseB, successors, visited, topoOrderIndex);

// results.push_back(isPrerequisite);

// fill(visited.begin(), visited.end(), false); // Reset visited for the next query

// }

// return results;

// }

// private:

// bool dfs(int courseA, int courseB, const vector>& successors, vector& visited, const unordered_map& topoOrderIndex) {

// if (courseA == courseB) {

// return true;

// }

// visited[courseA] = true;

// for (int successor : successors[courseA]) {

// if (!visited[successor] && (topoOrderIndex.at(courseA) < topoOrderIndex.at(successor))) {

// if (successor == courseB || dfs(successor, courseB, successors, visited, topoOrderIndex)) {

// return true;

// }

// }

// }

// return false;

// }

// };

火星詞典

題目

思路

這道題的題目首先得看懂，然后解析所有字符串，兩個(gè)字符串滿足前一個(gè)字符串的前n個(gè)字符和后一個(gè)字符串的前n個(gè)字符相同，第一次出現(xiàn)不同字符時(shí)，前一個(gè)字符串的第n+1個(gè)字符的序列小于后一個(gè)字符串的第n+1個(gè)字符的序列，如果第一個(gè)字符串的長(zhǎng)度大于第二個(gè)字符串的長(zhǎng)度，且第一個(gè)字符串的長(zhǎng)度為第二個(gè)字符串長(zhǎng)度的字符和第二個(gè)字符串相等，這樣是不符合題意的，直接返回空串；否則就建立鄰接表，并統(tǒng)計(jì)所有節(jié)點(diǎn)的入度信息，將入度為0的節(jié)點(diǎn)的值加入隊(duì)列，然后取出隊(duì)頭元素，將該節(jié)點(diǎn)加入字符串末尾，并將以該節(jié)點(diǎn)為起始點(diǎn)的邊的終點(diǎn)的入度-1，如果有節(jié)點(diǎn)的入度為0，就將該節(jié)點(diǎn)加入隊(duì)列中，執(zhí)行將該節(jié)點(diǎn)加入字符串末尾，并將以該節(jié)點(diǎn)為起始點(diǎn)的邊的終點(diǎn)的入度-1，如果有節(jié)點(diǎn)的入度為0，就將該節(jié)點(diǎn)加入隊(duì)列中。

最后掃描數(shù)組，如果存在某個(gè)節(jié)點(diǎn)的入度不為0，說(shuō)明存在環(huán)，不能排序，返回空串；否則返回結(jié)果字符串。

代碼

class Solution {

unordered_map> edges;

unordered_map in;

bool flag;

public:

string alienOrder(vector& words) {

for(string s:words)

for(char ch:s)

in[ch]=0;

int n=words.size();

for(int i=0;i

for(int j=i+1;j

helper(words[i],words[j]);

if(flag) return "";

}

queue q;

string s;

for(auto& [a,b]:in){

if(b==0) q.push(a);

}

while(!q.empty()){

int ch=q.front();q.pop();

s+=ch;

for(char c:edges[ch])

if(--in[c]==0)

q.push(c);

}

for(auto& [a,b]:in)

if(b!=0) return "";

return s;

}

void helper(string& s1,string& s2){

int n=min(s1.size(),s2.size());

int i=0;

for(;i

if(s1[i]!=s2[i]){

char a=s1[i],b=s2[i];

if(!edges.count(a) || !edges[a].count(b)){

edges[a].insert(b);

in[b]++;

}

break;

}

if(i==s2.size() && i

flag=true;

}

};

柚子快報(bào)激活碼778899分享：算法 拓?fù)渑判驅(qū)ｎ}篇

http://yzkb.51969.com/

相關(guān)閱讀