0050 solved.

liuyubobobo · liuyubobobo · commit 022c10adb173 · 2018-12-20T18:49:00.000-08:00
diff --git a/0050-Pow-x-n/cpp-0050/CMakeLists.txt b/0050-Pow-x-n/cpp-0050/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.13)
+project(cpp_0050)
+
+set(CMAKE_CXX_STANDARD 11)
+
+add_executable(cpp_0050 main.cpp)
diff --git a/0050-Pow-x-n/cpp-0050/main.cpp b/0050-Pow-x-n/cpp-0050/main.cpp
@@ -0,0 +1,57 @@
+/// Source : https://leetcode.com/problems/powx-n/
+/// Author : liuyubobobo
+/// Time   : 2018-12-20
+
+#include <iostream>
+#include <vector>
+#include <cassert>
+
+using namespace std;
+
+
+/// Classic Divide and Conquer to get power
+/// Only deal with positive n
+///
+/// Time Complexity: O(logn)
+/// Space Complexity: O(logn)
+class Solution {
+public:
+    double myPow(double x, int n) {
+
+        if(n == 0) return 1.0;
+
+        double res = myPositivePow(x, abs((long long)n));
+        if(n < 0) res = 1.0 / res;
+        return res;
+    }
+
+private:
+    double myPositivePow(double x, long long n){
+
+        assert(n >= 0);
+        if(!n) return 1.0;
+
+        double t = myPositivePow(x, n / 2);
+        double res = t * t;
+        if(n % 2) res *= x;
+        return res;
+    }
+};
+
+
+int main() {
+
+    cout << Solution().myPow(2.0, -2) << endl;
+    // 0.25
+
+    cout << Solution().myPow(-2.0, 2) << endl;
+    // 4.0
+
+    cout << Solution().myPow(34.00515, -3) << endl;
+    // 3e-05
+
+    cout << Solution().myPow(1.0, -2147483648) << endl;
+    // 3e-05
+
+    return 0;
+}
diff --git a/0050-Pow-x-n/cpp-0050/main2.cpp b/0050-Pow-x-n/cpp-0050/main2.cpp
@@ -0,0 +1,44 @@
+/// Source : https://leetcode.com/problems/powx-n/
+/// Author : liuyubobobo
+/// Time   : 2018-12-20
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Classic Divide and Conquer to get power
+/// Deal with both positive and negative n correctly
+///
+/// Time Complexity: O(logn)
+/// Space Complexity: O(logn)
+class Solution {
+public:
+    double myPow(double x, int n) {
+
+        if(n == 0) return 1.0;
+
+        double t = myPow(x, n / 2);
+        if(n % 2 == 0)
+            return t * t;
+        else if( n > 0)
+            return t * t * x;
+        return t * t / x;
+    }
+};
+
+
+int main() {
+
+    cout << Solution().myPow(2.0, -2) << endl;
+    // 0.25
+
+    cout << Solution().myPow(-2.0, 2) << endl;
+    // 4.0
+
+    cout << Solution().myPow(34.00515, -3) << endl;
+    // 3e-05
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -88,7 +88,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 047 | [Permutations II](https://leetcode.com/problems/permutations-ii/description/) | [无] | [C++](0047-Permutations-II/cpp-0047/) | | |
 | 048 | [Rotate Image](https://leetcode.com/problems/rotate-image/description/) | [solution](https://leetcode.com/problems/rotate-image/) | [C++](0048-Rotate-Image/cpp-0048/) | | |
 | 049 | [Group Anagrams](https://leetcode.com/problems/group-anagrams/description/) | [solution](https://leetcode.com/problems/group-anagrams/solution/) | [C++](0049-Group-Anagrams/cpp-0049/) | | |
-| | | | | | |
+| 050 | [Pow(x, n)](https://leetcode.com/problems/powx-n/) | [无] | [C++](0050-Pow-x-n/cpp-0050/) | | |
 | 051 | [N-Queens](https://leetcode.com/problems/n-queens/description/) | [缺：N皇后问题整理] | [C++](0051-N-Queens/cpp-0051/) | [Java](0051-N-Queens/java-0051/src/) | |
 | | | | | | |
 | 054 | [Spiral Matrix](https://leetcode.com/problems/spiral-matrix/description/) | [solution](https://leetcode.com/problems/spiral-matrix/solution/) | [C++](0054-Spiral-Matrix/cpp-0054/) | | |
