perfect_squares

hitzzc · hitzzc · commit 65793014c670 · 2016-10-22T18:17:29.000+08:00
diff --git a/README.md b/README.md
@@ -204,6 +204,8 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [263. Ugly Number](https://github.com/hitzzc/go-leetcode/tree/master/ugly_number)
 #### [264. Ugly Number II](https://github.com/hitzzc/go-leetcode/tree/master/ugly_number_II)
 #### [268. Missing Number](https://github.com/hitzzc/go-leetcode/tree/master/missing_number)
+#### [278. First Bad Version](https://github.com/hitzzc/go-leetcode/tree/master/missing_number)
+#### [279. Perfect Squares](https://github.com/hitzzc/go-leetcode/tree/master/perfect_squares)
 
 
 
diff --git a/first_bad_version/first_bad_version.cpp b/first_bad_version/first_bad_version.cpp
@@ -0,0 +1,21 @@
+bool isBadVersion(int version);
+
+class Solution {
+public:
+    int firstBadVersion(int n) {
+		int i = 1;
+		int j = n;
+		int ret;
+		while (i <= j) {
+			int mid = i + (j-i)/2;
+			if (isBadVersion(mid)) {
+				j = mid;
+				ret = mid;
+			}else {
+				i= mid+1;
+				ret = mid+1;
+			}
+		}
+		return ret;   
+    }
+};
diff --git a/perfect_squares/perfect_squares.cpp b/perfect_squares/perfect_squares.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+    int numSquares(int n) {
+        if ( n<=0 ) return 0;
+        static vector<int> dp(1, 0);
+        if (dp.size() >n) return dp[n];
+        for (int i = dp.size(); i <= n; ++i) {
+        	int m = n;
+        	for (int j = 1; i-j*j>=0; ++j) {
+        		m = min(m, dp[i-j*j]+1);
+        	}
+        	dp.push_back(m);
+        }
+        return dp[n];
+    }
+    int min(int i, int j) {
+    	if (i < j) return i;
+    	return j;
+    }
+};
