Algorithm: Leetcode Contest 410

3248. Snake in Matrix

Solution

class Solution {
    public int finalPositionOfSnake(int n, List<String> commands) {
        int i = 0, j = 0;
        
        for (String command: commands) {
            if(command.equals("UP")) {
                i--;
            } else if(command.equals("DOWN")) {
                i++;
            } else if(command.equals("LEFT")) {
                j--;
            } else if(command.equals("RIGHT")) {
                j++;
            }
        }
        
        return i * n + j;
    }
}

3249. Count the Number of Good Nodes

Solution

class Solution {
    public int countGoodNodes(int[][] edges) {
        // build tree
        Map<Integer, Node> map = new HashMap<>();
        Node root = new Node(0);
        map.put(0, root);
        
        for(int[] edge: edges) {
            if (!map.containsKey(edge[0])) {
                map.put(edge[0], new Node(edge[0]));
            }
            
            if (!map.containsKey(edge[1])) {
                map.put(edge[1], new Node(edge[1]));
            }
            Node parent = map.get(edge[0]);
            Node child = map.get(edge[1]);

            parent.children.add(child);
            child.children.add(parent);
        }
            
        // iterate on tree, calcuate each tree's good & size
        Set<Node> seen = new HashSet<>();
        seen.add(root);
        Info res = iterate(root, seen);
        return res.goodChildren;
    }
    
    private Info iterate(Node root, Set<Node> seen) {
        seen.add(root);
        List<Info> children = new ArrayList<>();
        for(Node child: root.children) {
            if (!seen.contains(child)) {
                children.add(iterate(child, seen));
            }
        }

        if (children.size() == 0) {
            return new Info(1, 1);
        }
        
        int size = children.get(0).size;
        int totalSize = 1;
        int goodChildren = 0;
        boolean isGood = true;
        for(Info child: children) {
            if (child.size != size) {
                isGood = false;
            }
            totalSize += child.size;
            goodChildren += child.goodChildren;
        }
        
        if (isGood) {
            goodChildren++;
        }
        
        return new Info(totalSize, goodChildren);
    }
    
    private class Info {
        int size = 0;
        int goodChildren = 0;
        public Info(int i, int c) {
            size = i;
            goodChildren = c;
        }
    }
    
    private class Node {
        int label;
        List<Node> children;
        
        public Node(int i) {
            label = i;
            children = new ArrayList<>();
        }
    }
}

Retro

1. This challenge can be divided into 3 sub problems: construct tree, DFS, check good node.
2. How to construct a undirected tree – make undirected edge and set to ensure the iterate is single directional