Commit b855035
authored
Merge pull request algorithm001#591 from rononz/master
week3 first commit2 files changed
Lines changed: 82 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,56 @@ | |||
| 1 | + /* | ||
| 2 | + // Definition for a Node. | ||
| 3 | + class Node { | ||
| 4 | + public int val; | ||
| 5 | + public List<Node> children; | ||
| 6 | + | ||
| 7 | + public Node() {} | ||
| 8 | + | ||
| 9 | + public Node(int _val,List<Node> _children) { | ||
| 10 | + val = _val; | ||
| 11 | + children = _children; | ||
| 12 | + } | ||
| 13 | + }; | ||
| 14 | + */ | ||
| 15 | + import java.util.Collections; | ||
| 16 | + import java.util.ArrayList; | ||
| 17 | + import java.util.LinkedList; | ||
| 18 | + | ||
| 19 | + class Solution { | ||
| 20 | + | ||
| 21 | + public List<List<Integer>> levelOrder(Node root) { | ||
| 22 | + if (root == null) { | ||
| 23 | + return Collections.emptyList(); | ||
| 24 | + } | ||
| 25 | + List<List<Integer>> retList = new ArrayList<>(); | ||
| 26 | + List<Integer> lineList = new LinkedList<>(); // all nodes at the same level | ||
| 27 | + Queue<Node> queue = new ArrayDeque<>(); | ||
| 28 | + queue.offer(root); | ||
| 29 | + int currLevelCount = 1; // node count on the current level | ||
| 30 | + int nextLevelCount = 0; // node count on the next level | ||
| 31 | + while (queue.peek() != null) { | ||
| 32 | + Node node = queue.poll(); | ||
| 33 | + currLevelCount--; | ||
| 34 | + lineList.add(node.val); | ||
| 35 | + List<Node> children = node.children; | ||
| 36 | + if (children != null && children.size() != 0) { | ||
| 37 | + int size = children.size(); | ||
| 38 | + // update the next level node count and push these nodes into queue | ||
| 39 | + nextLevelCount += size; | ||
| 40 | + for (Node child : children) { | ||
| 41 | + queue.offer(child); | ||
| 42 | + } | ||
| 43 | + } | ||
| 44 | + // If this is the last node of the current level | ||
| 45 | + if (currLevelCount == 0) { | ||
| 46 | + // add lineList into retList and re-init it | ||
| 47 | + retList.add(lineList); | ||
| 48 | + lineList = new LinkedList<>(); | ||
| 49 | + // now start visiting the next level | ||
| 50 | + currLevelCount = nextLevelCount; | ||
| 51 | + nextLevelCount = 0; | ||
| 52 | + } | ||
| 53 | + } | ||
| 54 | + return retList; | ||
| 55 | + } | ||
| 56 | + } | ||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,26 @@ | |||
| 1 | + class Solution { | ||
| 2 | + | ||
| 3 | + public int findJudge(int N, int[][] trust) { | ||
| 4 | + int[] trustArr = new int[N + 1]; // how many people this person trusts | ||
| 5 | + int[] trustedArr = new int[N + 1]; // how many people trust this person | ||
| 6 | + for (int[] pair : trust) { | ||
| 7 | + trustArr[pair[0]]++; | ||
| 8 | + trustedArr[pair[1]]++; | ||
| 9 | + } | ||
| 10 | + int judge = -1; | ||
| 11 | + for (int i = 1; i <= N; i++) { | ||
| 12 | + if (trustArr[i] == 0) { // not trust anyone, may be the judge | ||
| 13 | + if (judge == -1) { | ||
| 14 | + judge = i; // update judge | ||
| 15 | + } else { | ||
| 16 | + return -1; // got the second judge, return -1 | ||
| 17 | + } | ||
| 18 | + } | ||
| 19 | + } | ||
| 20 | + // the judge must be trusted by N-1 people. | ||
| 21 | + if (judge != -1 && trustedArr[judge] == N - 1) { | ||
| 22 | + return judge; | ||
| 23 | + } | ||
| 24 | + return -1; | ||
| 25 | + } | ||
| 26 | + } | ||
0 commit comments