[207]Course Schedule
排课问题, n 门课排课, 有的课程必须在另外一些课程之前上, 问能不能排出来顺序.
题解: 裸的拓扑排序. 参考代码见算法竞赛入门指南这本书.
- class Solution {
- public:
- bool dfs(const vector<vector<int>>& g, vector<int>& c, int u) {
- c[u] = -1;
- for (int v = 0; v <n; ++v) {
- if (g[u][v]) {
- if (c[v] < 0) { return false; }
- else if (!c[v] && !dfs(g, c, v)) {
- return false;
- }
- }
- }
- c[u] = 1;
- topo[--t] = u;
- return true;
- }
- bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
- vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
- n = numCourses;
- topo.resize(n);
- t = n;
- for (auto ele : prerequisites) {
- int u = ele.first, v = ele.second;
- graph[v][u] = 1;
- }
- vector<int> c(n, 0);
- for (int i = 0; i <n; ++i) {
- if (!c[i]) {
- if (!dfs(graph, c, i)) {
- return false;
- }
- }
- }
- /*
- for (int i = 0; i < n; ++i) {
- cout << topo[i] << " " ;
- }
- cout << endl;
- */
- return true;
- }
- vector<int> topo;
- int n, t;
- };
- View Code
[210]Course Schedule II
同上一个排课问题, 这次的问题是能不能给出一个可行的顺序.
题解: 还是裸的拓扑排序.
- class Solution {
- public:
- bool dfs(vector<int>& c, vector<int>& topo, int u) {
- c[u] = -1;
- for (int v = 0; v <n; ++v) {
- if (g[u][v]) {
- if (c[v] < 0) {return false;}
- else if (!c[v] && !dfs(c, topo, v)) {return false; }
- }
- }
- c[u] = 1;
- topo[--t] = u;
- return true;
- }
- vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
- n = numCourses, t = n;
- vector<int> topo(n, 0);
- vector<int> c(n, 0);
- vector<vector<int>> graph(n, vector<int>(n, 0));
- for (auto ele : prerequisites) {
- int u = ele.first, v = ele.second;
- graph[v][u] = 1;
- }
- g = graph;
- for (int u = 0; u <n; ++u) {
- if (!c[u]) {
- if (!dfs(c, topo, u)) {
- vector<int> temp;
- return temp;
- }
- }
- }
- return topo;
- }
- int n, t;
- vector<vector<int>> g;
- };
- View Code
[269]Alien Dictionary
给了一门新的语言, 给了一个单词字典, 所有的单词按照字典序排序. 要求返回现有字母的顺序, 没有顺序的话, 返回空数组.
题解: 逐个比较两个相邻的单词, 如果他们第 i 个位置不同, 说明前一个单词的第 i 个字母 u, 要小于后一个单词的第 i 个字母 v, 然后建图, 建完图直接裸的拓扑排序.
- class Solution {
- public:
- bool dfs(int u) {
- c[u] = -1;
- for (int v = 0; v <tot; ++v) {
- if (g[u][v]) {
- if (c[v] < 0) {return false;}
- else if (!c[v] && !dfs(v)) {return false;}
- }
- }
- c[u] = 1;
- topo[--cur] = u;
- return true;
- }
- string alienOrder(vector<string>& words) {
- vector<pair<int, int>> order;
- const int n = words.size();
- int t = 0;
- for (int i = 0; i <n; ++i) {
- string word = words[i];
- for (auto ele : word) {
- if (mpCh2Num.find(ele) == mpCh2Num.end()) {
- mpCh2Num[ele] = t;
- mpNum2Ch[t] = ele;
- ++t;
- }
- }
- }
- c.resize(t), topo.resize(t);
- tot = t; cur = t;
- for (int i = 0; i < n - 1; ++i) {
- string word1 = words[i], word2 = words[i+1];
- for (int idx = 0; idx < min(word1.size(), word2.size()); ++idx) {
- if (word1[idx] != word2[idx]) {
- pair<int, int> p = make_pair(mpCh2Num[word1[idx]], mpCh2Num[word2[idx]]);
- order.push_back(p);
- break;
- }
- }
- }
- vector<vector<int>> graph(t, vector<int>(t, 0));
- for (auto ele : order) {
- int u = ele.first, v = ele.second;
- graph[u][v] = 1;
- }
- g = graph;
- for (int u = 0; u <t; ++u) {
- if (!c[u]) {
- if (!dfs(u)) {
- string temp;
- return temp;
- }
- }
- }
- string ans;
- for (auto ele : topo) {
- ans += mpNum2Ch[ele];
- }
- return ans;
- }
- vector<vector<int>> g;
- vector<int> c, topo;
- map<int, char> mpNum2Ch;
- map<char, int> mpCh2Num;
- int tot;
- int cur;
- };
- View Code
[329]Longest Increasing Path in a Matrix
给了一个矩阵 matrix, 一个点他可以朝着上下左右四个方向走, 问这个矩阵能走出来的最长递增的路径的长度是多少.
题解: 裸的 dfs 会超时, 所以加上了一个记忆化数组过了. 题目的解法三有拓扑排序的相关解法, 下次要搞懂那个解法.
- class Solution {
- public:
- void print(vector<vector<int>>& mat) {
- const int n = mat.size(), m = mat[0].size();
- for (int i = 0; i <n; ++i) {
- for (int j = 0; j < m; ++j) {
- cout << mat[i][j] << " ";
- }
- cout << endl;
- }
- }
- int dirx[4] = {-1, 0, 1, 0};
- int diry[4] = {0, -1, 0, 1};
- int dfs(const vector<vector<int>>& mat, int x, int y, vector<vector<int>>& vis) {
- vis[x][y] = 1;
- for (int i = 0; i <4; ++i) {
- int newx = x + dirx[i], newy = y + diry[i];
- if (newx>= 0 && newx <n && newy>= 0 && newy <m && !vis[newx][newy]&& mat[newx][newy]> mat[x][y]) {
- if (memo[newx][newy] != 0) {
- memo[x][y] = max(memo[x][y], memo[newx][newy] + 1);
- } else {
- memo[x][y] = max(memo[x][y], dfs(mat, newx, newy, vis) + 1);
- }
- }
- }
- vis[x][y] = 0;
- return memo[x][y];
- }
- int longestIncreasingPath(vector<vector<int>>& matrix) {
- n = matrix.size();
- if (n == 0) { return 0; }
- m = matrix[0].size();
- if (m == 0) { return 0; }
- int ans = 0;
- memo = matrix;
- for (int i = 0; i <n; ++i) {
- for (int j = 0; j < m; ++j) {
- memo[i][j] = 0;
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- vector<vector<int>> vis(n, vector<int>(m, 0));
- memo[i][j] = dfs(matrix, i, j, vis);
- ans = max(ans, memo[i][j]);
- }
- }
- return ans +1;
- }
- int n, m;
- vector<vector<int>> memo;
- };
来源: http://www.bubuko.com/infodetail-2769628.html