BoomBleBee: Probleme grafuri & arbori (1)

19 iulie 2024

Probleme grafuri & arbori (1)

#1. Aflare daca exista o cale intre doua noduri dintr-un graf

Graf neorientat cu n noduri pentru care se da o lista de muchii edges[i] = [n1, n2] care inseamna ca exista o legatura directa intre n1 si n2. Sa se afle daca din n1 se poate ajunge in n2.

Nota: BFS. Nu este necesar sa folosim Map, un simplu ArrayList e suficient.

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if (source == destination) {
            return true;
        }

        Map<Integer, Node> nodes = new HashMap<>();
        for (int i=0; i<n; i++) {
            nodes.put(i, new Node(i));
        }

        for (int i=0; i<edges.length; i++) {
            int from = edges[i][0], to = edges[i][1];
            nodes.get(from).addNeighbor(nodes.get(to));
            nodes.get(to).addNeighbor(nodes.get(from));
        }

        Node startNode = nodes.get(source);
        if (startNode.isLinkedTo(nodes.get(destination))) {
            return true;
        }
        startNode.setVisited();

        Queue<Node> queue = new LinkedList<>();
        queue.addAll(startNode.neighbors);
        
        while(!queue.isEmpty()) {
            Node next = queue.remove();
            if (!next.visited) {
                next.setVisited();
                if (next.isLinkedTo(nodes.get(destination))) {
                    return true;
                }
                queue.addAll(next.neighbors);
            }
        }

        return false;
    }

    private class Node {
        int value;
        List<Node> neighbors;
        boolean visited = false;

        public Node (int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }

        public void addNeighbor(Node node) {
            this.neighbors.add(node);
        }

        public boolean isLinkedTo(Node node) {
            return this.neighbors.contains(node);
        }

        public void setVisited() {
            this.visited = true;
        }
    }
}

#2. Transformarea unui array sortat intr-un BST (binary search tree)

Sirul este sortat crescator. In arborele creat, toti descendentii din stanga ai unui nod <= valoarea nodului, iar descendentii din dreapta > valoarea nodului. In plus, arborele trebuie sa fie aiba inaltimea minima posibila.

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return transform(nums, 0, nums.length - 1);
    }

    TreeNode transform(int[] nums, int indexFrom, int indexTo) {
        if (indexFrom == indexTo) {
            return new TreeNode(nums[indexFrom]);
        }
        
        if (indexFrom == indexTo - 1) {
            TreeNode root = new TreeNode(nums[indexTo]);
            root.left = new TreeNode(nums[indexFrom]);
            return root;
        }

        int size = indexTo - indexFrom + 1;
        TreeNode root = new TreeNode(nums[indexFrom + size/2]);
        root.left = transform(nums, indexFrom, indexFrom + size/2 - 1);
        root.right = transform(nums, indexFrom + size/2 + 1, indexTo);
        return root;
    }
}

#3. Arbore binar echilibrat

Dandu-se un arbore binar, sa se afle daca este echilibrat, adica pt fiecare nod diferenta intre inaltimile in jos ale fiecarui subarbore sa nu fie mai mare decat 1.

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        try {
            findHeightUnderNode(root);
        } catch (UnbalancedTreeException e) {
            return false;
        }
        return true;
    }

    private int findHeightUnderNode(TreeNode node) throws UnbalancedTreeException {
        if (node.left == null && node.right == null) {
            return 1;
        }
        int heightUnderLeft = node.left == null ? 0 : findHeightUnderNode(node.left);
        int heightUnderRight = node.right == null ? 0 : findHeightUnderNode(node.right);
        if (Math.abs(heightUnderLeft - heightUnderRight) > 1) {
            throw new UnbalancedTreeException();
        }
        return 1 + Math.max(heightUnderLeft, heightUnderRight);
    }

    private class UnbalancedTreeException extends RuntimeException {
        public UnbalancedTreeException() {
            super();
        }
    }
}

#4. Validarea unui BST

Se da un arbore binar. Sa se verifice daca este un arbore binar de cautare (BST).

class Solution {
    public boolean isValidBST(TreeNode root) {
        try {
            checkValid(root, null, null);
        } catch(InvalidBSTException e) {
            return false;
        }
        return true;
    }

    private void checkValid(TreeNode node, Integer lessThan, Integer moreThan) {
        // lessThan, moreThan - constrangeri propagate de sus in jos
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }
        
        if (node.left != null) {
            if (node.left.val >= node.val || (lessThan != null && node.left.val >= lessThan) || 
                    (moreThan != null && node.left.val <= moreThan)) {
                throw new InvalidBSTException();
            }
        }
        if (node.right != null) {
            if (node.right.val <= node.val || (lessThan != null && node.right.val >= lessThan) || 
                    (moreThan != null && node.right.val <= moreThan)) {
                throw new InvalidBSTException();
            }
        }

        checkValid(node.left, min(node.val, lessThan), moreThan);
        checkValid(node.right, lessThan, max(node.val, moreThan));
    }

    private int min(Integer x, Integer y) {
        if (x != null && y != null) {
            return Math.min(x,y);
        }
        return x != null ? x : y;
    }

    private int max(Integer x, Integer y) {
        if (x != null && y != null) {
            return Math.max(x,y);
        }
        return x != null ? x : y;
    }

    private class InvalidBSTException extends RuntimeException {
        public InvalidBSTException() {
            super();
        }
    }
}

Niciun comentariu:

Trimiteți un comentariu