Skip to content

Commit df53f9c

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode solutions with tag amazon.
1 parent a3a0726 commit df53f9c

File tree

4 files changed

+278
-0
lines changed

4 files changed

+278
-0
lines changed

‎leetcode/200. Number of Islands.md

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -220,3 +220,55 @@ class Solution {
220220
}
221221
}
222222
```
223+
224+
### Fourth Time
225+
* Method 1: uf
226+
```Java
227+
class Solution {
228+
private int[] uf;
229+
private static final int[][] dir = new int[][]{{0, 1}, {1, 0}};
230+
public int numIslands(char[][] grid) {
231+
if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
232+
int height = grid.length;
233+
int width = grid[0].length;
234+
this.uf = new int[height * width];
235+
for(int i = 0; i < height; i++){
236+
for(int j = 0; j < width; j++){
237+
if(grid[i][j] == '1')
238+
uf[i * width + j] = i * width + j;
239+
else uf[i * width + j] = -1;
240+
}
241+
}
242+
for(int i = 0; i < height; i++){
243+
for(int j = 0; j < width; j++){
244+
if(grid[i][j] == '0') continue;
245+
int tx = 0, ty = 0;
246+
for(int d = 0; d < 2; d++){
247+
tx = i + dir[d][0];
248+
ty = j + dir[d][1];
249+
if(tx >= 0 && tx < height && ty >= 0 && ty < width && grid[tx][ty] == '1'){
250+
union(i * width + j, tx * width + ty);
251+
}
252+
}
253+
}
254+
}
255+
int count = 0;
256+
for(int i = 0; i < uf.length; i++){
257+
if(uf[i] == i) count++;
258+
}
259+
return count;
260+
}
261+
private int find(int i){
262+
if(uf[i] != i){
263+
uf[i] = find(uf[i]);
264+
}
265+
return uf[i];
266+
}
267+
private void union(int i, int j){
268+
int p = find(i);
269+
int q = find(j);
270+
uf[p] = q;
271+
}
272+
273+
}
274+
```

‎leetcode/261. Graph Valid Tree.md

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
## 261. Graph Valid Tree
2+
3+
### Question
4+
Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
5+
6+
```
7+
Example 1:
8+
9+
Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
10+
Output: true
11+
12+
Example 2:
13+
14+
Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
15+
Output: false
16+
```
17+
18+
Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.
19+
20+
21+
### Solution
22+
* Method 1: Union find
23+
```Java
24+
class Solution {
25+
private int[] uf;
26+
public boolean validTree(int n, int[][] edges) {
27+
this.uf = new int[n];
28+
for(int i = 0; i < n; i++) uf[i] = i;
29+
for(int[] edge : edges){
30+
int p = find(edge[0]);
31+
int q = find(edge[1]);
32+
if(p == q) return false;
33+
uf[p] = q;
34+
}
35+
int count = 0;
36+
for(int i = 0; i < n; i++)
37+
if(uf[i] == i) count++;
38+
return count == 1;
39+
}
40+
private int find(int i){
41+
if(uf[i] != i){
42+
uf[i] = find(uf[i]);
43+
}
44+
return uf[i];
45+
}
46+
}
47+
```

‎leetcode/269. Alien Dictionary.md

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
## 269. Alien Dictionary
2+
3+
### Question
4+
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
5+
6+
```
7+
Example 1:
8+
9+
Input:
10+
[
11+
"wrt",
12+
"wrf",
13+
"er",
14+
"ett",
15+
"rftt"
16+
]
17+
18+
Output: "wertf"
19+
20+
Example 2:
21+
22+
Input:
23+
[
24+
"z",
25+
"x"
26+
]
27+
28+
Output: "zx"
29+
30+
Example 3:
31+
32+
Input:
33+
[
34+
"z",
35+
"x",
36+
"z"
37+
]
38+
39+
Output: ""
40+
41+
Explanation: The order is invalid, so return "".
42+
```
43+
44+
Note:
45+
* You may assume all letters are in lowercase.
46+
* You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
47+
* If the order is invalid, return an empty string.
48+
* There may be multiple valid order of letters, return any one of them is fine.
49+
50+
### Solution
51+
* Method 1: Topological sort
52+
```Java
53+
class Solution {
54+
public String alienOrder(String[] words) {
55+
Map<Character, Set<Character>> adj = new HashMap<>();
56+
Map<Character, Integer> indegree = new HashMap<>();
57+
for(String word: words){
58+
for(char c : word.toCharArray()){
59+
indegree.put(c, 0);
60+
}
61+
}
62+
for(int i = 1; i < words.length; i++){
63+
int maxLen = Math.min(words[i].length(), words[i - 1].length());
64+
char[] arr1 = words[i - 1].toCharArray(), arr2 = words[i].toCharArray();
65+
for(int j = 0; j < maxLen; j++){
66+
if(arr1[j] != arr2[j]){
67+
Set<Character> set = adj.containsKey(arr1[j]) ? adj.get(arr1[j]): new HashSet<>();
68+
if(!set.contains(arr2[j])){
69+
set.add(arr2[j]);
70+
adj.put(arr1[j], set);
71+
indegree.put(arr2[j], indegree.get(arr2[j]) + 1);
72+
}
73+
break;
74+
}
75+
}
76+
}
77+
Queue<Character> q = new LinkedList<>();
78+
for(Character c : indegree.keySet()){
79+
if(indegree.get(c) == 0) q.offer(c);
80+
}
81+
StringBuilder result = new StringBuilder();
82+
while(!q.isEmpty()){
83+
char c = q.poll();
84+
result.append(c);
85+
if(adj.get(c) == null) continue;
86+
for(Character neigh: adj.get(c)){
87+
indegree.put(neigh, indegree.get(neigh) - 1);
88+
if(indegree.get(neigh) == 0) q.offer(neigh);
89+
}
90+
}
91+
for(int count: indegree.values()){
92+
if(count > 0) return "";
93+
}
94+
return result.toString();
95+
}
96+
}
97+
```

‎leetcode/285. Inorder Successor in BST.md

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
## 285. Inorder Successor in BST
2+
3+
### Question
4+
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
5+
6+
The successor of a node p is the node with the smallest key greater than p.val.
7+
8+
```
9+
Example 1:
10+
11+
Input: root = [2,1,3], p = 1
12+
Output: 2
13+
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
14+
15+
Example 2:
16+
17+
Input: root = [5,3,6,2,4,null,null,1], p = 6
18+
Output: null
19+
Explanation: There is no in-order successor of the current node, so the answer is null.
20+
```
21+
22+
Note:
23+
* If the given node has no in-order successor in the tree, return null.
24+
* It's guaranteed that the values of the tree are unique.
25+
26+
27+
28+
### Solution
29+
* Method 1: BST
30+
```Java
31+
/**
32+
* Definition for a binary tree node.
33+
* public class TreeNode {
34+
* int val;
35+
* TreeNode left;
36+
* TreeNode right;
37+
* TreeNode(int x) { val = x; }
38+
* }
39+
*/
40+
class Solution {
41+
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
42+
if(root == null) return null;
43+
if(root.val <= p.val) return inorderSuccessor(root.right, p);
44+
else{
45+
TreeNode left = inorderSuccessor(root.left, p);
46+
return left == null ? root: left;
47+
}
48+
}
49+
}
50+
```
51+
52+
* Method 2: inorder traversal
53+
```Java
54+
/**
55+
* Definition for a binary tree node.
56+
* public class TreeNode {
57+
* int val;
58+
* TreeNode left;
59+
* TreeNode right;
60+
* TreeNode(int x) { val = x; }
61+
* }
62+
*/
63+
class Solution {
64+
private List<TreeNode> result;
65+
private int index = 0;
66+
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
67+
result = new ArrayList<>();
68+
dfs(root, p);
69+
if(index >= result.size()) return null;
70+
return result.get(index);
71+
}
72+
private void dfs(TreeNode node, TreeNode p){
73+
if(node == null) return;
74+
else{
75+
dfs(node.left, p);
76+
result.add(node);
77+
if(p == node) index = result.size();
78+
dfs(node.right, p);
79+
}
80+
}
81+
}
82+
```

0 commit comments

Comments
 (0)