Add comments to explain the solutions

haoel · haoel · commit 33f3f485333f · 2014-11-05T00:21:28.000+08:00
diff --git a/src/3SumClosest/3SumClosest.cpp b/src/3SumClosest/3SumClosest.cpp
@@ -25,13 +25,30 @@ using namespace std;
 
 #define INT_MAX 2147483647
 //solution:  http://en.wikipedia.org/wiki/3SUM
+//the idea as blow:
+//  1) sort the array.
+//  2) take the element one by one, calculate the two numbers in reset array.
+//
+//notes: be careful the duplication number.
+//
+// for example:
+//    [-4,-1,-1,1,2]    target=1
+// 
+//    take -4, can cacluate the "two number problem" of the reset array [-1,-1,1,2] while target=5
+//    [(-4),-1,-1,1,2]  target=5  distance=4
+//           ^      ^ 
+//    because the -1+2 = 1 which < 5, then move the `low` pointer(skip the duplication)
+//    [(-4),-1,-1,1,2]  target=5  distance=2
+//                ^ ^ 
+//    take -1(skip the duplication), can cacluate the "two number problem" of the reset array [1,2] while target=2
+//    [-4,-1,(-1),1,2]  target=2  distance=1
+//                ^ ^ 
 int threeSumClosest(vector<int> &num, int target) {
-
-
+    //sort the array
     sort(num.begin(), num.end());
 
     int n = num.size();
-    int distance = INT_MAX; 
+    int distance = INT_MAX;
     int result;
 
     for (int i=0; i<n-2; i++) {
@@ -40,34 +57,38 @@ int threeSumClosest(vector<int> &num, int target) {
         int a = num[i];
         int low = i+1;
         int high = n-1;
+        //convert the 3sum to 2sum problem
         while ( low < high ) {
             int b = num[low];
             int c = num[high];
             int sum = a+b+c;
             if (sum - target == 0) {
                 //got the final soultion
                 return target;
-            } else if (sum -target> 0) {
+            } else {
+
+                //tracking the minmal distance
                 if (abs(sum-target) < distance ) {
-                    distance = abs(sum - target); 
+                    distance = abs(sum - target);
                     result = sum;
                 }
-                //skip the duplication
-                while(high>0 && num[high]==num[high-1]) high--;
-                high--;
-            } else{
-                if (abs(sum-target) < distance) {
-                    distance = abs(sum - target); 
-                    result = sum;
+
+                if (sum -target> 0) {
+                    //skip the duplication
+                    while(high>0 && num[high]==num[high-1]) high--;
+                    //move the `high` pointer
+                    high--;
+                } else {
+                    //skip the duplication
+                    while(low<n && num[low]==num[low+1]) low++;
+                    //move the `low` pointer
+                    low++;
                 }
-                //skip the duplication
-                while(low<n && num[low]==num[low+1]) low++;
-                low++;
-            } 
+            }
         }
     }
-    return result;
 
+    return result;
 }
 
 
diff --git a/src/pow/pow.cpp b/src/pow/pow.cpp
@@ -12,6 +12,30 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+/*
+ *   Basically, most people think this is very easy as below:
+ *
+ *      double result = 1.0;
+ *      for (int i=0; i<n; i++){
+ *           result *=x;
+ *      }
+ *   
+ *   However, 
+ *
+ *     1) We need think about the `n` is negtive number.
+ *
+ *     2) We need more wisely deal with the following cases:
+ *
+ *         pow(1, MAX_INT);
+ *         pow(-1,BIG_INT);
+ *         pow(2, BIG_INT);
+ *
+ *        To deal with such kind case, we can use x = x*x to reduce the `n` more quickly
+ *
+ *        so, if `n` is an even number, we can `x = x*x`, and `n = n>>1;`
+ *            if `n` is an odd number, we can just `result *= x;`
+ *
+ */
 double pow(double x, int n) {
 
     bool sign = false;
diff --git a/src/searchForRange/searchForRange.cpp b/src/searchForRange/searchForRange.cpp
@@ -23,6 +23,15 @@ using namespace std;
 
 int binary_search(int A[], int low, int high, int key);
 
+/*
+ *   O(log n) solution must be something like binary search.
+ *
+ *   So, we can use the binary search to find the one postion - `pos`
+ *   
+ *   then, we can keep using the binary search find the target in A[0..pos-1] and A[pos+1..n]
+ *
+ *   The code below is self-explaination
+ */
 vector<int> searchRange(int A[], int n, int target) {
     int pos = binary_search(A, 0, n-1, target);
 
