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

Commit9a69639

Browse files
committed
[Function add]
1. Add leetcode solutions with amazon tag.
1 parent60a6f1e commit9a69639

4 files changed

+197
-26
lines changed

‎leetcode/124. Binary Tree Maximum Path Sum.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -86,4 +86,33 @@ class Solution {
8686
return Math.max(node.val, Math.max(node.val + left, node.val + right));
8787
}
8888
}
89+
```
90+
91+
###Amazon Session
92+
* Method 1: dfs + traversal 2 childs and return one
93+
```Java
94+
/**
95+
* Definition for a binary tree node.
96+
* public class TreeNode {
97+
* int val;
98+
* TreeNode left;
99+
* TreeNode right;
100+
* TreeNode(int x) { val = x; }
101+
* }
102+
*/
103+
class Solution {
104+
private int result = Integer.MIN_VALUE;
105+
public int maxPathSum(TreeNode root) {
106+
dfs(root);
107+
return this.result;
108+
}
109+
private int dfs(TreeNode root){
110+
if(root == null) return 0;
111+
int left = Math.max(dfs(root.left), 0);
112+
int right = Math.max(dfs(root.right), 0);
113+
int res = Math.max(root.val, left + right + root.val);
114+
this.result = Math.max(result, res);
115+
return Math.max(Math.max(left, right) + root.val, root.val);
116+
}
117+
}
89118
```

‎leetcode/347. Top K Frequent Elements.md

Lines changed: 59 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -17,29 +17,63 @@ Output: [1]
1717

1818
###Thinking:
1919
* Method 1:
20+
```Java
21+
class Solution {
22+
public List<Integer> topKFrequent(int[] nums, int k) {
23+
Map<Integer, Integer> map = new HashMap<>();
24+
List<Integer> res = new ArrayList<>();
25+
for(int num : nums){
26+
map.put(num, map.containsKey(num)?map.get(num) + 1: 1);
27+
}
28+
Set<Map.Entry<Integer, Integer>> set = map.entrySet();
29+
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>(){
30+
@Override
31+
public int compare(Map.Entry<Integer, Integer> n1, Map.Entry<Integer, Integer> n2){
32+
return n2.getValue() - n1.getValue();
33+
}
34+
});
35+
for(Map.Entry<Integer, Integer> entry: set){
36+
pq.offer(entry);
37+
}
38+
for(int i = 0; i < k; i++){
39+
res.add(pq.poll().getKey());
40+
}
41+
return res;
42+
}
43+
}
44+
```
2045

21-
```Java
22-
classSolution {
23-
publicList<Integer>topKFrequent(int[]nums,intk) {
24-
Map<Integer,Integer> map=newHashMap<>();
25-
List<Integer> res=newArrayList<>();
26-
for(int num: nums){
27-
map.put(num, map.containsKey(num)?map.get(num)+1:1);
28-
}
29-
Set<Map.Entry<Integer,Integer>> set= map.entrySet();
30-
PriorityQueue<Map.Entry<Integer,Integer>> pq=newPriorityQueue<>(newComparator<Map.Entry<Integer,Integer>>(){
31-
@Override
32-
publicintcompare(Map.Entry<Integer,Integer>n1,Map.Entry<Integer,Integer>n2){
33-
return n2.getValue()- n1.getValue();
34-
}
35-
});
36-
for(Map.Entry<Integer,Integer> entry: set){
37-
pq.offer(entry);
38-
}
39-
for(int i=0; i< k; i++){
40-
res.add(pq.poll().getKey());
41-
}
42-
return res;
43-
}
44-
}
45-
```
46+
* Method 2: bucket sort
47+
1. Take the appearance freq for each number.
48+
2. Do another index count to according to their appearance.
49+
3. From the end to begin, add k values to result.
50+
```Java
51+
class Solution {
52+
public List<Integer> topKFrequent(int[] nums, int k) {
53+
List<Integer> result = new ArrayList<>();
54+
if(nums == null || nums.length == 0) return result;
55+
Map<Integer, Integer> map = new HashMap<>();
56+
int max = 1, freqMax = 0;
57+
for(int n : nums){
58+
max = Math.max(max, n);
59+
map.put(n, map.getOrDefault(n, 0) + 1);
60+
freqMax = Math.max(freqMax, map.get(n));
61+
}
62+
List[] arr = new List[freqMax + 1];
63+
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
64+
int freq = entry.getValue();
65+
if(arr[freq] == null) arr[freq] = new ArrayList<>();
66+
arr[freq].add(entry.getKey());
67+
}
68+
for(int i = arr.length - 1; i >= 0 && k > 0; i--){
69+
if(arr[i] == null) continue;
70+
result.addAll(arr[i]);
71+
k -= arr[i].size();
72+
}
73+
return result;
74+
}
75+
}
76+
```
77+
78+
###Reference
79+
1.[Java O(n) solution using Buckets](https://leetcode.com/problems/top-k-frequent-elements/discuss/306454/Java-O(n)-solution-using-Buckets)

‎leetcode/4. Median of Two Sorted Arrays.md

Lines changed: 65 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -134,4 +134,68 @@ class Solution {
134134
return (c1 + c2) * 0.5;
135135
}
136136
}
137-
```
137+
```
138+
139+
###Amazon Session
140+
* Method 1: Merge and find medium
141+
```Java
142+
class Solution {
143+
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
144+
int[] arr = new int[nums1.length + nums2.length];
145+
int index1 = 0, index2 = 0, index = 0;
146+
while(index1 < nums1.length && index2 < nums2.length){
147+
if(nums1[index1] <= nums2[index2]){
148+
arr[index++] = nums1[index1++];
149+
}else{
150+
arr[index++] = nums2[index2++];
151+
}
152+
}
153+
if(index1 == nums1.length){ // nums1 reached the end, need to append nums2
154+
for(; index < nums1.length + nums2.length; index++){
155+
arr[index] = nums2[index2++];
156+
}
157+
}else{
158+
for(; index < nums1.length + nums2.length; index++){
159+
arr[index] = nums1[index1++];
160+
}
161+
}
162+
return arr.length % 2 == 1 ? (double)arr[arr.length/2]:
163+
(double)(arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2;
164+
}
165+
}
166+
```
167+
168+
* Method 2: Binary search
169+
![Imgur](https://i.imgur.com/wU6ojSC.png)
170+
1. Medium value is created by C1 and C2.
171+
2. There are totally K = (len1 + len2 + 1) / 2 will be selected to create the left side of the merged array.
172+
3. We use m1 numbers from nums1 and m2 values from nums2, k = m1 + m2.
173+
4. The constraint for binary search is nums1[m1 - 1] <= nums2[m2 - 1].
174+
5. If total number of values are even, result is (Ck + Ck-1) / 2 else Ck-1.
175+
```Java
176+
classSolution {
177+
publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {
178+
int len1= nums1.length, len2= nums2.length;
179+
if(len2< len1)return findMedianSortedArrays(nums2, nums1);
180+
int k= (len1+ len2+1)/2;
181+
int l=0, r= len1, m1=0;
182+
while(l< r){
183+
m1= l+ (r- l)/2;
184+
int m2= k- m1;
185+
if(nums1[m1]< nums2[m2-1]) l= m1+1;
186+
else r= m1;
187+
}
188+
m1= l;
189+
int c1=Math.max(m1<=0?Integer.MIN_VALUE: nums1[m1-1],
190+
k- m1<=0?Integer.MIN_VALUE: nums2[k- m1-1]);
191+
if((len1+ len2)%2==1)
192+
return (double)c1;
193+
int c2=Math.min(m1>= len1?Integer.MAX_VALUE: nums1[m1],
194+
k- m1>= len2?Integer.MAX_VALUE: nums2[k- m1]);
195+
return (double)(c1+ c2)/2;
196+
}
197+
}
198+
```
199+
200+
###Reference
201+
1. [花花酱LeetCode4.Median ofTwoSortedArrays](https://zxi.mytechroad.com/blog/algorithms/binary-search/leetcode-4-median-of-two-sorted-arrays/)

‎leetcode/490. The Maze.md

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -166,4 +166,48 @@ private static boolean searchBFS(int[][] maze, int[] start, int[] des, boolean[]
166166
return new int[]{tx - dir[d][0], ty - dir[d][1]};
167167
}
168168
}
169+
```
170+
171+
###Amazon session
172+
* Method 1: dfs
173+
```Java
174+
class Solution {
175+
private static final int[][] dir = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
176+
private int[][] maze;
177+
private int height, width;
178+
private int[] destination;
179+
private Set<Integer> visited;
180+
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
181+
this.maze = maze;
182+
this.height = maze.length;
183+
this.width = maze[0].length;
184+
this.destination = destination;
185+
this.visited = new HashSet<>();
186+
if(start[0] == destination[0] && start[1] == destination[1]) return true;
187+
visited.add(start[0] * width + start[1]);
188+
for(int i = 0; i < 4; i++)
189+
if(dfs(start[0], start[1], i)) return true;
190+
return false;
191+
}
192+
private boolean dfs(int x, int y, int pre){
193+
if(x == destination[0] && y == destination[1]) return true;
194+
int tx = 0, ty = 0;
195+
for(int d = 0; d < 4; d++){
196+
if(d + pre == 3) continue;
197+
tx = x + dir[d][0];
198+
ty = y + dir[d][1];
199+
while(tx >= 0 && tx < height && ty >= 0 && ty < width && maze[tx][ty] == 0){
200+
tx += dir[d][0];
201+
ty += dir[d][1];
202+
}
203+
tx -= dir[d][0];
204+
ty -= dir[d][1];
205+
if(!visited.contains(tx * width + ty)){
206+
visited.add(tx * width + ty);
207+
if(dfs(tx, ty, d)) return true;
208+
}
209+
}
210+
return false;
211+
}
212+
}
169213
```

0 commit comments

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