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

Commita56ebc3

Browse files
committed
[Function add]
1. Add leetcode solutions with amazon tag.
1 parentceef087 commita56ebc3

5 files changed

+226
-4
lines changed

‎leetcode/103. Binary Tree Zigzag Level Order Traversal.md

Lines changed: 41 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -124,4 +124,44 @@ class Solution {
124124
return result;
125125
}
126126
}
127-
```
127+
```
128+
129+
###Amazon session
130+
* Method 1: BFS
131+
1. Not really necessary to use stack or other data structure.
132+
2. Use normal bfs, just remember to add values to list using reverse flag.
133+
```Java
134+
/**
135+
* Definition for a binary tree node.
136+
* public class TreeNode {
137+
* int val;
138+
* TreeNode left;
139+
* TreeNode right;
140+
* TreeNode(int x) { val = x; }
141+
* }
142+
*/
143+
class Solution {
144+
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
145+
List<List<Integer>> result = new ArrayList<>();
146+
if(root == null) return result;
147+
Queue<TreeNode> q = new LinkedList<>();
148+
q.offer(root);
149+
boolean reverse = false;
150+
while(!q.isEmpty()){
151+
LinkedList<Integer> cur = new LinkedList<>();
152+
Queue<TreeNode> next = new LinkedList<>();
153+
while(!q.isEmpty()){
154+
TreeNode node = q.poll();
155+
if(!reverse) cur.add(node.val);
156+
else cur.addFirst(node.val);
157+
if(node.left != null) next.offer(node.left);
158+
if(node.right != null) next.offer(node.right);
159+
}
160+
result.add(cur);
161+
q = next;
162+
reverse = !reverse;
163+
}
164+
return result;
165+
}
166+
}
167+
```

‎leetcode/295.Find Median from Data Stream.md

Lines changed: 52 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,11 @@ addNum(3)
2323
findMedian() -> 2
2424
```
2525

26+
Follow up:
27+
* If all integer numbers from the stream are between 0 and 100, how would you optimize it?
28+
* If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?
29+
30+
2631
###Thinking:
2732
* Method 1:
2833
* 通过堆结构来实现，堆结构是通过优先级队列实现的。
@@ -133,4 +138,50 @@ class MedianFinder {
133138
* obj.addNum(num);
134139
* double param_2 = obj.findMedian();
135140
*/
136-
```
141+
```
142+
143+
###Amazon session
144+
* Method 1: PriorityQueue
145+
* Follow up:
146+
1. Count sort, record the appearance frequency of each number. Find the medium of according to the total numbers. O(100) = O(1)
147+
2. In this case, we need an integer array of length 100 and a hashmap for these numbers that are not in [0,100].
148+
```Java
149+
class MedianFinder {
150+
private PriorityQueue<Integer> minQ;
151+
private PriorityQueue<Integer> maxQ;
152+
/** initialize your data structure here. */
153+
public MedianFinder() {
154+
this.minQ = new PriorityQueue<>((a, b)->{
155+
return a - b;
156+
});
157+
this.maxQ = new PriorityQueue<>((a, b)->{
158+
return b - a;
159+
});
160+
}
161+
162+
public void addNum(int num) {
163+
if(minQ.isEmpty() || num <= minQ.peek()){
164+
maxQ.offer(num);
165+
if(maxQ.size() > minQ.size()) minQ.offer(maxQ.poll());
166+
}else{
167+
minQ.offer(num);
168+
if(minQ.size() - maxQ.size() > 1) maxQ.offer(minQ.poll());
169+
}
170+
}
171+
172+
public double findMedian() {
173+
if(maxQ.size() != minQ.size()) return (double)minQ.peek();
174+
else return (minQ.peek() + maxQ.peek()) / 2.0D;
175+
}
176+
}
177+
178+
/**
179+
* Your MedianFinder object will be instantiated and called as such:
180+
* MedianFinder obj = new MedianFinder();
181+
* obj.addNum(num);
182+
* double param_2 = obj.findMedian();
183+
*/
184+
```
185+
186+
###Reference
187+
1.[Solutions to follow-ups](https://leetcode.com/problems/find-median-from-data-stream/discuss/275207/Solutions-to-follow-ups)

‎leetcode/642. Design Search Autocomplete System.md

Lines changed: 85 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -134,4 +134,88 @@ Note:
134134
* AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
135135
* List<String> param_1 = obj.input(c);
136136
*/
137-
```
137+
```
138+
139+
###Amazon session
140+
*Method1:TrieTree+HashMap+PriorityQueue
141+
```Java
142+
classAutocompleteSystem {
143+
privatestaticfinalclassNode{
144+
Map<Character,Node> childs;// key: next character, value: child node.
145+
Map<String,Integer> freq;// key: sentence, value: appear number.
146+
publicNode(){
147+
this.childs=newHashMap<>();
148+
this.freq=newHashMap<>();
149+
}
150+
}
151+
privateNode root;
152+
privatevoidaddToTree(Strings,inttime){
153+
char[] arr= s.toCharArray();
154+
Node temp= root;
155+
for(char c: arr){
156+
if(!temp.childs.containsKey(c)){
157+
temp.childs.put(c,newNode());
158+
}
159+
temp= temp.childs.get(c);
160+
int appear= temp.freq.getOrDefault(s,0);
161+
temp.freq.put(s, appear+ time);
162+
}
163+
}
164+
privateStringBuilder sb;
165+
privateNode search;
166+
publicAutocompleteSystem(String[]sentences,int[]times) {
167+
this.root=newNode();
168+
for(int i=0; i< sentences.length; i++){
169+
addToTree(sentences[i], times[i]);
170+
}
171+
this.sb=newStringBuilder();
172+
this.search=this.root;
173+
}
174+
privatestaticclassPair{
175+
int freq;
176+
String sentence;
177+
publicPair(intfreq,Stringsentence){
178+
this.freq= freq;
179+
this.sentence= sentence;
180+
}
181+
}
182+
privateList<String>getTopFromNode(Nodenode){
183+
List<String> result=newArrayList<>();
184+
PriorityQueue<Pair> pq=newPriorityQueue<>((a, b)->{
185+
if(b.freq!= a.freq)return b.freq- a.freq;
186+
elsereturn a.sentence.compareTo(b.sentence);
187+
});
188+
for(Map.Entry<String,Integer> entry: node.freq.entrySet()){
189+
pq.offer(newPair(entry.getValue(), entry.getKey()));
190+
}
191+
while(!pq.isEmpty()&& result.size()<3){
192+
result.add(pq.poll().sentence);
193+
}
194+
return result;
195+
}
196+
publicList<String>input(charc) {
197+
List<String> result=newArrayList<>();
198+
if(c!='#') sb.append(c);
199+
if(search!=null&& c!='#'){
200+
if(search.childs.containsKey(c)){// normal character and is not #.
201+
search= search.childs.get(c);
202+
result= getTopFromNode(search);
203+
}else{// doesn't contains current node.
204+
search=null;
205+
}
206+
}
207+
if(c=='#'){
208+
addToTree(sb.toString(),1);
209+
sb=newStringBuilder();
210+
search=this.root;
211+
}
212+
return result;// if parent node hasn't existed
213+
}
214+
}
215+
216+
/**
217+
* Your AutocompleteSystem object will be instantiated and called as such:
218+
* AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
219+
* List<String> param_1 = obj.input(c);
220+
*/
221+
```

‎leetcode/763. Partition Labels.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,3 +48,31 @@ Note:
4848
}
4949
}
5050
```
51+
52+
###Amazon Session
53+
* Method 1: Greedy
54+
* We can use array to replace map in this question to speed up.
55+
```Java
56+
class Solution {
57+
public List<Integer> partitionLabels(String S) {
58+
int[] last = new int[26];
59+
char[] arr = S.toCharArray();
60+
for(int i = arr.length - 1; i >= 0; i--){ // record the last appearance of each letter.
61+
if(last[arr[i] - 'a'] == 0){
62+
last[arr[i] - 'a'] = i;
63+
}
64+
}
65+
int index = 0;
66+
int end = 0;
67+
List<Integer> result = new ArrayList<>();
68+
while(index < arr.length){ // get start and end.
69+
int start = index;
70+
while(index <= end){
71+
end = Math.max(end, last[arr[index++] - 'a']);
72+
}
73+
result.add(++end - start);
74+
}
75+
return result;
76+
}
77+
}
78+
```

‎leetcode/957. Prison Cells After N Days.md

Lines changed: 20 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,4 +59,23 @@ Note:
5959
return cells;
6060
}
6161
}
62-
```
62+
```
63+
64+
###Amazon session
65+
*Method1:Math
66+
1.We found that the result repeats after every14 iterations.
67+
```Java
68+
classSolution {
69+
publicint[]prisonAfterNDays(int[]cells,intN) {
70+
N=N%14==0?14:N%14;
71+
for(int i=0; i<N; i++){
72+
int[] next=newint[8];
73+
for(int j=1; j<7; j++){
74+
next[j]= cells[j-1]== cells[j+1]?1:0;
75+
}
76+
cells= next;
77+
}
78+
return cells;
79+
}
80+
}
81+
```

0 commit comments

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