[Function add]

Seanforfun · Seanforfun · commit 6cafc3d3e66c · 2019-05-17T12:41:15.000-04:00
1. Add leetcode solutions.
diff --git a/leetcode/588. Design In-Memory File System.md b/leetcode/588. Design In-Memory File System.md
@@ -0,0 +1,115 @@
+## 588. Design In-Memory File System
+
+### Question
+Design an in-memory file system to simulate the following functions:
+
+ls: Given a path in string format. If it is a file path, return a list that only contains this file's name. If it is a directory path, return the list of file and directory names in this directory. Your output (file and directory names together) should in lexicographic order.
+
+mkdir: Given a directory path that does not exist, you should make a new directory according to the path. If the middle directories in the path don't exist either, you should create them as well. This function has void return type.
+
+addContentToFile: Given a file path and file content in string format. If the file doesn't exist, you need to create that file containing given content. If the file already exists, you need to append given content to original content. This function has void return type.
+
+readContentFromFile: Given a file path, return its content in string format.
+
+```
+Example:
+
+Input: 
+["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]
+[[],["/"],["/a/b/c"],["/a/b/c/d","hello"],["/"],["/a/b/c/d"]]
+
+Output:
+[null,[],null,null,["a"],"hello"]
+
+Explanation:
+filesystem
+```
+![Imgur](https://i.imgur.com/M0m9jsf.png)
+
+Note:
+1. You can assume all file or directory paths are absolute paths which begin with / and do not end with / except that the path is just "/".
+2. You can assume that all operations will be passed valid parameters and users will not attempt to retrieve file content or list a directory or file that does not exist.
+3. You can assume that all directory names and file names only contain lower-case letters, and same names won't exist in the same directory.
+
+### Thinking:
+* Method: Trie Tree like design
+    ```Java
+    class FileSystem {
+        private static final class File{
+            boolean isFile;
+            TreeMap<String, File> childs;   //key is the name, value is the file object.
+            String name;
+            String content;
+            public File(String name){
+                this.name = name;
+                this.childs = new TreeMap<>();
+            }
+        }
+        private File root;
+        public FileSystem() {
+            this.root = new File("/");
+        }
+        
+        public List<String> ls(String path) {
+            String[] tokens = path.split("/");
+            File cur = root;
+            for(int i = 1; i < tokens.length; i++){
+                cur = cur.childs.get(tokens[i]);
+            }
+            List<String> result = new ArrayList<>();
+            if(cur.isFile){
+                result.add(cur.name);
+            }else{
+                for(String key : cur.childs.keySet()){
+                    result.add(key);
+                }
+            }
+            return result;
+        }
+        private File createFileOrDirectory(String path){
+            File cur = root;
+            String[] tokens = path.split("/");
+            for(int i = 1; i < tokens.length; i++){
+                if(!cur.childs.containsKey(tokens[i])){
+                    File next = new File(tokens[i]);
+                    cur.childs.put(tokens[i], next);
+                }
+                cur = cur.childs.get(tokens[i]);
+            }
+            return cur;
+        }
+        public void mkdir(String path) {
+            createFileOrDirectory(path);
+        }
+        
+        public void addContentToFile(String filePath, String content) {
+            int index = filePath.lastIndexOf("/");
+            File dir = createFileOrDirectory(filePath.substring(0, index));
+            String filename = filePath.substring(index + 1);
+            File file = null;
+            if(!dir.childs.containsKey(filename)){
+                file = new File(filename);
+                dir.childs.put(filename, file);
+                file.isFile = true;
+                file.content = content;
+            }else{
+                file = dir.childs.get(filename);
+                file.content += content;
+            }
+        }
+        
+        public String readContentFromFile(String filePath) {
+            File file = createFileOrDirectory(filePath);
+            return file.content;
+        }
+    }
+    
+    /**
+     * Your FileSystem object will be instantiated and called as such:
+     * FileSystem obj = new FileSystem();
+     * List<String> param_1 = obj.ls(path);
+     * obj.mkdir(path);
+     * obj.addContentToFile(filePath,content);
+     * String param_4 = obj.readContentFromFile(filePath);
+     */
+    ```
diff --git a/leetcode/694. Number of Distinct Islands.md b/leetcode/694. Number of Distinct Islands.md
@@ -0,0 +1,90 @@
+## 694. Number of Distinct Islands
+
+### Question
+Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
+
+Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
+
+```
+Example 1:
+
+11000
+11000
+00011
+00011
+
+Given the above grid map, return 1.
+
+Example 2:
+
+11011
+10000
+00001
+11011
+
+Given the above grid map, return 3.
+
+Notice that:
+
+11
+1
+
+and
+
+ 1
+11
+
+are considered different island shapes, because we do not consider reflection / rotation.
+```
+
+Note: The length of each dimension in the given grid does not exceed 50. 
+
+### Thinking:
+* Method: DFS + serialization
+    * The idea of this question is to define the shape of the island.
+    * We use dfs to traversal the whole island.
+    * We can save the shapes into set and finally returns the size of the shape.
+    ```Java
+    class Solution {
+        private Set<String> shapes;
+        private int[][] grid;
+        private int height;
+        private int width;
+        private static final int[][] dir = new int[][]{{0, 1},{1, 0},{0, -1}, {-1, 0}};
+        private static final char[] dStr = new char[]{'r', 'd', 'l', 'u'};
+        public int numDistinctIslands(int[][] grid) {
+            if(grid == null || grid.length == 0) return 0;
+            this.grid = grid;
+            this.shapes = new HashSet<>();
+            this.height = grid.length;
+            this.width = grid[0].length;
+            for(int i = 0; i < height; i++){
+                for(int j = 0; j < width; j++){
+                    if(grid[i][j] == 0) continue;
+                    StringBuilder sb = new StringBuilder();
+                    sb.append('s');
+                    grid[i][j] = 0;
+                    dfs(i, j, sb);
+                    this.shapes.add(sb.toString());
+                }
+            }
+            return shapes.size();
+        }
+        private void dfs(int x, int y, StringBuilder sb){
+            int tx = 0, ty = 0;
+            for(int d = 0; d < 4; d++){
+                tx = x + dir[d][0];
+                ty = y + dir[d][1];
+                if(tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] == 1){
+                    sb.append(dStr[d]);
+                    grid[tx][ty] = 0;
+                    dfs(tx, ty, sb);
+                }
+            }
+            sb.append('b');
+        }
+    }
+    ```
+
+### Reference
+1. [Java very Elegant and concise DFS Solution(Beats 100%)](https://leetcode.com/problems/number-of-distinct-islands/discuss/108475/Java-very-Elegant-and-concise-DFS-Solution(Beats-100))
diff --git a/leetcode/863. All Nodes Distance K in Binary Tree.md b/leetcode/863. All Nodes Distance K in Binary Tree.md
