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

Commit1312ecf

Browse files
committed
[Function add]
1. Add leetcode solutions with amazon tag.
1 parent25cb3d6 commit1312ecf

File tree

3 files changed

+155
-1
lines changed

3 files changed

+155
-1
lines changed

‎leetcode/165. Compare Version Numbers.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -120,4 +120,32 @@ class Solution {
120120
return 0;
121121
}
122122
}
123+
```
124+
125+
###Amazon Session
126+
* Method 1: String
127+
```Java
128+
class Solution {
129+
public int compareVersion(String version1, String version2) {
130+
String[] tokens1 = version1.split("\\.");
131+
String[] tokens2 = version2.split("\\.");
132+
int index = 0;
133+
while(index < tokens1.length || index < tokens2.length){
134+
if(index < tokens1.length && index < tokens2.length){
135+
int first = Integer.parseInt(tokens1[index]);
136+
int second = Integer.parseInt(tokens2[index]);
137+
if(first < second) return -1;
138+
else if(first > second) return 1;
139+
}else if(index < tokens1.length){
140+
int first = Integer.parseInt(tokens1[index]);
141+
if(first != 0) return 1;
142+
}else if(index < tokens2.length){
143+
int second = Integer.parseInt(tokens2[index]);
144+
if(second != 0) return -1;
145+
}
146+
index++;
147+
}
148+
return 0;
149+
}
150+
}
123151
```

‎leetcode/253. Meeting Rooms II.md

Lines changed: 27 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,4 +72,30 @@ return 2.
7272
return max;
7373
}
7474
}
75-
```
75+
```
76+
77+
###AmazonSeesion
78+
*Method1:Pq+ sort
79+
```Java
80+
classSolution {
81+
publicintminMeetingRooms(int[][]intervals) {
82+
if(intervals.length<=1)return intervals.length;
83+
int result=1;
84+
PriorityQueue<int[]> pq=newPriorityQueue<>((a, b)->{
85+
return a[1]- b[1];
86+
});
87+
Arrays.sort(intervals, (a, b)->{
88+
return a[0]!= b[0]? a[0]- b[0]: a[1]- b[1];
89+
});
90+
pq.offer(intervals[0]);
91+
for(int i=1; i< intervals.length; i++){
92+
if(intervals[i][0]>= pq.peek()[1]){
93+
pq.poll();
94+
}
95+
pq.offer(intervals[i]);
96+
result=Math.max(result, pq.size());
97+
}
98+
return result;
99+
}
100+
}
101+
```

‎leetcode/505. The Maze II.md

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -210,5 +210,105 @@ Meanwhile, we need to use some ideas from the shortest path to update the path.
210210
}
211211
```
212212

213+
###AmazonSession
214+
*Method1: dfs
215+
```Java
216+
classSolution {
217+
privatestaticfinalint[][] dir=newint[][]{{0,1}, {1,0}, {-1,0}, {0,-1}};
218+
privateint height, width;
219+
privateint[][] maze;
220+
privateint[] destination;
221+
privateint result;
222+
privateint[][] dist;
223+
publicintshortestDistance(int[][]maze,int[]start,int[]destination) {
224+
this.height= maze.length;
225+
this.width= maze[0].length;
226+
this.maze= maze;
227+
this.destination= destination;
228+
this.result=Integer.MAX_VALUE;
229+
this.dist=newint[height][width];
230+
for(int[] dd: dist)Arrays.fill(dd,Integer.MAX_VALUE);
231+
dist[start[0]][start[1]]=0;
232+
if(start[0]== destination[0]&& start[1]== destination[1])return0;
233+
for(int d=0; d<4; d++){
234+
dfs(start,0, d);
235+
}
236+
returnthis.result==Integer.MAX_VALUE?-1:this.result;
237+
}
238+
privatevoiddfs(int[]cur,inttemp,intpre){
239+
// cur: current position
240+
// temp: current step
241+
// pre: previous direction
242+
if(cur[0]==this.destination[0]&& cur[1]==this.destination[1]){
243+
this.result=Math.min(this.result, temp);
244+
}elseif(dist[cur[0]][cur[1]]<this.result){
245+
int tx=0, ty=0;
246+
for(int d=0; d<4; d++){// 4 directions
247+
if(d+ pre==3|| d== pre)continue;
248+
int currentStep= temp+1;
249+
tx= cur[0]+ dir[d][0];
250+
ty= cur[1]+ dir[d][1];
251+
while(tx>=0&& tx< height&& ty>=0&& ty< width&& maze[tx][ty]!=1){
252+
tx+= dir[d][0];
253+
ty+= dir[d][1];
254+
currentStep++;
255+
}
256+
tx-= dir[d][0];
257+
ty-= dir[d][1];
258+
--currentStep;
259+
if(dist[tx][ty]<= currentStep)continue;
260+
else{
261+
dist[tx][ty]= currentStep;
262+
dfs(newint[]{tx, ty}, currentStep, d);
263+
}
264+
}
265+
}
266+
}
267+
}
268+
```
269+
270+
*Method2: bfs
271+
```Java
272+
classSolution {
273+
privatestaticfinalint[][] dir=newint[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
274+
publicintshortestDistance(int[][]maze,int[]start,int[]destination) {
275+
int height= maze.length, width= maze[0].length;
276+
if(start[0]== destination[0]&& start[1]== destination[1])return0;
277+
int[][] dist=newint[height][width];
278+
for(int[] dd: dist)Arrays.fill(dd,Integer.MAX_VALUE);
279+
dist[start[0]][start[1]]=0;
280+
Queue<int[]> q=newLinkedList<>();
281+
q.offer(start);
282+
int result=Integer.MAX_VALUE;
283+
while(!q.isEmpty()){
284+
int[] cur= q.poll();
285+
if(cur[0]== destination[0]&& cur[1]== destination[1]){
286+
result=Math.min(result, dist[cur[0]][cur[1]]);
287+
continue;
288+
}
289+
int tx=0, ty=0;
290+
for(int d=0; d<4; d++){
291+
int step= dist[cur[0]][cur[1]]+1;
292+
tx= cur[0]+ dir[d][0];
293+
ty= cur[1]+ dir[d][1];
294+
while(tx>=0&& tx< height&& ty>=0&& ty< width&& maze[tx][ty]!=1){
295+
tx+= dir[d][0];
296+
ty+= dir[d][1];
297+
++step;
298+
}
299+
--step;
300+
tx-= dir[d][0];
301+
ty-= dir[d][1];
302+
if(tx== cur[0]&& ty== cur[1])continue;
303+
if(dist[tx][ty]> step){
304+
dist[tx][ty]= step;
305+
if(dist[tx][ty]< result) q.offer(newint[]{tx, ty});
306+
}
307+
}
308+
}
309+
return result==Integer.MAX_VALUE?-1: result;
310+
}
311+
}
312+
```
213313
###Reference
214314
1. [Java 6msBFS by optimizing solution #2](https://leetcode.com/problems/the-maze-ii/discuss/290079/Java-6ms-BFS-by-optimizing-solution-2)

0 commit comments

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