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

Commitc745673

Browse files
committed
[Function add]
1. Add leetcode solutions with tag amazon.
1 parent95bb6cc commitc745673

File tree

4 files changed

+122
-0
lines changed

4 files changed

+122
-0
lines changed

‎leetcode/140. Word Break II.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -216,4 +216,33 @@ class Solution {
216216
return map.get(s);
217217
}
218218
}
219+
```
220+
221+
###Amazon session
222+
* Method 1: dp + recursion(bottom to top)
223+
```Java
224+
class Solution {
225+
private Map<String, List<String>> map = new HashMap<>();// memory
226+
public List<String> wordBreak(String s, List<String> wordDict) {
227+
if(map.containsKey(s)) return map.get(s);
228+
else if(s.equals("")){// break point
229+
List<String> temp = new ArrayList<>();
230+
temp.add("");
231+
map.put("", temp);
232+
return temp;
233+
}else{
234+
List<String> result = new ArrayList<>();
235+
for(String word: wordDict){
236+
if(s.startsWith(word)){
237+
List<String> res = wordBreak(s.substring(word.length()), wordDict);// Get result from sub question
238+
for(String ss : res){
239+
result.add(word + (ss.length() == 0 ? "": " ") + ss);
240+
}
241+
}
242+
}
243+
map.put(s, result);
244+
return result;
245+
}
246+
}
247+
}
219248
```

‎leetcode/53. Maximum Subarray.md

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -125,4 +125,22 @@ class Solution {
125125
return res;
126126
}
127127
}
128+
```
129+
130+
###Amazon Session
131+
* Method 1: dp
132+
```Java
133+
class Solution {
134+
public int maxSubArray(int[] nums) {
135+
if(nums == null || nums.length == 0) return 0;
136+
int[] dp = new int[nums.length];
137+
dp[0] = nums[0];
138+
int max = nums[0];
139+
for(int i = 1; i < nums.length; i++){
140+
dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
141+
max = Math.max(max, dp[i]);
142+
}
143+
return max;
144+
}
145+
}
128146
```

‎leetcode/64. Minimum Path Sum.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,3 +88,28 @@ class Solution {
8888
}
8989
}
9090
```
91+
92+
###Amazon session
93+
* Method 1: dp
94+
```Java
95+
class Solution {
96+
public int minPathSum(int[][] grid) {
97+
if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
98+
int height = grid.length, width = grid[0].length;
99+
int[][] dp = new int[height][width];
100+
dp[0][0] = grid[0][0];
101+
for(int i = 1; i < height; i++){
102+
dp[i][0] = grid[i][0] + dp[i - 1][0];
103+
}
104+
for(int i = 1; i < width; i++){
105+
dp[0][i] = grid[0][i] + dp[0][i - 1];
106+
}
107+
for(int i = 1; i < height; i++){
108+
for(int j = 1; j < width; j++){
109+
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
110+
}
111+
}
112+
return dp[height - 1][width - 1];
113+
}
114+
}
115+
```

‎leetcode/773. Sliding Puzzle.md

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -90,4 +90,54 @@ Note:
9090
returnnewString(arr);
9191
}
9292
}
93+
```
94+
95+
###Amazon session
96+
*Method1:BFS
97+
```Java
98+
classSolution {
99+
privatestaticfinalint[][] dir=newint[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
100+
publicintslidingPuzzle(int[][]board) {
101+
String target="123450";
102+
StringBuilder sb=newStringBuilder();
103+
for(int[] bb: board)
104+
for(int b: bb)
105+
sb.append(b);
106+
if(sb.toString().equals(target))return0;
107+
Set<String> visited=newHashSet<>();
108+
visited.add(sb.toString());
109+
Queue<String> q=newLinkedList<>();
110+
q.offer(sb.toString());
111+
int step=0;
112+
while(!q.isEmpty()){
113+
int size= q.size();
114+
for(int sz=0; sz< size; sz++){
115+
String cur= q.poll();
116+
int index= cur.indexOf("0");
117+
int x= index/3, y= index%3;
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<2&& ty>=0&& ty<3){
123+
String next= swap(cur, index, tx*3+ ty);
124+
if(visited.contains(next))continue;
125+
if(next.equals(target))return step+1;
126+
visited.add(next);
127+
q.offer(next);
128+
}
129+
}
130+
}
131+
step++;
132+
}
133+
return-1;
134+
}
135+
privateStringswap(Stringcur,inta,intb){
136+
char[] arr= cur.toCharArray();
137+
char temp= arr[a];
138+
arr[a]= arr[b];
139+
arr[b]= temp;
140+
returnnewString(arr);
141+
}
142+
}
93143
```

0 commit comments

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