Commit95bb6cc

committed

[Function add]

1. Add leetcode solutions.

1 parentfdb0087 commit95bb6ccCopy full SHA for 95bb6cc

File tree

+131

-0

lines changed

+131

-0

lines changed

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -195,4 +195,46 @@ class Solution {`
`195`	`195`	`return remain.isEmpty() ? order: new int[0];`
`196`	`196`	`}`
`197`	`197`	`}`
	`198`	+```
	`199`	`+`
	`200`	`+###Amazon Session`
	`201`	`+* Method 1: Topological sort`
	`202`	+```Java
	`203`	`+class Solution {`
	`204`	`+public int[] findOrder(int numCourses, int[][] prerequisites) {`
	`205`	`+Map<Integer, List<Integer>> map = new HashMap<>();`
	`206`	`+int[] indegree = new int[numCourses];`
	`207`	`+for(int[] req : prerequisites){`
	`208`	`+indegree[req[0]]++;`
	`209`	`+List<Integer> list = map.getOrDefault(req[1], new ArrayList<>());`
	`210`	`+list.add(req[0]);`
	`211`	`+map.put(req[1], list);`
	`212`	`+}`
	`213`	`+Queue<Integer> q = new LinkedList<>();`
	`214`	`+for(int i = 0; i < numCourses; i++){`
	`215`	`+if(indegree[i] == 0){`
	`216`	`+q.offer(i);`
	`217`	`+}`
	`218`	`+}`
	`219`	`+List<Integer> result = new ArrayList<>();`
	`220`	`+while(!q.isEmpty()){`
	`221`	`+int cur = q.poll();`
	`222`	`+result.add(cur);`
	`223`	`+if(!map.containsKey(cur)) continue;`
	`224`	`+List<Integer> neighbours = map.get(cur);`
	`225`	`+for(Integer n : neighbours){`
	`226`	`+if(--indegree[n] == 0){`
	`227`	`+q.offer(n);`
	`228`	`+}`
	`229`	`+}`
	`230`	`+}`
	`231`	`+if(result.size() != numCourses) return new int[0];`
	`232`	`+int[] res = new int[numCourses];`
	`233`	`+int index = 0;`
	`234`	`+while(index < numCourses){`
	`235`	`+res[index] = result.get(index++);`
	`236`	`+}`
	`237`	`+return res;`
	`238`	`+}`
	`239`	`+}`
`198`	`240`	```

Lines changed: 47 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -67,3 +67,50 @@ Some examples:`
`67`	`67`	`}`
`68`	`68`	`}`
`69`	`69`	```
	`70`	`+`
	`71`	`+###Amazon session`
	`72`	`+* Method 1: recursion + stack`
	`73`	+```Java
	`74`	`+class Solution {`
	`75`	`+private char[] arr;`
	`76`	`+private int i;`
	`77`	`+public int calculate(String s) {`
	`78`	`+this.arr = s.toCharArray();`
	`79`	`+return parse();`
	`80`	`+}`
	`81`	`+private int parse(){`
	`82`	`+char oper = '+';`
	`83`	`+int sum = 0;`
	`84`	`+Stack<Integer> stack = new Stack<>();`
	`85`	`+while(i < arr.length){`
	`86`	`+char c = arr[i];`
	`87`	`+if(c == '('){`
	`88`	`+i++;`
	`89`	`+addToStack(stack, oper, parse());`
	`90`	`+}else if(Character.isDigit(c)){`
	`91`	`+int cur = c - '0';`
	`92`	`+i++;`
	`93`	`+while(i < arr.length && Character.isDigit(arr[i])){`
	`94`	`+cur = cur * 10 + arr[i++] - '0';`
	`95`	`+}`
	`96`	`+addToStack(stack, oper, cur);`
	`97`	`+}else if(c == ')'){`
	`98`	`+while(!stack.isEmpty()) sum += stack.pop();`
	`99`	`+i++;`
	`100`	`+return sum;`
	`101`	`+}else if(c == '+' \|\| c == '-' \|\| c == '*' \|\| c == '/'){`
	`102`	`+oper = c;`
	`103`	`+i++;`
	`104`	`+}else if(c == ' ') i++;`
	`105`	`+}`
	`106`	`+while(!stack.isEmpty()) sum += stack.pop();`
	`107`	`+return sum;`
	`108`	`+}`
	`109`	`+private void addToStack(Stack<Integer> stack, char c, int num){`
	`110`	`+if(c == '+') stack.push(num);`
	`111`	`+else if(c == '-') stack.push(-num);`
	`112`	`+else if(c == '') stack.push(stack.pop() num);`
	`113`	`+else stack.push(stack.pop() / num);`
	`114`	`+}`
	`115`	`+}`
	`116`	+```

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -75,3 +75,45 @@ Note:`
`75`	`75`	`}`
`76`	`76`	`}`
`77`	`77`	```
	`78`	`+`
	`79`	`+###AmazonSession`
	`80`	`+*Method1: bfs`
	`81`	+```Java
	`82`	`+/**`
	`83`	`+ * Definition for a binary tree node.`
	`84`	`+ * public class TreeNode {`
	`85`	`+ * int val;`
	`86`	`+ * TreeNode left;`
	`87`	`+ * TreeNode right;`
	`88`	`+ * TreeNode(int x) { val = x; }`
	`89`	`+ * }`
	`90`	`+*/`
	`91`	`+classSolution {`
	`92`	`+publicbooleanisCousins(TreeNoderoot,intx,inty) {`
	`93`	`+Queue<TreeNode> q=newLinkedList<>();`
	`94`	`+if(root.val== x\|\| root.val== y)returnfalse;`
	`95`	`+q.offer(root);`
	`96`	`+while(!q.isEmpty()){`
	`97`	`+Set<Integer> value=newHashSet<>();`
	`98`	`+int size= q.size();`
	`99`	`+for(int i=0; i< size; i++){`
	`100`	`+TreeNode node= q.poll();`
	`101`	`+if(node.left!=null&& node.right!=null){`
	`102`	`+if((node.left.val== x&& node.right.val== y)`
	`103`	`+\|\| (node.left.val== y&& node.right.val== x))returnfalse;`
	`104`	`+}`
	`105`	`+if(node.left!=null){`
	`106`	`+q.offer(node.left);`
	`107`	`+value.add(node.left.val);`
	`108`	`+}`
	`109`	`+if(node.right!=null){`
	`110`	`+q.offer(node.right);`
	`111`	`+value.add(node.right.val);`
	`112`	`+}`
	`113`	`+}`
	`114`	`+if(value.contains(x)&& value.contains(y))returntrue;`
	`115`	`+}`
	`116`	`+returnfalse;`
	`117`	`+}`
	`118`	`+}`
	`119`	+```

Comments

(0)