2

hitzzc · hitzzc · commit ffda9a663ae4 · 2016-11-03T14:30:08.000+08:00
diff --git a/README.md b/README.md
@@ -259,6 +259,8 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [374. Guess Number Higher or Lower](https://github.com/hitzzc/go-leetcode/tree/master/guess_number_higher_or_lower)
 #### [375. Guess Number Higher or Lower II](https://github.com/hitzzc/go-leetcode/tree/master/guess_number_higher_or_lower_II)
 #### [376. Wiggle Subsequence](https://github.com/hitzzc/go-leetcode/tree/master/wiggle_subsequence)
+#### [377. Combination Sum IV](https://github.com/hitzzc/go-leetcode/tree/master/combination_sum_IV)
+#### [378. Kth Smallest Element in a Sorted Matrix](https://github.com/hitzzc/go-leetcode/tree/master/kth_smallest_element_in_a_sorted_matrix)
 
 
 
diff --git a/combination_sum_IV/combination_sum_IV.cpp b/combination_sum_IV/combination_sum_IV.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+    int combinationSum4(vector<int>& nums, int target) {
+        vector<int> dp(target+1, 0);
+        dp[0] = 1;
+        for (int i = 1; i <= target; ++i) {
+        	for (auto& num: nums) {
+        		if (num <= i) {
+        			dp[i] += dp[i-num];
+        		}
+        	}
+        }
+        return dp[target];
+    }
+};
diff --git a/kth_smallest_element_in_a_sorted_matrix/kth_smallest_element_in_a_sorted_matrix.cpp b/kth_smallest_element_in_a_sorted_matrix/kth_smallest_element_in_a_sorted_matrix.cpp
@@ -0,0 +1,16 @@
+class Solution {
+public:
+    int kthSmallest(vector<vector<int>>& matrix, int k) {
+        int left = matrix[0][0], right = matrix.back().back();
+        while (left < right) {
+        	int mid = left + (right - left)/2;
+        	int cnt = 0;
+        	for (auto& vec: matrix) {
+        		cnt += upper_bound(vec.begin(), vec.end(), mid) - vec.begin();
+        	}
+        	if (cnt < k) left = mid + 1;
+        	else right = mid;
+        }
+        return left;
+    }
+};
