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

Commitfd5926f

Browse files
committed
[Function add]
1. Add leetcode solutions with tag Amazon.
1 parent5fc32ef commitfd5926f

File tree

3 files changed

+239
-1
lines changed

3 files changed

+239
-1
lines changed

‎leetcode/289. Game of Life.md

Lines changed: 36 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -124,4 +124,39 @@ class Solution {
124124
return count;
125125
}
126126
}
127-
```
127+
```
128+
129+
###Amazon Session
130+
* Method 1: Bit Manipulation
131+
1. Use the second lowest bit to save the state of next generation.
132+
2. State compression: use a 3 * 3 matrix to traversal the board
133+
* if count == 3: current is live and 2 neighbors, current is dead and 3 neighbors(reproduction).
134+
* count - board = 3, current is live and 3 neighbors, so count is 4.
135+
```Java
136+
class Solution {
137+
public void gameOfLife(int[][] board) {
138+
if(board == null || board.length == 0 || board[0].length == 0) return;
139+
int height = board.length, width = board[0].length;
140+
for(int i = 0; i < height; i++){
141+
for(int j = 0; j < width; j++){
142+
//center is (i, j)
143+
int count = 0;
144+
for(int p = Math.max(0, i - 1); p <= Math.min(height - 1, i + 1); p++){
145+
for(int q = Math.max(0, j - 1); q <= Math.min(width - 1, j + 1); q++){
146+
count += board[p][q] & 1;
147+
}
148+
}
149+
if(count == 3 || count - board[i][j] == 3) board[i][j] |= 0B10;
150+
}
151+
}
152+
for(int i = 0; i < height; i++){
153+
for(int j = 0; j < width; j++){
154+
board[i][j] >>= 1;
155+
}
156+
}
157+
}
158+
}
159+
```
160+
161+
###Reference
162+
1.[花花酱 LeetCode 289. Game of Life](http://zxi.mytechroad.com/blog/simulation/leetcode-289-game-of-life/);

‎leetcode/445. Add Two Numbers II.md

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -171,5 +171,129 @@ Output: 7 -> 8 -> 0 -> 7
171171
}
172172
```
173173

174+
###AmazonSession
175+
*Method1: recursion
176+
```Java
177+
/**
178+
* Definition for singly-linked list.
179+
* public class ListNode {
180+
* int val;
181+
* ListNode next;
182+
* ListNode(int x) { val = x; }
183+
* }
184+
*/
185+
classSolution {
186+
privateint len1;
187+
privateint len2;
188+
publicListNodeaddTwoNumbers(ListNodel1,ListNodel2) {
189+
ListNode cur1= l1;
190+
int len1=0;
191+
while(cur1!=null){
192+
len1++;
193+
cur1= cur1.next;
194+
}
195+
ListNode cur2= l2;
196+
int len2=0;
197+
while(cur2!=null){
198+
len2++;
199+
cur2= cur2.next;
200+
}
201+
this.len1=Math.max(len1, len2);
202+
this.len2=Math.min(len1, len2);
203+
ListNode first= len1>= len2? l1: l2;
204+
ListNode second= len1>= len2? l2: l1;
205+
ListNode next= add(first,this.len1-1, second,this.len2-1);
206+
if(next.val<10)return next;
207+
else{
208+
int carry= next.val/10;
209+
next.val%=10;
210+
ListNode res=newListNode(carry);
211+
res.next= next;
212+
return res;
213+
}
214+
215+
}
216+
publicListNodeadd(ListNodel1,intindex1,ListNodel2,intindex2){// we garantee l1 is longer
217+
if(index1==0&& index2==0){
218+
returnnewListNode(l1.val+ l2.val);
219+
}elseif(index1> index2){
220+
ListNode next= add(l1.next, index1-1, l2, index2);
221+
int carry= next.val/10;
222+
next.val%=10;
223+
ListNode res=newListNode(carry+ l1.val);
224+
res.next= next;
225+
return res;
226+
}else{
227+
ListNode next= add(l1.next, index1-1, l2.next, index2-1);
228+
int carry= next.val/10;
229+
next.val%=10;
230+
ListNode res=newListNode(carry+ l1.val+ l2.val);
231+
res.next= next;
232+
return res;
233+
}
234+
}
235+
}
236+
```
237+
238+
*Method2: reverse the string
239+
```Java
240+
/**
241+
* Definition for singly-linked list.
242+
* public class ListNode {
243+
* int val;
244+
* ListNode next;
245+
* ListNode(int x) { val = x; }
246+
* }
247+
*/
248+
classSolution {
249+
publicListNodeaddTwoNumbers(ListNodel1,ListNodel2) {
250+
ListNode cur1= l1, pre1=null;
251+
while(cur1!=null){
252+
ListNode next= cur1.next;
253+
cur1.next= pre1;
254+
pre1= cur1;
255+
cur1= next;
256+
}
257+
ListNode cur2= l2, pre2=null;
258+
while(cur2!=null){
259+
ListNode next= cur2.next;
260+
cur2.next= pre2;
261+
pre2= cur2;
262+
cur2= next;
263+
}
264+
ListNode dummy=newListNode(1), cur= dummy;
265+
// pre1 && pre2 are the new heads
266+
int carry=0;
267+
while(pre1!=null|| pre2!=null){
268+
int sum=0;
269+
if(pre1!=null&& pre2!=null){
270+
sum= pre1.val+ pre2.val+ carry;
271+
pre1= pre1.next;
272+
pre2= pre2.next;
273+
}elseif(pre1!=null){
274+
sum= pre1.val+ carry;
275+
pre1= pre1.next;
276+
}else{
277+
sum= pre2.val+ carry;
278+
pre2= pre2.next;
279+
}
280+
carry= sum/10;
281+
cur.next=newListNode(sum%10);
282+
cur= cur.next;
283+
}
284+
if(carry!=0) cur.next=newListNode(1);
285+
ListNode res= dummy.next;
286+
cur2= res; pre2=null;
287+
while(cur2!=null){
288+
ListNode next= cur2.next;
289+
cur2.next= pre2;
290+
pre2= cur2;
291+
cur2= next;
292+
}
293+
return pre2;
294+
}
295+
}
296+
```
297+
174298
###Reference
175299
1. [Java O(n) recursive solution by counting the difference of length](https://leetcode.com/problems/add-two-numbers-ii/discuss/92643/Java-O(n)-recursive-solution-by-counting-the-difference-of-length)

‎leetcode/588. Design In-Memory File System.md

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -113,3 +113,82 @@ Note:
113113
* String param_4 = obj.readContentFromFile(filePath);
114114
*/
115115
```
116+
117+
###AmazonSession
118+
*Method1:TireTree
119+
```Java
120+
classFileSystem {
121+
privatestaticfinalclassNode{
122+
boolean isFile;
123+
String path;
124+
String content;
125+
Map<String,Node> map;//key is path name, value is child nodes.
126+
publicNode(Stringpath){
127+
this.map=newTreeMap<>();
128+
this.path= path;
129+
}
130+
}
131+
privateNode root;
132+
publicFileSystem() {
133+
this.root=newNode("/");
134+
root.path="/";
135+
this.root.isFile=false;
136+
}
137+
privateList<String>getListFromNode(Nodenode){
138+
List<String> res=newArrayList<>();
139+
if(node.isFile){
140+
res.add(node.path);
141+
return res;
142+
}
143+
res.addAll(node.map.keySet());
144+
res.sort((a, b)->{
145+
return a.compareTo(b);
146+
});
147+
return res;
148+
}
149+
publicList<String>ls(Stringpath) {
150+
String[] tokens= path.split("\\/");
151+
List<String> result=newArrayList<>();
152+
if(path.equals("/"))return getListFromNode(root);
153+
Node temp=this.root;
154+
for(int i=1; i< tokens.length; i++){
155+
if(!temp.map.containsKey(tokens[i]))return result;
156+
temp= temp.map.get(tokens[i]);
157+
}
158+
return getListFromNode(temp);
159+
}
160+
privateNodecreateOrGetByPath(Stringpath){
161+
String[] tokens= path.split("\\/");
162+
Node temp=this.root;
163+
for(int i=1; i< tokens.length; i++){
164+
if(!temp.map.containsKey(tokens[i])) temp.map.put(tokens[i],newNode(tokens[i]));
165+
temp= temp.map.get(tokens[i]);
166+
}
167+
return temp;
168+
}
169+
publicvoidmkdir(Stringpath) {
170+
createOrGetByPath(path);
171+
}
172+
publicvoidaddContentToFile(StringfilePath,Stringcontent) {
173+
Node file= createOrGetByPath(filePath);
174+
if(file.content==null){
175+
file.isFile=true;
176+
file.content= content;
177+
}else{
178+
file.content+= content;
179+
}
180+
}
181+
publicStringreadContentFromFile(StringfilePath) {
182+
Node file= createOrGetByPath(filePath);
183+
return file.content;
184+
}
185+
}
186+
/**
187+
* Your FileSystem object will be instantiated and called as such:
188+
* FileSystem obj = new FileSystem();
189+
* List<String> param_1 = obj.ls(path);
190+
* obj.mkdir(path);
191+
* obj.addContentToFile(filePath,content);
192+
* String param_4 = obj.readContentFromFile(filePath);
193+
*/
194+
```

0 commit comments

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