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

Commit25cb3d6

Browse files
committed
[Function add]
1. Add leetcode solutions with amazon tag.
1 parenta56ebc3 commit25cb3d6

4 files changed

+260
-0
lines changed

‎leetcode/273. Integer to English Words.md

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,3 +69,52 @@ Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Th
6969
}
7070
}
7171
```
72+
73+
###Amazon Session
74+
* Method 1: Math
75+
```Java
76+
class Solution {
77+
private static final String[] units = new String[]{"", "Thousand", "Million", "Billion"};
78+
private static final String[] ones = new String[]{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
79+
private static String[] tens = new String[]{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
80+
private static String[] overTens = new String[]{"", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
81+
public String numberToWords(int num) {
82+
if(num == 0) return "Zero";
83+
int bigUnit = 0;
84+
String result = "";
85+
while(num != 0){
86+
String cur = parseThree(num % 1000);
87+
if(cur.length() != 0){
88+
result = cur
89+
+ (bigUnit == 0 ? "": " ")
90+
+ units[bigUnit]
91+
+ (result.length() == 0 ? "": " ")
92+
+ result;
93+
}
94+
bigUnit++;
95+
num /= 1000;
96+
}
97+
return result;
98+
}
99+
private String parseThree(int num){
100+
String result = "";
101+
if(num % 100 > 10 && num % 100 < 20){
102+
result = overTens[num % 100 - 10];
103+
num /= 100;
104+
}else{
105+
if(num % 10 != 0){
106+
result = ones[num % 10];
107+
}
108+
num /= 10;
109+
if(num % 10 != 0){
110+
result = tens[num % 10] + (result.length() == 0 ? "" : " ") + result;
111+
}
112+
num /= 10;
113+
}
114+
if(num % 10 != 0){
115+
result = ones[num % 10] + " Hundred" + (result.length() == 0 ? "": " ") + result;
116+
}
117+
return result;
118+
}
119+
}
120+
```

‎leetcode/348. Design Tic-Tac-Toe.md

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -130,3 +130,116 @@ Could you do better than O(n2) per move() operation?
130130
* int param_1 = obj.move(row,col,player);
131131
*/
132132
```
133+
134+
###Amazon Session
135+
* Method 1: Design
136+
```Java
137+
class TicTacToe {
138+
private int[][] g;
139+
private int n;
140+
/** Initialize your data structure here. */
141+
public TicTacToe(int n) {
142+
this.g = new int[n][n];
143+
this.n = n;
144+
}
145+
146+
/** Player {player} makes a move at ({row}, {col}).
147+
@param row The row of the board.
148+
@param col The column of the board.
149+
@param player The player, can be either 1 or 2.
150+
@return The current winning condition, can be either:
151+
0: No one wins.
152+
1: Player 1 wins.
153+
2: Player 2 wins. */
154+
public int move(int row, int col, int player) {
155+
g[row][col] = player;
156+
if(checkHorizontal(row, col, player) || checkVerticle(row, col, player) || checkDiagnonal(row, col, player)) return player;
157+
return 0;
158+
}
159+
private boolean checkHorizontal(int row, int col, int player){
160+
int temp = col - 1;
161+
while(temp >= 0){
162+
if(g[row][temp--] != player) return false;
163+
}
164+
temp = col + 1;
165+
while(temp < n){
166+
if(g[row][temp++] != player) return false;
167+
}
168+
return true;
169+
}
170+
private boolean checkVerticle(int row, int col, int player){
171+
int temp = row - 1;
172+
while(temp >= 0){
173+
if(g[temp--][col] != player) return false;
174+
}
175+
temp = row + 1;
176+
while(temp < n){
177+
if(g[temp++][col] != player) return false;
178+
}
179+
return true;
180+
}
181+
private boolean checkDiagnonal(int row, int col, int player){
182+
int tx = 0, ty = 0;
183+
boolean flag1 = true;
184+
while(tx < n){
185+
flag1 &= g[tx][tx++] == player;
186+
}
187+
tx = 0; ty = n - 1;
188+
boolean flag2 = true;
189+
while(tx < n){
190+
flag2 &= g[tx++][ty--] == player;
191+
}
192+
return flag1 || flag2;
193+
}
194+
}
195+
196+
/**
197+
* Your TicTacToe object will be instantiated and called as such:
198+
* TicTacToe obj = new TicTacToe(n);
199+
* int param_1 = obj.move(row,col,player);
200+
*/
201+
```
202+
203+
* Method 2:
204+
1. We don't have to record all of the actions.
205+
2. We only need to record all the numebrs in one row or col.
206+
```Java
207+
class TicTacToe {
208+
private int[][] rows;
209+
private int[][] cols;
210+
private int[][] digs;
211+
private int n;
212+
/** Initialize your data structure here. */
213+
public TicTacToe(int n) {
214+
this.rows = new int[n][2];
215+
this.cols = new int[n][2];
216+
this.digs = new int[2][2];
217+
this.n = n;
218+
}
219+
220+
/** Player {player} makes a move at ({row}, {col}).
221+
@param row The row of the board.
222+
@param col The column of the board.
223+
@param player The player, can be either 1 or 2.
224+
@return The current winning condition, can be either:
225+
0: No one wins.
226+
1: Player 1 wins.
227+
2: Player 2 wins. */
228+
public int move(int row, int col, int player) {
229+
if(++rows[row][player - 1] == n) return player;
230+
if(++cols[col][player - 1] == n) return player;
231+
if(row == col && ++digs[0][player - 1] == n) return player;
232+
if(row + col == n - 1 && ++digs[1][player - 1] == n) return player;
233+
return 0;
234+
}
235+
}
236+
237+
/**
238+
* Your TicTacToe object will be instantiated and called as such:
239+
* TicTacToe obj = new TicTacToe(n);
240+
* int param_1 = obj.move(row,col,player);
241+
*/
242+
```
243+
244+
###Reference
245+
1.[Java concise O(1) easy understand](https://leetcode.com/problems/design-tic-tac-toe/discuss/296370/Java-concise-O(1)-easy-understand)

‎leetcode/675. Cut Off Trees for Golf Event.md

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -111,5 +111,64 @@ Hint: size of the given matrix will not exceed 50x50.
111111
}
112112
```
113113

114+
###AmazonSession
115+
*Method1:PriorityQueue+ bfs
116+
```Java
117+
classSolution {
118+
privateint[][] g;
119+
privatestaticfinalint[][] dir=newint[][]{{0,1}, {0,-1}, {1,0}, {-1,0}};
120+
publicintcutOffTree(List<List<Integer>>forest) {
121+
if(forest.get(0).get(0)==0)return-1;
122+
int height= forest.size(), width= forest.get(0).size();
123+
//a[0]: value, a[1]: row, a[2]: col
124+
PriorityQueue<int[]> pq=newPriorityQueue<>((a, b)->{
125+
return a[0]- b[0];
126+
});
127+
g=newint[height][width];
128+
for(int i=0; i< height; i++){
129+
for(int j=0; j< width; j++){
130+
g[i][j]= forest.get(i).get(j);
131+
if(g[i][j]!=0){
132+
pq.offer(newint[]{g[i][j], i, j});
133+
}
134+
}
135+
}
136+
int[] last=newint[]{0,0};
137+
int result=0;
138+
LABEL:
139+
while(!pq.isEmpty()){
140+
int[] dest= pq.poll();
141+
Queue<int[]> q=newLinkedList<>();
142+
Set<Integer> visited=newHashSet<>();
143+
visited.add(last[0]* width+ last[1]);
144+
q.offer(last);
145+
int step=0;
146+
while(!q.isEmpty()){
147+
int size= q.size();
148+
for(int sz=0; sz< size; sz++){
149+
int[] cur= q.poll();
150+
if(cur[0]== dest[1]&& cur[1]== dest[2]){
151+
result+= step;
152+
last= cur;
153+
continueLABEL;
154+
}
155+
int tx=0, ty=0;
156+
for(int d=0; d<4; d++){
157+
tx= cur[0]+ dir[d][0];
158+
ty= cur[1]+ dir[d][1];
159+
if(tx>=0&& tx< height&& ty>=0&& ty< width&&!visited.contains(tx* width+ ty)&& g[tx][ty]!=0){
160+
visited.add(tx* width+ ty);
161+
q.offer(newint[]{tx, ty});
162+
}
163+
}
164+
}
165+
step++;
166+
}
167+
return-1;
168+
}
169+
return result;
170+
}
171+
}
172+
```
114173
###Reference
115174
1. [花花酱LeetCode675.CutOffTreesforGolfEvent- 刷题找工作EP55](https://www.youtube.com/watch?v=OFkLC30OxXM)

‎leetcode/909. Snakes and Ladders.md

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -76,3 +76,42 @@ Note:
7676
}
7777
}
7878
```
79+
80+
###Amazon Session
81+
* Method 1: BFS(because it is shortest path question)
82+
```Java
83+
class Solution {
84+
private int N;
85+
private int[] numberToIndex(int num){ // return the row and col index of current number
86+
num--; // change to 0-based
87+
int diff = num / N;
88+
int rem = num % N;
89+
return new int[]{N - 1 - num / N, diff % 2 == 0 ? rem: N - 1 - rem};
90+
}
91+
public int snakesAndLadders(int[][] board) {
92+
this.N = board.length;
93+
int dest = N * N;
94+
Queue<Integer> q = new LinkedList<>();
95+
q.offer(1);
96+
int step = 0;
97+
Set<Integer> visited = new HashSet<>();
98+
while(!q.isEmpty()){
99+
int sz = q.size();
100+
for(int p = 0; p < sz; p++){
101+
int cur = q.poll();
102+
if(cur == dest) return step;
103+
for(int i = 1; i <= 6; i++){
104+
int next = cur + i;
105+
if(visited.contains(next) || next > dest) continue;
106+
visited.add(next);
107+
int[] index = numberToIndex(next);
108+
if(board[index[0]][index[1]] == -1) q.offer(next);
109+
else q.offer(board[index[0]][index[1]]);
110+
}
111+
}
112+
step++;
113+
}
114+
return -1;
115+
}
116+
}
117+
```

0 commit comments

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