solve 4 problems

hitzzc · hitzzc · commit 28fe57e95dcd · 2016-10-16T13:51:33.000+08:00
diff --git a/README.md b/README.md
@@ -167,6 +167,10 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [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)
+#### [209. Minimum Size Subarray Sum](https://github.com/hitzzc/go-leetcode/tree/master/minimum_size_subarray_sum)
+#### [210. Course Schedule II](https://github.com/hitzzc/go-leetcode/tree/master/course_schedule_II)
+#### [211. Add and Search Word - Data structure design](https://github.com/hitzzc/go-leetcode/tree/master/add_and_search_word)
+#### [213. House Robber II](https://github.com/hitzzc/go-leetcode/tree/master/add_and_search_word)
 
 
 
diff --git a/add_and_search_word/add_and_search_word.cpp b/add_and_search_word/add_and_search_word.cpp
@@ -0,0 +1,52 @@
+#include <unordered_map>
+using namespace std;
+
+struct TrieNode {
+	bool is_word_;
+	unordered_map<char, TrieNode*> children;
+	TrieNode(): is_word_(false) {}
+};
+
+class WordDictionary {
+public:
+	TrieNode* root;
+	WordDictionary() {
+		root = new TrieNode();
+	}
+    // Adds a word into the data structure.
+    void addWord(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;
+    }
+
+    // Returns if the word is in the data structure. A word could
+    // contain the dot character '.' to represent any one letter.
+    bool search(string word) {
+        return retrieve(word, root, 0, word.size());
+    }
+
+    bool retrieve(string& word, TrieNode* node, int idx, int length) {
+    	if (idx == length) return node->is_word_;
+    	if (word[idx] == '.') {
+    		if (node->children.size() == 0) {
+    			return false;
+    		}
+    		for (auto& kv: node->children) {
+    			if (retrieve(word, kv.second, idx+1, length)) {
+    				return true;
+    			}
+    		}
+    		return false;
+    	}else if (node->children.find(word[idx]) != node->children.end()) {
+    		return retrieve(word, node->children[word[idx]], idx+1, length);
+    	}
+    	return false;
+    }
+};
diff --git a/course_schedule_II/course_schedule_II.go b/course_schedule_II/course_schedule_II.go
@@ -0,0 +1,32 @@
+package course_schedule_II
+
+func findOrder(numCourses int, prerequisites [][]int) []int {
+	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)
+		}
+	}
+	ret := []int{}
+	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])
+			}
+		}
+		ret = append(ret, head)
+	}
+	if len(ret) != numCourses {
+		return []int{}
+	}
+	return ret
+}
diff --git a/house_robber_II/house_robber_II.go b/house_robber_II/house_robber_II.go
@@ -0,0 +1,33 @@
+package house_robber_II
+
+func rob(nums []int) int {
+	if len(nums) == 0 {
+		return 0
+	}
+	if len(nums) == 1 {
+		return nums[0]
+	}
+	if len(nums) == 2 {
+		return max(nums[0], nums[1])
+	}
+	x := helper(nums, 0, len(nums)-2)
+	y := helper(nums, 1, len(nums)-1)
+	return max(x, y)
+}
+
+func helper(nums []int, i, j int) int {
+	var n1, n2, current int
+	for ; i <= j; i++ {
+		current = max(n1, n2+nums[i])
+		n2 = n1
+		n1 = current
+	}
+	return n1
+}
+
+func max(i, j int) int {
+	if i > j {
+		return i
+	}
+	return j
+}
diff --git a/minimum_size_subarray_sum/minimum_size_subarray_sum.go b/minimum_size_subarray_sum/minimum_size_subarray_sum.go
@@ -0,0 +1,21 @@
+package minimum_size_subarray_sum
+
+func minSubArrayLen(s int, nums []int) int {
+	var left, right, res int
+	min := len(nums) + 1
+	for right < len(nums) {
+		for ; res < s && right < len(nums); right++ {
+			res += nums[right]
+		}
+		for ; res >= s; left++ {
+			res -= nums[left]
+			if right-left < min {
+				min = right - left
+			}
+		}
+	}
+	if min == len(nums)+1 {
+		return 0
+	}
+	return min
+}
