Commit438c7f1

committed

[Function add]

1. Add leetcode solutions with tag amazon.

1 parentec1f261 commit438c7f1Copy full SHA for 438c7f1

File tree

+126

-1

lines changed

+126

-1

lines changed

Lines changed: 43 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -104,4 +104,46 @@ public class Solution {`
`104`	`104`	`}`
`105`	`105`	`}`
`106`	`106`	`}`
`107`		-```
	`107`	+```
	`108`	`+`
	`109`	`+###Amazon Session`
	`110`	`+* Method 1: BFS`
	`111`	+```Java
	`112`	`+/*`
	`113`	`+// Definition for a Node.`
	`114`	`+class Node {`
	`115`	`+public int val;`
	`116`	`+public Node left;`
	`117`	`+public Node right;`
	`118`	`+public Node next;`
	`119`	`+`
	`120`	`+public Node() {}`
	`121`	`+`
	`122`	`+public Node(int _val,Node _left,Node _right,Node _next) {`
	`123`	`+val = _val;`
	`124`	`+left = _left;`
	`125`	`+right = _right;`
	`126`	`+next = _next;`
	`127`	`+}`
	`128`	`+};`
	`129`	`+*/`
	`130`	`+class Solution {`
	`131`	`+public Node connect(Node root) {`
	`132`	`+if(root == null) return root;`
	`133`	`+Queue<Node> q = new LinkedList<>();`
	`134`	`+q.offer(root);`
	`135`	`+while(!q.isEmpty()){`
	`136`	`+Queue<Node> next = new LinkedList<>();`
	`137`	`+int size = q.size();`
	`138`	`+for(int sz = 0; sz < size; sz++){`
	`139`	`+Node cur = q.poll();`
	`140`	`+cur.next = q.isEmpty() ? null: q.peek();`
	`141`	`+if(cur.left != null) next.offer(cur.left);`
	`142`	`+if(cur.right != null) next.offer(cur.right);`
	`143`	`+}`
	`144`	`+q = next;`
	`145`	`+}`
	`146`	`+return root;`
	`147`	`+}`
	`148`	`+}`
	`149`	+```

Lines changed: 18 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -57,3 +57,21 @@ public class MeetingRooms {`
`57`	`57`	`}`
`58`	`58`	`}`
`59`	`59`	```
	`60`	`+`
	`61`	`+###Amazon Session`
	`62`	`+* Method 1: Sort and judge`
	`63`	+```Java
	`64`	`+class Solution {`
	`65`	`+public boolean canAttendMeetings(int[][] intervals) {`
	`66`	`+if(intervals == null) return false;`
	`67`	`+if(intervals.length == 0) return true;`
	`68`	`+Arrays.sort(intervals, (a, b)->{`
	`69`	`+return a[0] == b[0] ? a[1] - b[1]: a[0] - b[0];`
	`70`	`+});`
	`71`	`+for(int i = 1; i < intervals.length; i++){`
	`72`	`+if(intervals[i][0] < intervals[i - 1][1]) return false;`
	`73`	`+}`
	`74`	`+return true;`
	`75`	`+}`
	`76`	`+}`
	`77`	+```

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -64,3 +64,35 @@ Follow up:`
`64`	`64`	`}`
`65`	`65`	`}`
`66`	`66`	```
	`67`	`+`
	`68`	`+###Amazon Session`
	`69`	`+* Method 1: Map + PriorityQueue`
	`70`	+```Java
	`71`	`+class Solution {`
	`72`	`+private static class Node{`
	`73`	`+String word;`
	`74`	`+int count;`
	`75`	`+public Node(String word, int count){`
	`76`	`+this.word = word;`
	`77`	`+this.count = count;`
	`78`	`+}`
	`79`	`+}`
	`80`	`+public List<String> topKFrequent(String[] words, int k) {`
	`81`	`+List<String> result = new ArrayList<>();`
	`82`	`+Map<String, Integer> map = new HashMap<>();`
	`83`	`+for(String word: words){`
	`84`	`+map.put(word, map.getOrDefault(word, 0) + 1);`
	`85`	`+}`
	`86`	`+PriorityQueue<Node> pq = new PriorityQueue<>((a, b)->{`
	`87`	`+return a.count != b.count ? b.count - a.count: a.word.compareTo(b.word);`
	`88`	`+});`
	`89`	`+for(Map.Entry<String, Integer> entry: map.entrySet()){`
	`90`	`+pq.offer(new Node(entry.getKey(), entry.getValue()));`
	`91`	`+}`
	`92`	`+while(k-- > 0){`
	`93`	`+result.add(pq.poll().word);`
	`94`	`+}`
	`95`	`+return result;`
	`96`	`+}`
	`97`	`+}`
	`98`	+```

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -62,5 +62,38 @@ Note:`
`62`	`62`	`}`
`63`	`63`	```
`64`	`64`
	`65`	`+###Amazon Session`
	`66`	`+* Method 1: bfs + bit manipulation`
	`67`	+```Java
	`68`	`+class Solution {`
	`69`	`+public int shortestPathLength(int[][] graph) {`
	`70`	`+int len = graph.length;`
	`71`	`+boolean[][] visited = new boolean[len][1 << len];`
	`72`	`+int expect = (1 << len) - 1;`
	`73`	`+Queue<int[]> q = new LinkedList<>();`
	`74`	`+for(int i = 0; i < len; i++){`
	`75`	`+q.offer(new int[]{i, 1 << i});`
	`76`	`+}`
	`77`	`+int step = -1;`
	`78`	`+while(!q.isEmpty()){`
	`79`	`+step++;`
	`80`	`+int size = q.size();`
	`81`	`+for(int sz = 0; sz < size; sz++){`
	`82`	`+int[] cur = q.poll();`
	`83`	`+int node = cur[0];`
	`84`	`+int state = cur[1];`
	`85`	`+if(state == expect) return step;`
	`86`	`+if(visited[node][state]) continue;`
	`87`	`+visited[node][state] = true;`
	`88`	`+for(int next: graph[node]){`
	`89`	`+q.offer(new int[]{next, state \| (1 <<next)});`
	`90`	`+}`
	`91`	`+}`
	`92`	`+}`
	`93`	`+return step;`
	`94`	`+}`
	`95`	`+}`
	`96`	+```
	`97`	`+`
`65`	`98`	`###Reference`
`66`	`99`	`1.[花花酱 LeetCode 847. Shortest Path Visiting All Nodes](http://zxi.mytechroad.com/blog/graph/leetcode-847-shortest-path-visiting-all-nodes/)`

Comments

(0)