[Function add]

Seanforfun · Seanforfun · commit 231521bc9a51 · 2019-05-03T13:05:40.000-04:00
1. Add leetcode solutions.
diff --git a/leetcode/149. Max Points on a Line.md b/leetcode/149. Max Points on a Line.md
@@ -0,0 +1,113 @@
+## 149. Max Points on a Line
+
+### Question
+Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
+
+```
+Example 1:
+
+Input: [[1,1],[2,2],[3,3]]
+Output: 3
+Explanation:
+^
+|
+|        o
+|     o
+|  o  
++------------->
+0  1  2  3  4
+
+Example 2:
+
+Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
+Output: 4
+Explanation:
+^
+|
+|  o
+|     o        o
+|        o
+|  o        o
++------------------->
+0  1  2  3  4  5  6
+```
+
+NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
+
+
+### Solutions:
+* Method 1: I first used the double to calculate the slope but cause precision error. O(n^3) cannot AC.
+    ```Java
+    class Solution {
+        public int maxPoints(int[][] points) {
+            int len = points.length;
+            if(len <= 2) return len;
+            int res = 0;
+            for(int i = 0; i < len; i++){
+                for(int j = i + 1; j < len; j++){
+                    int temp = 2;
+                    double x1 = (double)points[i][0];
+                    double x2 = (double)points[j][0];
+                    if(x1 != x2){
+                        double y1 = (double)points[i][1];
+                        double y2 = (double)points[j][1];
+                        double s = (y2 - y1) / (x2 - x1);
+                        double b = y1 - s * x1;
+                        for(int k = 0; k < len; k++){
+                            if(k == i || k == j) continue;
+                            double x = (double)points[k][0];
+                            double y = (double)points[k][1];
+                            if(y == x * s + b) temp++;
+                        }
+                    }else{
+                        for(int k = 0; k < len; k++){
+                            if(k == i || k == j) continue;
+                            double x = (double)points[k][0];
+                            if(x == x1) temp++;
+                        }
+                    }
+                    res = Math.max(res, temp);
+                }
+            }
+            return res;
+        }
+    }
+    ```
+
+* Method 2: HashMap to save the slope(use string) AC
+    ```Java
+    class Solution {
+        public int maxPoints(int[][] points) {
+            int len = points.length;
+            if(len <= 2) return len;
+            int res = 0;
+            for(int i = 0; i < len; i++){
+                for(int j = i + 1; j < len; j++){
+                    int temp = 2;
+                    double x1 = (double)points[i][0];
+                    double x2 = (double)points[j][0];
+                    if(x1 != x2){
+                        double y1 = (double)points[i][1];
+                        double y2 = (double)points[j][1];
+                        double s = (y2 - y1) / (x2 - x1);
+                        double b = y1 - s * x1;
+                        for(int k = 0; k < len; k++){
+                            if(k == i || k == j) continue;
+                            double x = (double)points[k][0];
+                            double y = (double)points[k][1];
+                            if(y == x * s + b) temp++;
+                        }
+                    }else{
+                        for(int k = 0; k < len; k++){
+                            if(k == i || k == j) continue;
+                            double x = (double)points[k][0];
+                            if(x == x1) temp++;
+                        }
+                    }
+                    res = Math.max(res, temp);
+                }
+            }
+            return res;
+        }
+    }
+    ```
diff --git a/leetcode/443. String Compression.md b/leetcode/443. String Compression.md
@@ -0,0 +1,90 @@
+## 443. String Compression
+
+### Question
+Given an array of characters, compress it in-place.
+
+The length after compression must always be smaller than or equal to the original array.
+
+Every element of the array should be a character (not int) of length 1.
+
+After you are done modifying the input array in-place, return the new length of the array.
+ 
+
+Follow up:
+Could you solve it using only O(1) extra space?
+ 
+```
+Example 1:
+
+Input:
+["a","a","b","b","c","c","c"]
+
+Output:
+Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
+
+Explanation:
+"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
+
+ 
+
+Example 2:
+
+Input:
+["a"]
+
+Output:
+Return 1, and the first 1 characters of the input array should be: ["a"]
+
+Explanation:
+Nothing is replaced.
+
+ 
+
+Example 3:
+
+Input:
+["a","b","b","b","b","b","b","b","b","b","b","b","b"]
+
+Output:
+Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
+
+Explanation:
+Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
+Notice each digit has it's own entry in the array.
+```
+
+Note:
+1. All characters have an ASCII value in [35, 126].
+2. 1 <= len(chars) <= 1000.
+
+
+
+
+
+### Solutions:
+* Method 1: 9m46s two pointers
+    ```Java
+    class Solution {
+        public int compress(char[] chars) {
+            int count = 0;
+            int read = 0;
+            while(read < chars.length){
+                char c = chars[read];
+                int check = read;
+                while(check < chars.length && chars[check] == c){
+                    check++;
+                }
+                // c appears check - read times.
+                chars[count++] = c;
+                if(check - read > 1){
+                    String num = "" + (check - read);
+                    for(int i = 0; i < num.length(); i++){
+                        chars[count++] = num.charAt(i);
+                    }
+                }
+                read = check;
+            }
+            return count;
+        }
+    }
+    ```
diff --git a/leetcode/528. Random Pick with Weight.md b/leetcode/528. Random Pick with Weight.md
@@ -0,0 +1,94 @@
+## 528. Random Pick with Weight
+
+### Question
+Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.
+
+Note:
+* 1 <= w.length <= 10000
+* 1 <= w[i] <= 10^5
+* pickIndex will be called at most 10000 times.
+
+```
+Example 1:
+
+Input: 
+["Solution","pickIndex"]
+[[[1]],[]]
+Output: [null,0]
+
+Example 2:
+
+Input: 
+["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
+[[[1,3]],[],[],[],[],[]]
+Output: [null,0,1,1,1,0]
+```
+
+Explanation of Input Syntax:
+
+The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren't any.
+
+
+### Solutions:
+* Method 1:  O(n) for each pick
+    ```
+    class Solution {
+        private static Random random = new Random();
+        private int[] w;
+        private int sum;
+        public Solution(int[] w) {
+            this.w = w;
+            for(int num : w) this.sum += num;
+        }
+        
+        public int pickIndex() {
+            int rand = random.nextInt(sum) + 1;
+            int temp = 0;
+            for(int i = 0; i < w.length; i++){
+                if(temp + w[i] >= rand) return i;
+                temp += w[i];
+            }
+            return w.length - 1;
+        }
+    }
+    
+    /**
+     * Your Solution object will be instantiated and called as such:
+     * Solution obj = new Solution(w);
+     * int param_1 = obj.pickIndex();
+     */
+    ```
+
+* Method 2: Binary search O(lgN)
+    * we take the sum up to all indexes.
+    * we use binary search to find the first number bigger(or equal to) the random value.
+    ```Java
+    class Solution {
+        private static Random random = new Random();
+        private int[] w;
+        public Solution(int[] w) {
+            this.w = w;
+            for(int i = 1; i < w.length; i++){
+                w[i] += w[i - 1];
+            }
+        }
+        
+        public int pickIndex() {
+            int rand = random.nextInt(w[w.length - 1]) + 1;
+            int left = 0, right = w.length - 1;
+            while(left < right){
+                int mid = left + (right - left) / 2;
+                if(w[mid] == rand) return mid;
+                else if(w[mid] < rand) left = mid + 1;
+                else right = mid;
+            }
+            return left;
+        }
+    }
+    
+    /**
+     * Your Solution object will be instantiated and called as such:
+     * Solution obj = new Solution(w);
+     * int param_1 = obj.pickIndex();
+     */
+    ```
diff --git a/leetcode/57. Insert Interval.md b/leetcode/57. Insert Interval.md
@@ -107,3 +107,38 @@ class Solution {
     }
 }
 ```
+
+### Third Time
+* Method 1: Array + Sort
+	```Java
+	class Solution {
+		public int[][] insert(int[][] intervals, int[] newInterval) {
+			int len = intervals.length;
+			int[] starts = new int[len + 1];
+			int[] ends = new int[len + 1];
+			// Currently the starts and ends are sorted and non-overlap
+			for(int i = 0; i < len; i++){
+				starts[i] = intervals[i][0];
+				ends[i] = intervals[i][1];
+			}
+			starts[len] = newInterval[0]; 
+			ends[len] = newInterval[1];
+			Arrays.sort(starts);
+			Arrays.sort(ends);
+			List<int[]> temp = new ArrayList<>();
+			int start = starts[0];
+			for(int i = 1; i <= len; i++){
+				if(starts[i] > ends[i - 1]){
+					temp.add(new int[]{start, ends[i - 1]});
+					start = starts[i];
+				}
+			}
+			temp.add(new int[]{start, ends[len]});
+			int[][] res = new int[temp.size()][2];
+			for(int i = 0; i < temp.size(); i++){
+				res[i] = temp.get(i);
+			}
+			return res;
+		}
+	}
+	```
diff --git a/leetcode/68. Text Justification.md b/leetcode/68. Text Justification.md
