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

Commitec1f261

Browse files
committed
[Function add]
1. Add leetcode solutions with tag Amazon.
1 parentfd5926f commitec1f261

3 files changed

+172
-1
lines changed

‎leetcode/341. Flatten Nested List Iterator.md

Lines changed: 58 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,4 +75,61 @@ public class NestedIterator implements Iterator<Integer> {
7575
* NestedIterator i = new NestedIterator(nestedList);
7676
* while (i.hasNext()) v[f()] = i.next();
7777
*/
78-
```
78+
```
79+
80+
###Amazon Session
81+
* Method 1: recursion
82+
```Java
83+
/**
84+
* // This is the interface that allows for creating nested lists.
85+
* // You should not implement it, or speculate about its implementation
86+
* public interface NestedInteger {
87+
*
88+
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
89+
* public boolean isInteger();
90+
*
91+
* // @return the single integer that this NestedInteger holds, if it holds a single integer
92+
* // Return null if this NestedInteger holds a nested list
93+
* public Integer getInteger();
94+
*
95+
* // @return the nested list that this NestedInteger holds, if it holds a nested list
96+
* // Return null if this NestedInteger holds a single integer
97+
* public List<NestedInteger> getList();
98+
* }
99+
*/
100+
public class NestedIterator implements Iterator<Integer> {
101+
private List<Integer> list;
102+
private int index;
103+
public NestedIterator(List<NestedInteger> nestedList) {
104+
if(nestedList == null || nestedList.size() == 0) return;
105+
this.list = new ArrayList<>();
106+
getValues(nestedList);
107+
}
108+
private void getValues(List<NestedInteger> list){
109+
for(NestedInteger obj : list){
110+
if(obj.isInteger()) this.list.add(obj.getInteger());
111+
else{
112+
List<NestedInteger> next = obj.getList();
113+
getValues(next);
114+
}
115+
}
116+
}
117+
118+
@Override
119+
public Integer next() {
120+
return this.list.get(index++);
121+
}
122+
123+
@Override
124+
public boolean hasNext() {
125+
if(this.list == null) return false;
126+
return index < this.list.size();
127+
}
128+
}
129+
130+
/**
131+
* Your NestedIterator object will be instantiated and called as such:
132+
* NestedIterator i = new NestedIterator(nestedList);
133+
* while (i.hasNext()) v[f()] = i.next();
134+
*/
135+
```

‎leetcode/662. Maximum Width of Binary Tree.md

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,3 +107,46 @@ Note: Answer will in the range of 32-bit signed integer.
107107
}
108108
}
109109
```
110+
111+
###Amazon Session
112+
* Method 1:
113+
```Java
114+
/**
115+
* Definition for a binary tree node.
116+
* public class TreeNode {
117+
* int val;
118+
* TreeNode left;
119+
* TreeNode right;
120+
* TreeNode(int x) { val = x; }
121+
* }
122+
*/
123+
class Solution {
124+
private static final class Node{
125+
TreeNode node;
126+
int index;
127+
public Node(TreeNode node, int index){
128+
this.node = node;
129+
this.index = index;
130+
}
131+
}
132+
public int widthOfBinaryTree(TreeNode root) {
133+
if(root == null) return 0;
134+
Queue<Node> q = new LinkedList<>();
135+
q.offer(new Node(root, 1));
136+
int res = 1;
137+
while(!q.isEmpty()){
138+
int size = q.size();
139+
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
140+
for(int sz = 0; sz < size; sz++){
141+
Node n = q.poll();
142+
min = Math.min(min, n.index);
143+
max = Math.max(max, n.index);
144+
if(n.node.left != null) q.offer(new Node(n.node.left, (n.index << 1) - 1));
145+
if(n.node.right != null) q.offer(new Node(n.node.right, n.index << 1));
146+
}
147+
res = Math.max(res, max - min + 1);
148+
}
149+
return res;
150+
}
151+
}
152+
```

‎leetcode/997. Find the Town Judge.md

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
##997. Find the Town Judge
2+
3+
###Question
4+
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.
5+
6+
If the town judge exists, then:
7+
* The town judge trusts nobody.
8+
* Everybody (except for the town judge) trusts the town judge.
9+
* There is exactly one person that satisfies properties 1 and 2.
10+
11+
You are given trust, an array of pairs trust[i] =[a, b] representing that the person labelled a trusts the person labelled b.
12+
13+
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
14+
15+
```
16+
Example 1:
17+
18+
Input: N = 2, trust = [[1,2]]
19+
Output: 2
20+
21+
Example 2:
22+
23+
Input: N = 3, trust = [[1,3],[2,3]]
24+
Output: 3
25+
26+
Example 3:
27+
28+
Input: N = 3, trust = [[1,3],[2,3],[3,1]]
29+
Output: -1
30+
31+
Example 4:
32+
33+
Input: N = 3, trust = [[1,2],[2,3]]
34+
Output: -1
35+
36+
Example 5:
37+
38+
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
39+
Output: 3
40+
```
41+
42+
Note:
43+
44+
1. 1 <= N <= 1000
45+
2. trust.length <= 10000
46+
3. trust[i] are all different
47+
4. trust[i][0] != trust[i][1]
48+
5. 1 <= trust[i][0], trust[i][1] <= N
49+
50+
###Solution
51+
* Method 1: Indegree and outdegree of each vertex.
52+
```Java
53+
class Solution {
54+
public int findJudge(int N, int[][] trust) {
55+
int[] indegree = new int[N + 1];
56+
int[] outdegree = new int[N + 1];
57+
for(int[] t : trust){
58+
indegree[t[1]]++;
59+
outdegree[t[0]]++;
60+
}
61+
int res = -1;
62+
for(int i = 1; i <= N; i++){
63+
if(indegree[i] == N - 1 && outdegree[i] == 0){
64+
if(res != -1) return -1;
65+
else res = i;
66+
}
67+
}
68+
return res;
69+
}
70+
}
71+
```

0 commit comments

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