民族服装的网站建设,化学产品在哪个网站做推广最好,wordpress中文主题免费下载,泰顺机械网站建设【207】 Course Schedule 排课问题#xff0c;n门课排课#xff0c;有的课程必须在另外一些课程之前上#xff0c;问能不能排出来顺序。 题解#xff1a;裸的拓扑排序。参考代码见算法竞赛入门指南这本书。 1 class Solution {2 public:3 bool dfs(const vectorvec… 【207】 Course Schedule 排课问题n门课排课有的课程必须在另外一些课程之前上问能不能排出来顺序。 题解裸的拓扑排序。参考代码见算法竞赛入门指南这本书。 1 class Solution {2 public:3 bool dfs(const vectorvectorint g, vectorint c, int u) {4 c[u] -1;5 for (int v 0; v n; v) {6 if (g[u][v]) {7 if (c[v] 0) { return false; }8 else if (!c[v] !dfs(g, c, v)) {9 return false;
10 }
11 }
12 }
13 c[u] 1;
14 topo[--t] u;
15 return true;
16 }
17 bool canFinish(int numCourses, vectorpairint, int prerequisites) {
18 vectorvectorint graph(numCourses, vectorint(numCourses, 0));
19 n numCourses;
20 topo.resize(n);
21 t n;
22 for (auto ele : prerequisites) {
23 int u ele.first, v ele.second;
24 graph[v][u] 1;
25 }
26 vectorint c(n, 0);
27 for (int i 0; i n; i) {
28 if (!c[i]) {
29 if (!dfs(graph, c, i)) {
30 return false;
31 }
32 }
33 }
34 /*
35 for (int i 0; i n; i) {
36 cout topo[i] ;
37 }
38 cout endl;
39 */
40 return true;
41 }
42 vectorint topo;
43 int n, t;
44 }; View Code 【210】 Course Schedule II 同上一个排课问题这次的问题是能不能给出一个可行的顺序。 题解还是裸的拓扑排序。 1 class Solution {2 public:3 bool dfs(vectorint c, vectorint topo, int u) {4 c[u] -1;5 for (int v 0; v n; v) {6 if (g[u][v]) {7 if (c[v] 0) {return false;}8 else if (!c[v] !dfs(c, topo, v)) {return false; }9 }
10 }
11 c[u] 1;
12 topo[--t] u;
13 return true;
14 }
15 vectorint findOrder(int numCourses, vectorpairint, int prerequisites) {
16 n numCourses, t n;
17 vectorint topo(n, 0);
18 vectorint c(n, 0);
19 vectorvectorint graph(n, vectorint(n, 0));
20 for (auto ele : prerequisites) {
21 int u ele.first, v ele.second;
22 graph[v][u] 1;
23 }
24 g graph;
25
26 for (int u 0; u n; u) {
27 if (!c[u]) {
28 if (!dfs(c, topo, u)) {
29 vectorint temp;
30 return temp;
31 }
32 }
33 }
34 return topo;
35 }
36 int n, t;
37 vectorvectorint g;
38 }; View Code 【269】 Alien Dictionary 给了一门新的语言给了一个单词字典所有的单词按照字典序排序。要求返回现有字母的顺序没有顺序的话返回空数组。 题解逐个比较两个相邻的单词如果他们第i个位置不同说明前一个单词的第i个字母u要小于后一个单词的第i个字母v然后建图建完图直接裸的拓扑排序。 1 class Solution {2 public:3 bool dfs(int u) {4 c[u] -1;5 for (int v 0; v tot; v) {6 if (g[u][v]) {7 if (c[v] 0) {return false;}8 else if (!c[v] !dfs(v)) {return false;}9 }
10 }
11 c[u] 1;
12 topo[--cur] u;
13 return true;
14 }
15
16 string alienOrder(vectorstring words) {
17 vectorpairint, int order;
18 const int n words.size();
19 int t 0;
20 for (int i 0; i n; i) {
21 string word words[i];
22 for (auto ele : word) {
23 if (mpCh2Num.find(ele) mpCh2Num.end()) {
24 mpCh2Num[ele] t;
25 mpNum2Ch[t] ele;
26 t;
27 }
28 }
29 }
30 c.resize(t), topo.resize(t);
31 tot t; cur t;
32
33 for (int i 0; i n - 1; i) {
34 string word1 words[i], word2 words[i1];
35 for (int idx 0; idx min(word1.size(), word2.size()); idx) {
36 if (word1[idx] ! word2[idx]) {
37 pairint, int p make_pair(mpCh2Num[word1[idx]], mpCh2Num[word2[idx]]);
38 order.push_back(p);
39 break;
40 }
41 }
42 }
43
44 vectorvectorint graph(t, vectorint(t, 0));
45 for (auto ele : order) {
46 int u ele.first, v ele.second;
47 graph[u][v] 1;
48 }
49 g graph;
50
51 for (int u 0; u t; u) {
52 if (!c[u]) {
53 if (!dfs(u)) {
54 string temp;
55 return temp;
56 }
57 }
58 }
59 string ans;
60 for (auto ele : topo) {
61 ans mpNum2Ch[ele];
62 }
63 return ans;
64 }
65 vectorvectorint g;
66 vectorint c, topo;
67 mapint, char mpNum2Ch;
68 mapchar, int mpCh2Num;
69 int tot;
70 int cur;
71 }; View Code 【329】 Longest Increasing Path in a Matrix 给了一个矩阵matrix 一个点他可以朝着上下左右四个方向走问这个矩阵能走出来的最长递增的路径的长度是多少。 题解裸的dfs会超时所以加上了一个记忆化数组过了。题目的解法三有拓扑排序的相关解法下次要搞懂那个解法。 1 class Solution {2 public:3 void print(vectorvectorint mat) {4 const int n mat.size(), m mat[0].size();5 for (int i 0; i n; i) {6 for (int j 0; j m; j) {7 cout mat[i][j] ;8 }9 cout endl;
10 }
11 }
12 int dirx[4] {-1, 0, 1, 0};
13 int diry[4] {0, -1, 0, 1};
14 int dfs(const vectorvectorint mat, int x, int y, vectorvectorint vis) {
15 vis[x][y] 1;
16 for (int i 0; i 4; i) {
17 int newx x dirx[i], newy y diry[i];
18 if (newx 0 newx n newy 0 newy m !vis[newx][newy] mat[newx][newy] mat[x][y]) {
19 if (memo[newx][newy] ! 0) {
20 memo[x][y] max(memo[x][y], memo[newx][newy] 1);
21 } else {
22 memo[x][y] max(memo[x][y], dfs(mat, newx, newy, vis) 1);
23 }
24 }
25 }
26 vis[x][y] 0;
27 return memo[x][y];
28 }
29 int longestIncreasingPath(vectorvectorint matrix) {
30 n matrix.size();
31 if (n 0) { return 0; }
32 m matrix[0].size();
33 if (m 0) { return 0; }
34
35 int ans 0;
36 memo matrix;
37 for (int i 0; i n; i) {
38 for (int j 0; j m; j) {
39 memo[i][j] 0;
40 }
41 }
42
43 for (int i 0; i n; i) {
44 for (int j 0; j m; j) {
45 vectorvectorint vis(n, vectorint(m, 0));
46 memo[i][j] dfs(matrix, i, j, vis);
47 ans max(ans, memo[i][j]);
48 }
49 }
50 return ans 1;
51 }
52 int n, m;
53 vectorvectorint memo;
54 }; View Code 【444】 Sequence Reconstruction 转载于:https://www.cnblogs.com/zhangwanying/p/9655103.html
