#5. Aranjarea unor cursuri cu relatie de dependenta intre ele
Se da un numCourses si o lista de dependinte prereq[i] = [a, b], cu semnificatia: pentru a putea participa la cursul a, un student trebuie sa participe intai la cursul b. Sa se gaseasca o aranjare posibila a cursurilor, cu satisfacerea tuturor relatiilor de dependenta.
Nota: sortare topologica intr-un graf orientat. Se pun intr-o stiva si se elimina succesiv nodurile care nu au arce de iesire, impreuna cu arcele lor de intrare. Se repeta pana cand nu mai ramane niciun nod, apoi se scot nodurile din stiva; ele vor fi sortate topologic. Daca exista un ciclu in graf, nu exista sortare topologica - se va observa ca de la o iteratie la alta nu se mai sterg noduri.
class Solution {
public int[] findOrder(int numCourses, int[][] prereq) {
Map<Integer, Set<Integer>> outgoingEdges = new HashMap<>();
for (int i=0; i<numCourses; i++) {
outgoingEdges.put(i, new HashSet<>());
}
for (int[] edges : prereq) {
int to = edges[0], from = edges[1];
outgoingEdges.get(from).add(to);
}
int result[] = new int[numCourses];
try {
Stack<Integer> stack = topologicalSort(numCourses, outgoingEdges);
int i = 0;
while (!stack.isEmpty()) {
result[i++] = stack.pop();
}
} catch (CircularException e) {
return new int[0];
}
return result;
}
private Stack<Integer> topologicalSort(int numCourses, Map<Integer, Set<Integer>> outgoingEdges) {
Stack<Integer> nodeStack = new Stack<>();
int remainingNodes = outgoingEdges.size();
while (!outgoingEdges.isEmpty()) {
List<Integer> connectionsToDelete = new LinkedList<>();
for (int i=0; i<numCourses; i++) {
if (outgoingEdges.containsKey(i) && outgoingEdges.get(i).isEmpty()) {
nodeStack.push(i);
outgoingEdges.remove(i);
connectionsToDelete.add(i);
}
}
outgoingEdges.forEach((k,v) -> v.removeAll(connectionsToDelete));
connectionsToDelete.clear();
// este un ciclu atunci cand dupa o parcurgere completa nu se mai scot noduri
if (remainingNodes == outgoingEdges.size()) {
throw new CircularException();
}
remainingNodes = outgoingEdges.size();
}
return nodeStack;
}
private class CircularException extends RuntimeException {
public CircularException() {
super();
}
}
}
Varianta mai eficienta: sortare topologica folosind DSF. Dupa obtinerea unei ordini topologice, trebuie sa se verifice ca graful nu contine cicluri.
class Solution {
public int[] findOrder(int numCourses, int[][] prereq) {
List<List<Integer>> adjList = getAdjList(numCourses, prereq);
boolean visited[] = new boolean[numCourses]; // all false
Stack<Integer> stack = new Stack<>();
int result[] = new int[numCourses];
for (int i=0; i<numCourses; i++) {
if (!visited[i]) {
dfs(i, adjList, stack, visited);
}
}
int i = 0;
while (!stack.isEmpty()) {
result[i++] = stack.pop();
}
// check for any cycle
for (int node = 0; node < numCourses; node++) {
for (int conn : adjList.get(node)) {
// we have a vertex from node -> conn
// if conn appears before node in the ordering => cycle
if (indexOf(conn, result) < indexOf(node, result)) {
return new int[0]; // cycle
}
}
}
return result;
}
private void dfs(int node, List<List<Integer>> adjList, Stack<Integer> stack, boolean visited[]) {
visited[node] = true;
for (int neighbor : adjList.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, adjList, stack, visited);
}
}
stack.push(node);
}
private List<List<Integer>> getAdjList(int numCourses, int[][] prereq) {
List<List<Integer>> adjList = new ArrayList<>();
for (int i=0; i<numCourses; i++) {
adjList.add(new ArrayList<>());
}
for (int[] edges : prereq) {
int to = edges[0], from = edges[1];
adjList.get(from).add(to);
}
return adjList;
}
private int indexOf(int node, int[] order) {
for (int i=0; i<order.length; i++) {
if (order[i] == node) {
return i;
}
}
return -1;
}
}
#6. Primul stramos comun a doua noduri dintr-un arbore binar
Cand avem acces la parintii unui nod:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p == root || q == root) {
return root;
}
int diffDepth = depth(root, p) - depth(root, q);
while (diffDepth > 0) {
p = p.parent; // bring p on the same level with q
diffDepth--;
}
while (diffDepth < 0) {
q = q.parent; // bring q on the same level with p
diffDepth++;
}
while (p != q && p != null && q != null) {
// go up together
p = q.parent;
p = q.parent;
}
return (p != null && q != null) ? p : null;
}
private int depth(TreeNode root, TreeNode node) {
int depth = 0;
while (node != root) {
depth++;
node = node.parent;
}
return depth;
}
}
Cand nu avem acces la parintii unui nod:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p == root || q == root || root == null) {
return root;
}
return search(root, p, q);
}
private TreeNode search(TreeNode node, TreeNode p, TreeNode q) {
if (node == p || node == q) {
return node;
}
boolean isPinLeft = isNodeInSubtree(node.left, p);
boolean isQinLeft = isNodeInSubtree(node.left, q);
if (isPinLeft != isQinLeft) { // if p and q are in different branches of node
return node; // common ancestor
} else {
TreeNode nodeNext = isPinLeft ? node.left : node.right;
return search(nodeNext, p, q);
}
}
private boolean isNodeInSubtree(TreeNode subtree, TreeNode node) {
if (subtree == null) {
return false;
}
if (subtree.val == node.val) {
return true;
}
return isNodeInSubtree(subtree.left, node) || isNodeInSubtree(subtree.right, node);
}
// issue: repetitive calls to isNodeInSubtree when it already found the node
}
Alternativa - fara acces la parinti, tinem minte calea pana la nod in format L/R
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p == root || q == root || root == null) {
return root;
}
search(root, p, "", q, "");
TreeNode ancestor = root;
int i = 0;
while (finalPathP.length() > i && finalPathQ.length() > i && finalPathP.charAt(i) == finalPathQ.charAt(i)) {
char c = finalPathP.charAt(i);
ancestor = c == 'L' ? ancestor.left : ancestor.right;
i++;
}
return ancestor;
}
String finalPathP = null;
String finalPathQ = null;
private void search(TreeNode node, TreeNode p, String pathP, TreeNode q, String pathQ) {
if (node == null) {
return;
}
if (node.val == p.val) {
finalPathP = pathP;
}
if (node.val == q.val) {
finalPathQ = pathQ;
}
if (finalPathP == null || finalPathQ == null) {
search(node.left, p, pathP + "L", q, pathQ + "L");
search(node.right, p, pathP + "R", q, pathQ + "R");
}
}
}
