[Function add]

Seanforfun · Seanforfun · commit d74e12d04494 · 2019-04-10T10:36:19.000-04:00
1. Add leetcode solutions with tag binary search.
diff --git a/leetcode/34. Find First and Last Position of Element in Sorted Array.md b/leetcode/34. Find First and Last Position of Element in Sorted Array.md
@@ -75,4 +75,27 @@ class Solution {
             return binarySearch(nums, target, mid + 1, high);
     }
 }
-```
+```
+
+###Third Time
+* Method 1: Binary Search
+	```Java
+	class Solution {
+		public int[] searchRange(int[] nums, int target) {
+			if(nums == null || nums.length == 0) return new int[]{-1, -1};
+			int index = bs(nums, 0, nums.length - 1, target);
+			if(index == -1) return new int[]{-1, -1};
+			int left = index, right = index;
+			while(--left >= 0 && nums[left] == target){}
+			while(++right < nums.length && nums[right] == target){}
+			return new int[]{left + 1, right - 1};
+		}
+		private int bs(int[] nums, int low, int high, int target){
+			if(low > high) return -1;
+			int mid = low + (high - low) / 2;
+			if(nums[mid] == target) return mid;
+			else if(nums[mid] < target) return bs(nums, mid + 1, high, target);
+			else return bs(nums, low, mid - 1, target);
+		}
+	}
+	```
diff --git a/leetcode/35. Search Insert Position.md b/leetcode/35. Search Insert Position.md
@@ -57,4 +57,26 @@ class Solution {
         return nums.length;
     }
 }
-```
+```
+
+### Third Time
+* Method 1: binary search AC 100%
+	```Java
+	class Solution {
+		public int searchInsert(int[] nums, int target) {
+			int low = 0, high = nums.length - 1;
+			return bs(nums, low, high, target);
+		}
+		private int bs(int[] nums, int low, int high, int target){
+			int mid = low + (high - low) / 2;
+			if(target > nums[nums.length - 1]) return nums.length;
+			if(mid == low || mid == high){
+				if(target > nums[low]) return high;
+				else return low;
+			}
+			if(nums[mid] == target) return mid;
+			else if(nums[mid] > target) return bs(nums, low, mid, target);
+			else return bs(nums, mid, high, target);
+		}
+	}
+	```
diff --git a/leetcode/704. Binary Search.md b/leetcode/704. Binary Search.md
@@ -0,0 +1,43 @@
+## 704. Binary Search
+
+### Question:
+Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
+
+```
+Example 1:
+
+Input: nums = [-1,0,3,5,9,12], target = 9
+Output: 4
+Explanation: 9 exists in nums and its index is 4
+
+Example 2:
+
+Input: nums = [-1,0,3,5,9,12], target = 2
+Output: -1
+Explanation: 2 does not exist in nums so return -1
+```
+
+Note:
+1. You may assume that all elements in nums are unique.
+2. n will be in the range [1, 10000].
+3. The value of each element in nums will be in the range [-9999, 9999].
+
+
+### Solution:
+* Method 1: binary search
+    ```Java
+    class Solution {
+        public int search(int[] nums, int target) {
+            if(nums == null || nums.length == 0) return -1;
+            return bs(nums, 0, nums.length - 1, target);
+        }
+        private int bs(int[] nums, int low, int high, int target){
+            if(low > high) return -1;
+            int mid = low + (high - low) / 2;
+            if(nums[mid] == target) return mid;
+            else if(nums[mid] > target) return bs(nums, low, mid - 1, target);
+            else return bs(nums, mid + 1, high, target);
+        }
+    }
+    ```
+   
diff --git a/leetcode/981. Time Based Key-Value Store.md b/leetcode/981. Time Based Key-Value Store.md
@@ -0,0 +1,79 @@
+## 981. Time Based Key-Value Store
+
+### Question:
+Create a timebased key-value store class TimeMap, that supports two operations.
+
+1. set(string key, string value, int timestamp)
+
+    Stores the key and value, along with the given timestamp.
+
+2. get(string key, int timestamp)
+
+    Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
+    If there are multiple such values, it returns the one with the largest timestamp_prev.
+    If there are no values, it returns the empty string ("").
+
+ 
+···
+Example 1:
+
+Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
+Output: [null,null,"bar","bar",null,"bar2","bar2"]
+Explanation:   
+TimeMap kv;   
+kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
+kv.get("foo", 1);  // output "bar"   
+kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
+kv.set("foo", "bar2", 4);   
+kv.get("foo", 4); // output "bar2"   
+kv.get("foo", 5); //output "bar2"   
+
+Example 2:
+
+Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
+Output: [null,null,null,"","high","high","low","low"]
+···
+ 
+Note:
+1. All key/value strings are lowercase.
+2. All key/value strings have length in the range [1, 100]
+3. The timestamps for all TimeMap.set operations are strictly increasing.
+4. 1 <= timestamp <= 10^7
+5. TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.
+
+
+
+
+### Solution:
+* Method 1: TreeMap
+    ```Java
+    class TimeMap {
+        private Map<String, TreeMap<Integer, String>> map;
+        /** Initialize your data structure here. */
+        public TimeMap() {
+            map = new HashMap<>();
+        }
+        public void set(String key, String value, int timestamp) {
+            TreeMap<Integer, String> treeMap = map.containsKey(key) ? map.get(key): new TreeMap<>();
+            treeMap.put(timestamp, value);
+            map.put(key, treeMap);
+        }
+        public String get(String key, int timestamp) {
+            if(!map.containsKey(key)) return "";
+            else{
+                TreeMap treeMap = map.get(key);
+                Map.Entry<Integer, String> entry = treeMap.floorEntry(timestamp);
+                if(entry == null) return "";
+                else return entry.getValue();
+            }
+        }
+    }
+    /**
+     * Your TimeMap object will be instantiated and called as such:
+     * TimeMap obj = new TimeMap();
+     * obj.set(key,value,timestamp);
+     * String param_2 = obj.get(key,timestamp);
+     */
+    ```
+    
+   
