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

Commitc03b738

Browse files
committed
[Function add]
1. Add leetcode solutions with tag amazon.
1 parentc745673 commitc03b738

File tree

3 files changed

+206
-0
lines changed

3 files changed

+206
-0
lines changed

‎leetcode/572. Subtree of Another Tree.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,3 +88,33 @@ Return false.
8888
}
8989
}
9090
```
91+
92+
###Amazon session
93+
* Method 1: recursion
94+
```Java
95+
/**
96+
* Definition for a binary tree node.
97+
* public class TreeNode {
98+
* int val;
99+
* TreeNode left;
100+
* TreeNode right;
101+
* TreeNode(int x) { val = x; }
102+
* }
103+
*/
104+
class Solution {
105+
public boolean isSubtree(TreeNode s, TreeNode t) {
106+
if(s != null && t != null){
107+
return same(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
108+
}else if(s == null && t == null) return true;
109+
return false;
110+
}
111+
private boolean same(TreeNode s, TreeNode t){
112+
if(s == null && t == null) return true;
113+
else if((s == null && t != null) || (s != null && t == null)) return false;
114+
else{
115+
if(s.val != t.val) return false;
116+
return same(s.left, t.left) && same(s.right, t.right);
117+
}
118+
}
119+
}
120+
```

‎leetcode/694. Number of Distinct Islands.md

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,5 +86,99 @@ Note: The length of each dimension in the given grid does not exceed 50.
8686
}
8787
```
8888

89+
###Amazon session
90+
*Method1: dfs
91+
```Java
92+
classSolution {
93+
privatestaticfinalint[][] dir=newint[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
94+
privatestaticfinalString[] dStr=newString[]{"r","l","d","u"};
95+
privateSet<String> set;
96+
privateint height;
97+
privateint width;
98+
privateint[][] grid;
99+
publicintnumDistinctIslands(int[][]grid) {
100+
this.set=newHashSet<>();
101+
this.grid= grid;
102+
this.height= grid.length;
103+
this.width= grid[0].length;
104+
for(int i=0; i< height; i++){
105+
for(int j=0; j< width; j++){
106+
if(grid[i][j]==1){
107+
StringBuilder sb=newStringBuilder();
108+
sb.append("s");
109+
grid[i][j]=0;
110+
dfs(sb, i, j);
111+
set.add(sb.toString());
112+
}
113+
}
114+
}
115+
return set.size();
116+
}
117+
privatevoiddfs(StringBuildersb,intx,inty){
118+
int tx=0, ty=0;
119+
for(int d=0; d<4; d++){
120+
tx= x+ dir[d][0];
121+
ty= y+ dir[d][1];
122+
if(tx>=0&& tx< height&& ty>=0&& ty< width&& grid[tx][ty]==1){
123+
grid[tx][ty]=0;
124+
sb.append(dStr[d]);
125+
dfs(sb, tx, ty);
126+
}
127+
}
128+
sb.append("b");
129+
}
130+
}
131+
```
132+
133+
*Method2: bfs
134+
```Java
135+
classSolution {
136+
privatestaticfinalint[][] dir=newint[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
137+
privatestaticfinalString[] dStr=newString[]{"r","l","d","u"};
138+
privateSet<String> set;
139+
privateint height;
140+
privateint width;
141+
privateint[][] grid;
142+
publicintnumDistinctIslands(int[][]grid) {
143+
this.set=newHashSet<>();
144+
this.grid= grid;
145+
this.height= grid.length;
146+
this.width= grid[0].length;
147+
for(int i=0; i< height; i++){
148+
for(int j=0; j< width; j++){
149+
if(grid[i][j]==1){
150+
StringBuilder sb=newStringBuilder();
151+
sb.append("s");
152+
bfs(sb, i, j);
153+
}
154+
}
155+
}
156+
return set.size();
157+
}
158+
privatevoidbfs(StringBuildersb,intx,inty){
159+
Queue<int[]> q=newLinkedList<>();
160+
q.offer(newint[]{x, y});
161+
grid[x][y]=0;
162+
while(!q.isEmpty()){
163+
int size= q.size();
164+
for(int sz=0; sz< size; sz++){
165+
int[] cur= q.poll();
166+
int tx=0, ty=0;
167+
for(int d=0; d<4; d++){
168+
tx= cur[0]+ dir[d][0];
169+
ty= cur[1]+ dir[d][1];
170+
if(tx>=0&& tx< height&& ty>=0&& ty< width&& grid[tx][ty]==1){
171+
grid[tx][ty]=0;
172+
sb.append(dStr[d]);
173+
q.offer(newint[]{tx, ty});
174+
}
175+
}
176+
sb.append("b");
177+
}
178+
}
179+
set.add(sb.toString());
180+
}
181+
}
182+
```
89183
###Reference
90184
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/994. Rotting Oranges.md

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
##994. Rotting Oranges
2+
3+
###Question
4+
In a given grid, each cell can have one of three values:
5+
1. the value 0 representing an empty cell;
6+
2. the value 1 representing a fresh orange;
7+
3. the value 2 representing a rotten orange.
8+
9+
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
10+
11+
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.
12+
13+
```
14+
Example 1:
15+
16+
Input: [[2,1,1],[1,1,0],[0,1,1]]
17+
Output: 4
18+
19+
Example 2:
20+
21+
Input: [[2,1,1],[0,1,1],[1,0,1]]
22+
Output: -1
23+
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
24+
25+
Example 3:
26+
27+
Input: [[0,2]]
28+
Output: 0
29+
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
30+
```
31+
32+
Note:
33+
1. 1 <= grid.length <= 10
34+
2. 1 <= grid[0].length <= 10
35+
3. grid[i][j] is only 0, 1, or 2.
36+
37+
###Solution
38+
* Method 1: BFS
39+
```Java
40+
class Solution {
41+
private static final int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
42+
public int orangesRotting(int[][] grid) {
43+
int height = grid.length, width = grid[0].length;
44+
Queue<int[]> q = new LinkedList<>();
45+
int fresh = 0;
46+
Set<Integer> visited = new HashSet<>();
47+
for(int i = 0; i < height; i++){
48+
for(int j = 0; j < width; j++){
49+
if(grid[i][j] == 1) fresh++;
50+
else if(grid[i][j] == 2){
51+
q.offer(new int[]{i, j});
52+
visited.add(i * width + j);
53+
}
54+
}
55+
}
56+
int step = 0;
57+
if(fresh == 0) return 0;
58+
while(!q.isEmpty() && fresh != 0){
59+
int size = q.size();
60+
for(int sz = 0; sz < size; sz++){
61+
int[] cur = q.poll();
62+
int tx = 0, ty = 0;
63+
for(int d = 0; d < 4; d++){
64+
tx = cur[0] + dir[d][0];
65+
ty = cur[1] + dir[d][1];
66+
if(tx >= 0 && tx < height && ty >= 0 && ty < width && !visited.contains(tx * width + ty)){
67+
visited.add(tx * width + ty);
68+
if(grid[tx][ty] == 1){
69+
q.offer(new int[]{tx, ty});
70+
fresh--;
71+
}
72+
if(fresh == 0) return step + 1;
73+
}
74+
}
75+
}
76+
step++;
77+
}
78+
return -1;
79+
}
80+
}
81+
```
82+

0 commit comments

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