There are a total of n courses you have to take, labeled from
0
to n - 1
.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:
[0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
Hints:
-------------------------------------------------------------- This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
- Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- Topological sort could also be done via BFS.
重点:缺乏知识点,topological ordering的BFS做法https://en.wikipedia.org/wiki/Topological_sorting#Algorithms
Detect if there is a cycle in directed graph,
BFS
class Solution { public: bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { vector<vector<int> > edges(numCourses); vector<int> inDegree(numCourses,0); queue<int> que; for (int i = 0; i < prerequisites.size(); i++) { edges[prerequisites[i].second].push_back(prerequisites[i].first); inDegree[prerequisites[i].first]++; } for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) { que.push(i); } } while (!que.empty()) { int current = que.front(); que.pop(); for (int i = 0; i < edges[current].size(); i++) { inDegree[edges[current][i]]--; if (inDegree[edges[current][i]] == 0) { que.push(edges[current][i]); } } } for (int i = 0; i < numCourses; i++) { if (inDegree[i] != 0) { return false; } } return true; } };
DFS
class Solution { public: bool dfs(vector<vector<int> > &edges, vector<int> &visit, int point) { if (visit[point] == -1) return false; if (visit[point] == 1) return true; visit[point] = -1; for (int i = 0; i < edges[point].size(); i++) { if (!dfs(edges,visit,edges[point][i])) { return false; } } visit[point] = 1; return true; } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { vector<int> visit(numCourses,0); vector<vector<int> > edges(numCourses); for (int i = 0; i < prerequisites.size(); i++) { edges[prerequisites[i].second].push_back(prerequisites[i].first); } for (int i = 0; i < numCourses; i++) { if (!dfs(edges,visit,i)) return false; } return true; } };
Java, updated on Sep-29th-2018
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> graph = builtGraph(numCourses, prerequisites); int[] visited = new int[numCourses]; for (int i = 0; i < numCourses; i++) { if (!dfs(graph, i, visited)) return false; } return true; } private boolean dfs(List<List<Integer>> graph, int num, int[] visited) { if (visited[num] == 1) return true; if (visited[num] == -1) return false; visited[num] = -1; for (int nei : graph.get(num)) { if (!dfs(graph, nei, visited)) return false; } visited[num] = 1; return true; } private List<List<Integer>> builtGraph(int numCourses, int[][] prerequisites) { List<List<Integer>> rt = new ArrayList<>(); for (int i = 0; i < numCourses; i++) { rt.add(new ArrayList<>()); } for (int[] edge : prerequisites) { rt.get(edge[1]).add(edge[0]); } return rt; } }
BFS, Java
O(n), n是edge的数量,复杂度跟DFS一样
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<List<Integer>> rt = new ArrayList<>(); int[] inEdges = new int[numCourses]; for (int i = 0; i < numCourses; i++) { rt.add(new ArrayList<>()); } for (int[] edge : prerequisites) { rt.get(edge[1]).add(edge[0]); inEdges[edge[0]]++; } Queue<Integer> que = new LinkedList<>(); int count = 0; for (int i = 0; i < numCourses; i++) { if (inEdges[i] == 0) { que.add(i); } } while (!que.isEmpty()) { int top = que.poll(); for (int i : rt.get(top)) { inEdges[i]--; count++; if (inEdges[i] == 0) { que.add(i); } } } return count == prerequisites.length; } }
Implement Trie (Prefix Tree)
Implement a trie with
insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters
---------------------------------------------You may assume that all inputs are consist of lowercase letters
a-z
.在判断terminal上代码可以更简化
class TrieNode { public: // Initialize your data structure here. TrieNode() { next = vector<TrieNode*>(26,NULL); terminal = false; } char value; vector<TrieNode*> next; bool terminal; }; class Trie { public: Trie() { root = new TrieNode(); } // Inserts a word into the trie. void insert(string s) { TrieNode *cur = root; for (int i = 0; i < s.length(); i++) { char c = s[i] - 'a'; if (cur->next[c] == NULL) { TrieNode *trie = new TrieNode(); trie->value = c; cur->next[c] = trie; } if (i == s.length() - 1) { cur->next[c]->terminal = true; } cur = cur->next[c]; } } // Returns if the word is in the trie. bool search(string key) { TrieNode *cur = root; for (int i = 0; i < key.length(); i++) { char c = key[i] - 'a'; if (cur->next[c] == NULL) { return false; } if (i == key.length() - 1 && cur->next[c]->terminal) { return true; } cur = cur->next[c]; } return false; } // Returns if there is any word in the trie // that starts with the given prefix. bool startsWith(string prefix) { TrieNode *cur = root; for (int i = 0; i < prefix.length(); i++) { char c = prefix[i] - 'a'; if (cur->next[c] == NULL) { return false; } cur = cur->next[c]; } return true; } private: TrieNode* root; }; // Your Trie object will be instantiated and called as such: // Trie trie; // trie.insert("somestring"); // trie.search("key");
Java, updated on July-8th-2018
class Trie { class Node{ public Map<Character, Node> next; public boolean isWord; public Node() { next = new HashMap<>(); } } private Node root; /** Initialize your data structure here. */ public Trie() { root = new Node(); } /** Inserts a word into the trie. */ public void insert(String word) { Node node = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (!node.next.containsKey(c)) { node.next.put(c, new Node()); } node = node.next.get(c); } node.isWord = true; } /** Returns if the word is in the trie. */ public boolean search(String word) { Node node = getThatNode(word); return node != null && node.isWord; } /** Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String prefix) { return getThatNode(prefix) != null; } private Node getThatNode(String word) { Node node = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (!node.next.containsKey(c)) return null; node = node.next.get(c); } return node; } } /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */
No comments:
Post a Comment