[Function add]

Seanforfun · Seanforfun · commit 6c31644f5405 · 2019-05-09T10:57:18.000-04:00
1. Add leetcode solutions.
diff --git a/leetcode/340. Longest Substring with At Most K Distinct Characters.md b/leetcode/340. Longest Substring with At Most K Distinct Characters.md
@@ -0,0 +1,51 @@
+## 340. Longest Substring with At Most K Distinct Characters
+
+### Question
+Given a string, find the length of the longest substring T that contains at most k distinct characters.
+
+```
+Example 1:
+
+Input: s = "eceba", k = 2
+Output: 3
+Explanation: T is "ece" which its length is 3.
+
+Example 2:
+
+Input: s = "aa", k = 1
+Output: 2
+Explanation: T is "aa" which its length is 2.
+```
+
+### Solutions
+* Method 1: Sliding window + HashMap
+  ```Java
+  class Solution {
+        public int lengthOfLongestSubstringKDistinct(String s, int k) {
+            if(s.length() <= k) return s.length();
+            int start = 0, end = 0;
+            Map<Character, Integer> map = new HashMap<>();
+            char[] arr = s.toCharArray();
+            int max = 0;
+            while(end < s.length()){
+                if(map.containsKey(arr[end]) || map.size() < k){
+                    map.put(arr[end], map.getOrDefault(arr[end], 0) + 1);
+                    max = Math.max(max, end - start + 1);
+                }else{  // current we need to remove
+                    map.put(arr[end], 1);
+                    while(map.size() > k){
+                        char c = arr[start++];
+                        int count = map.get(c);
+                        if(count == 1){
+                            map.remove(c);
+                        }else{
+                            map.put(c, count - 1);
+                        }
+                    }
+                }
+                end++;
+            }
+            return max;
+        }
+    }
+	```
diff --git a/leetcode/509. Fibonacci Number.md b/leetcode/509. Fibonacci Number.md
@@ -0,0 +1,49 @@
+## 509. Fibonacci Number
+
+### Question
+The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
+
+F(0) = 0,   F(1) = 1
+F(N) = F(N - 1) + F(N - 2), for N > 1.
+
+Given N, calculate F(N).
+
+```
+Example 1:
+
+Input: 2
+Output: 1
+Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
+
+Example 2:
+
+Input: 3
+Output: 2
+Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
+
+Example 3:
+
+Input: 4
+Output: 3
+Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
+```
+ 
+Note:
+* 0 ≤ N ≤ 30.
+
+
+### Solutions
+* Method 1: DP
+  ```Java
+  class Solution {
+        public int fib(int N) {
+            if(N < 2) return N;
+            int[] dp = new int[N + 1];
+            dp[0] = 0; dp[1] = 1;
+            for(int i = 2; i <= N; i++){
+                dp[i] = dp[i - 1] + dp[i - 2];
+            }
+            return dp[N];
+        }
+    }
+	```
diff --git a/leetcode/636. Exclusive Time of Functions.md b/leetcode/636. Exclusive Time of Functions.md
@@ -0,0 +1,68 @@
+## 636. Exclusive Time of Functions
+
+### Question
+On a single threaded CPU, we execute some functions.  Each function has a unique id between 0 and N-1.
+
+We store logs in timestamp order that describe when a function is entered or exited.
+
+Each log is a string with this format: "{function_id}:{"start" | "end"}:{timestamp}".  For example, "0:start:3" means the function with id 0 started at the beginning of timestamp 3.  "1:end:2" means the function with id 1 ended at the end of timestamp 2.
+
+A function's exclusive time is the number of units of time spent in this function.  Note that this does not include any recursive calls to child functions.
+
+Return the exclusive time of each function, sorted by their function id.
+
+```
+Example 1:
+
+Input:
+n = 2
+logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
+Output: [3, 4]
+Explanation:
+Function 0 starts at the beginning of time 0, then it executes 2 units of time and reaches the end of time 1.
+Now function 1 starts at the beginning of time 2, executes 4 units of time and ends at time 5.
+Function 0 is running again at the beginning of time 6, and also ends at the end of time 6, thus executing for 1 unit of time. 
+So function 0 spends 2 + 1 = 3 units of total time executing, and function 1 spends 4 units of total time executing.
+```
+ 
+Note:
+1. 1 <= n <= 100
+2. Two functions won't start or end at the same time.
+3. Functions will always log when they exit.
+
+
+### Solutions
+* Method 1: Simulation
+  ```Java
+  class Solution {
+        public int[] exclusiveTime(int n, List<String> logs) {
+            int[] result = new int[n];
+            int startTime = -1;
+            int curId = -1;
+            Stack<Integer> stack = new Stack<>();
+            for(String log: logs){
+                String[] tokens = log.split(":");
+                int id = Integer.parseInt(tokens[0]);
+                int time = Integer.parseInt(tokens[2]);            
+                if(tokens[1].equals("start")){
+                    if(curId != -1){
+                        result[curId] += time - startTime;
+                        stack.push(curId);
+                    }
+                    curId = id;
+                    startTime = time;
+                }else{  // current log is for ending.
+                    result[curId] += time - startTime + 1;
+                    if(!stack.isEmpty()){
+                        curId = stack.pop();
+                        startTime = time + 1;
+                    }else{
+                        curId = -1;
+                        startTime = -1;
+                    }
+                }
+            }
+            return result;
+        }
+    }
+	```
