柚子快報激活碼778899分享：算法 拓?fù)渑判驅(qū)ｎ}篇
柚子快報激活碼778899分享：算法 拓?fù)渑判驅(qū)ｎ}篇
目錄
前言
課程表
課程表II
課程表IV
火星詞典
前言
拓?fù)渑判蚴侵笇σ粋€有向無環(huán)圖的節(jié)點進(jìn)行排序之后得到的序列，如果存在一條從節(jié)點A指向節(jié)點B的邊，那么在拓?fù)渑判虻男蛄兄泄?jié)點A出現(xiàn)在節(jié)點B的前面。一個有向無環(huán)圖可以有一個或多個拓?fù)渑判蛐蛄?，但無向圖或有向圖都不存在拓?fù)渑判颉?/p>
一種常用的拓?fù)渑判蛩惴ㄊ敲看螐挠邢驘o環(huán)圖中取出一個入度為0的節(jié)點添加到拓?fù)渑判蛐蛄兄?，然后刪除該節(jié)點及所有以他為起點的邊。重復(fù)這個步驟，直到圖為空或圖中不存在入度為0的節(jié)點。如果最終圖為空，那么圖是有向無環(huán)圖，此時就找到了該圖的一個拓?fù)渑判蛐蛄?。如果最終圖不為空并且已經(jīng)不存在入度為0的節(jié)點，那么該圖一定有環(huán)。
課程表
題目
思路
首先先建圖，可以采用鄰接矩陣或者鄰接表建圖，解題時采用鄰接表來建圖，并統(tǒng)計每個節(jié)點的入度，然后掃描所有節(jié)點的入度，將入度尾0的節(jié)點加入到隊列中，取出隊頭元素，將該節(jié)點加入數(shù)組中，并將以該節(jié)點為起始點的邊的終點的入度-1，如果有節(jié)點的入度為0，就將該節(jié)點加入隊列中，最后，如果數(shù)組的大小和課程數(shù)目不相等，說明存在環(huán)，不能修完課程；否則能修完課程。
代碼
class Solution {
public:
bool canFinish(int numCourses, vector
vector
vector
vector
for(auto it:prerequisites){
vv[it[1]].push_back(it[0]);
in[it[0]]++;
}
queue
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 題目 思路 這道題和上一道題其實是一樣的，只不過是問題不同而已，解決方法還是首先先建圖，可以采用鄰接矩陣或者鄰接表建圖，解題時采用鄰接表來建圖，并統(tǒng)計每個節(jié)點的入度，然后掃描所有節(jié)點的入度，將入度尾0的節(jié)點加入到隊列中，取出隊頭元素，將該節(jié)點加入數(shù)組中，并將以該節(jié)點為起始點的邊的終點的入度-1，如果有節(jié)點的入度為0，就將該節(jié)點加入隊列中，最后，如果數(shù)組的大小和課程數(shù)目不相等，說明存在環(huán)，不能修完課程；否則能修完課程。 代碼 class Solution { public: vector unordered_map vector vector for(auto it:prerequisites){ hash[it[1]].push_back(it[0]); in[it[0]]++; } queue 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 // vector // vector // vector // for(auto it:prerequisites){ // vv[it[1]].push_back(it[0]); // in[it[0]]++; // } // queue // 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 題目 思路 雖然這道題和前兩道題看起來是一樣的，但是這道題比前兩道題要難一些，因為對于每一遍掃描到的入度為0的節(jié)點，這些節(jié)點之間是沒有先決條件關(guān)系的，如果還用之前的解法，會把每一遍掃描到的入度為0的節(jié)點賦予先決條件，因此我們需要使用別的方法。 下面，先使用鄰接表建圖，然后掃描每個節(jié)點，進(jìn)行深度優(yōu)先遍歷，如果該節(jié)點沒有被遍歷過，則遍歷以該節(jié)點為起始點的所有邊的終點，依舊是判斷該節(jié)點有沒有被遍歷過，如果沒有被遍歷過，則遍歷以該節(jié)點為起始點的所有邊的終點，然后將鄰接矩陣中的起始點到終點的值置為true，然后遍歷所有終點，看是否存在以終點為起始點的點，然后將鄰接矩陣中起始點到終點的終點的值置為isPre[pos][i]=isPre[pos][i]|isPre[x][i]。 代碼 class Solution { public: vector vector vector vector for(auto& p:prerequisites) edges[p[0]].push_back(p[1]); for(int i=0;i dfs(edges,isPre,vis,i); vector for(auto& query:queries) res.push_back(isPre[query[0]][query[1]]); return res; } void dfs(vector 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 // vector // vector // vector // unordered_map // queue // // Construct adjacency list and initialize in-degree counts // vector // 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 // 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 // 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; // } // }; 火星詞典 題目 思路 這道題的題目首先得看懂，然后解析所有字符串，兩個字符串滿足前一個字符串的前n個字符和后一個字符串的前n個字符相同，第一次出現(xiàn)不同字符時，前一個字符串的第n+1個字符的序列小于后一個字符串的第n+1個字符的序列，如果第一個字符串的長度大于第二個字符串的長度，且第一個字符串的長度為第二個字符串長度的字符和第二個字符串相等，這樣是不符合題意的，直接返回空串；否則就建立鄰接表，并統(tǒng)計所有節(jié)點的入度信息，將入度為0的節(jié)點的值加入隊列，然后取出隊頭元素，將該節(jié)點加入字符串末尾，并將以該節(jié)點為起始點的邊的終點的入度-1，如果有節(jié)點的入度為0，就將該節(jié)點加入隊列中，執(zhí)行將該節(jié)點加入字符串末尾，并將以該節(jié)點為起始點的邊的終點的入度-1，如果有節(jié)點的入度為0，就將該節(jié)點加入隊列中。 最后掃描數(shù)組，如果存在某個節(jié)點的入度不為0，說明存在環(huán)，不能排序，返回空串；否則返回結(jié)果字符串。 代碼 class Solution { unordered_map unordered_map bool flag; public: string alienOrder(vector 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 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; } }; 柚子快報激活碼778899分享：算法 拓?fù)渑判驅(qū)ｎ}篇 相關(guān)閱讀
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Zalora海外時尚購
