2 problems

hitzzc · hitzzc · commit f6bf5d47720c · 2016-10-16T11:34:06.000+08:00
diff --git a/README.md b/README.md
@@ -165,6 +165,8 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [204. Count Primes](https://github.com/hitzzc/go-leetcode/tree/master/count_primes)
 #### [205. Isomorphic Strings](https://github.com/hitzzc/go-leetcode/tree/master/isomorphic_strings)
 #### [206. Reverse Linked List](https://github.com/hitzzc/go-leetcode/tree/master/reverse_linked_list)
+#### [207. Course Schedule](https://github.com/hitzzc/go-leetcode/tree/master/course_schedule)
+#### [208. Implement Trie (Prefix Tree)](https://github.com/hitzzc/go-leetcode/tree/master/implement_trie)
 
 
 
diff --git a/course_schedule/course_schedule.go b/course_schedule/course_schedule.go
@@ -0,0 +1,70 @@
+package course_schedule
+
+// BFS
+func canFinish(numCourses int, prerequisites [][]int) bool {
+	graph := map[int][]int{}
+	inDegree := make([]int, numCourses)
+	for i := range prerequisites {
+		graph[prerequisites[i][1]] = append(graph[prerequisites[i][1]], prerequisites[i][0])
+		inDegree[prerequisites[i][0]]++
+	}
+	queue := []int{}
+	for i := range inDegree {
+		if inDegree[i] == 0 {
+			queue = append(queue, i)
+		}
+	}
+	for len(queue) != 0 {
+		head := queue[0]
+		queue = queue[1:]
+		for i := range graph[head] {
+			inDegree[graph[head][i]]--
+			if inDegree[graph[head][i]] == 0 {
+				queue = append(queue, graph[head][i])
+			}
+		}
+	}
+	for i := range inDegree {
+		if inDegree[i] != 0 {
+			return false
+		}
+	}
+	return true
+}
+
+// DFS
+func canFinishDFS(numCourses int, prerequisites [][]int) bool {
+	graph := map[int][]int{}
+	for i := range prerequisites {
+		graph[prerequisites[i][1]] = append(graph[prerequisites[i][1]], prerequisites[i][0])
+	}
+	path := make([]bool, numCourses)
+	visited := make([]bool, numCourses)
+	for i := 0; i < numCourses; i++ {
+		if visited[i] {
+			continue
+		}
+		if hasCycle(i, graph, path, visited) {
+			return false
+		}
+	}
+	return true
+}
+
+func hasCycle(start int, graph map[int][]int, path []bool, visited []bool) bool {
+	for i := range graph[start] {
+		if visited[graph[start][i]] {
+			continue
+		}
+		if path[graph[start][i]] {
+			return true
+		}
+		path[graph[start][i]] = true
+		if hasCycle(graph[start][i], graph, path, visited) {
+			return true
+		}
+		path[graph[start][i]] = false
+	}
+	visited[start] = true
+	return false
+}
diff --git a/implement_trie/implement_trie.cpp b/implement_trie/implement_trie.cpp
@@ -0,0 +1,56 @@
+#include <unordered_map>
+using namespace std;
+
+class TrieNode {
+public:
+    TrieNode(): is_word_(false) {}
+public:
+    bool is_word_;
+    unordered_map<char, TrieNode*> children;
+};
+
+class Trie {
+public:
+    Trie() {
+        root = new TrieNode();
+    }
+
+    // Inserts a word into the trie.
+    void insert(string word) {
+        if (word.size() <= 0) return;
+        TrieNode* node = root;
+        for (int i = 0; i < word.size(); ++i){
+            if (node->children.find(word[i]) == node->children.end()){
+                node->children[word[i]] = new TrieNode();
+            }
+            node = node->children[word[i]];
+        }
+        node->is_word_ = true;
+        return;
+    }
+
+    // Returns if the word is in the trie.
+    bool search(string word) {
+        return retrieve(word, false);
+    }
+
+    // Returns if there is any word in the trie
+    // that starts with the given prefix.
+    bool startsWith(string prefix) {
+        return retrieve(prefix, true);
+    }
+
+private:
+    TrieNode* root;
+private:
+    bool retrieve(string& key, bool prefix){
+        if (key.size() <= 0) return false;
+        TrieNode* node = root;
+        for (int i = 0; i < key.size(); i++){
+            if (node->children.find(key[i]) == node->children.end())
+                return false;
+            node = node->children[key[i]];
+        }
+        return prefix ? true : node->is_word_;
+    }
+};
