Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6cafc3d

Browse files
committed
[Function add]
1. Add leetcode solutions.
1 parenta36bbdb commit6cafc3d

3 files changed

+205
-0
lines changed
Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
##588. Design In-Memory File System
2+
3+
###Question
4+
Design an in-memory file system to simulate the following functions:
5+
6+
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.
7+
8+
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.
9+
10+
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.
11+
12+
readContentFromFile: Given a file path, return its content in string format.
13+
14+
```
15+
Example:
16+
17+
Input:
18+
["FileSystem","ls","mkdir","addContentToFile","ls","readContentFromFile"]
19+
[[],["/"],["/a/b/c"],["/a/b/c/d","hello"],["/"],["/a/b/c/d"]]
20+
21+
Output:
22+
[null,[],null,null,["a"],"hello"]
23+
24+
Explanation:
25+
filesystem
26+
```
27+
![Imgur](https://i.imgur.com/M0m9jsf.png)
28+
29+
Note:
30+
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 "/".
31+
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.
32+
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.
33+
34+
###Thinking:
35+
* Method: Trie Tree like design
36+
```Java
37+
classFileSystem {
38+
privatestaticfinalclassFile{
39+
boolean isFile;
40+
TreeMap<String,File> childs;//key is the name, value is the file object.
41+
String name;
42+
String content;
43+
publicFile(Stringname){
44+
this.name= name;
45+
this.childs=newTreeMap<>();
46+
}
47+
}
48+
privateFile root;
49+
publicFileSystem() {
50+
this.root=newFile("/");
51+
}
52+
53+
publicList<String>ls(Stringpath) {
54+
String[] tokens= path.split("/");
55+
File cur= root;
56+
for(int i=1; i< tokens.length; i++){
57+
cur= cur.childs.get(tokens[i]);
58+
}
59+
List<String> result=newArrayList<>();
60+
if(cur.isFile){
61+
result.add(cur.name);
62+
}else{
63+
for(String key: cur.childs.keySet()){
64+
result.add(key);
65+
}
66+
}
67+
return result;
68+
}
69+
privateFilecreateFileOrDirectory(Stringpath){
70+
File cur= root;
71+
String[] tokens= path.split("/");
72+
for(int i=1; i< tokens.length; i++){
73+
if(!cur.childs.containsKey(tokens[i])){
74+
File next=newFile(tokens[i]);
75+
cur.childs.put(tokens[i], next);
76+
}
77+
cur= cur.childs.get(tokens[i]);
78+
}
79+
return cur;
80+
}
81+
publicvoidmkdir(Stringpath) {
82+
createFileOrDirectory(path);
83+
}
84+
85+
publicvoidaddContentToFile(StringfilePath,Stringcontent) {
86+
int index= filePath.lastIndexOf("/");
87+
File dir= createFileOrDirectory(filePath.substring(0, index));
88+
String filename= filePath.substring(index+1);
89+
File file=null;
90+
if(!dir.childs.containsKey(filename)){
91+
file=newFile(filename);
92+
dir.childs.put(filename, file);
93+
file.isFile=true;
94+
file.content= content;
95+
}else{
96+
file= dir.childs.get(filename);
97+
file.content+= content;
98+
}
99+
}
100+
101+
publicStringreadContentFromFile(StringfilePath) {
102+
File file= createFileOrDirectory(filePath);
103+
return file.content;
104+
}
105+
}
106+
107+
/**
108+
* Your FileSystem object will be instantiated and called as such:
109+
* FileSystem obj = new FileSystem();
110+
* List<String> param_1 = obj.ls(path);
111+
* obj.mkdir(path);
112+
* obj.addContentToFile(filePath,content);
113+
* String param_4 = obj.readContentFromFile(filePath);
114+
*/
115+
```
Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
##694. Number of Distinct Islands
2+
3+
###Question
4+
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.
5+
6+
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.
7+
8+
```
9+
Example 1:
10+
11+
11000
12+
11000
13+
00011
14+
00011
15+
16+
Given the above grid map, return 1.
17+
18+
Example 2:
19+
20+
11011
21+
10000
22+
00001
23+
11011
24+
25+
Given the above grid map, return 3.
26+
27+
Notice that:
28+
29+
11
30+
1
31+
32+
and
33+
34+
1
35+
11
36+
37+
are considered different island shapes, because we do not consider reflection / rotation.
38+
```
39+
40+
Note: The length of each dimension in the given grid does not exceed 50.
41+
42+
###Thinking:
43+
* Method: DFS + serialization
44+
* The idea of this question is to define the shape of the island.
45+
* We use dfs to traversal the whole island.
46+
* We can save the shapes into set and finally returns the size of the shape.
47+
```Java
48+
classSolution {
49+
privateSet<String> shapes;
50+
privateint[][] grid;
51+
privateint height;
52+
privateint width;
53+
privatestaticfinalint[][] dir=newint[][]{{0,1},{1,0},{0,-1}, {-1,0}};
54+
privatestaticfinalchar[] dStr=newchar[]{'r','d','l','u'};
55+
publicintnumDistinctIslands(int[][]grid) {
56+
if(grid==null|| grid.length==0)return0;
57+
this.grid= grid;
58+
this.shapes=newHashSet<>();
59+
this.height= grid.length;
60+
this.width= grid[0].length;
61+
for(int i=0; i< height; i++){
62+
for(int j=0; j< width; j++){
63+
if(grid[i][j]==0)continue;
64+
StringBuilder sb=newStringBuilder();
65+
sb.append('s');
66+
grid[i][j]=0;
67+
dfs(i, j, sb);
68+
this.shapes.add(sb.toString());
69+
}
70+
}
71+
return shapes.size();
72+
}
73+
privatevoiddfs(intx,inty,StringBuildersb){
74+
int tx=0, ty=0;
75+
for(int d=0; d<4; d++){
76+
tx= x+ dir[d][0];
77+
ty= y+ dir[d][1];
78+
if(tx>=0&& tx< height&& ty>=0&& ty< width&& grid[tx][ty]==1){
79+
sb.append(dStr[d]);
80+
grid[tx][ty]=0;
81+
dfs(tx, ty, sb);
82+
}
83+
}
84+
sb.append('b');
85+
}
86+
}
87+
```
88+
89+
###Reference
90+
1. [Java veryElegant and conciseDFS Solution(Beats100%)](https://leetcode.com/problems/number-of-distinct-islands/discuss/108475/Java-very-Elegant-and-concise-DFS-Solution(Beats-100))

‎leetcode/863. All Nodes Distance K in Binary Tree.md

Whitespace-only changes.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp