We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Java
  3. Advanced
  4. Java Visitor Pattern
  5. Discussions

Java Visitor Pattern

Sort by

recency

|

186 Discussions

|

  • KCarot
     + 0 comments

    I reviewed some comments, and find more efficient data structure to solve whever use recursive or non recursive way. Recursive:

    static int[] values;
    static Color[] colors;
    static Map<Integer, Set<Integer>> nodeMap = new HashMap<>();
    public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        values = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        colors = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .mapToObj(c -> c == 0 ? Color.RED : Color.GREEN).toArray(Color[]::new);

        for (int i = 0; i < n - 1; ++i) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;

            Set<Integer> linkedNodes = nodeMap.get(u);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(v);
            nodeMap.put(u, linkedNodes);

            linkedNodes = nodeMap.get(v);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(u);
            nodeMap.put(v, linkedNodes);
        }

        Tree root = new TreeNode(values[0], colors[0], 0);
        buildTree(root, 0);

        sc.close();
        return root;
    }

    private static void buildTree(Tree parentNode, int u) {
        Set<Integer> uLinkedNodes = nodeMap.get(u);
        uLinkedNodes.forEach(v -> {
            Set<Integer> vLinkedNodes = nodeMap.get(v);
            vLinkedNodes.remove(u);
            Tree childNode = null;
            if (vLinkedNodes.isEmpty()) {
                childNode = new TreeLeaf(values[v], colors[v], parentNode.getDepth() + 1);
            } else {
                childNode = new TreeNode(values[v], colors[v], parentNode.getDepth() + 1);
            }
            ((TreeNode) parentNode).addChild(childNode);
            buildTree(childNode, v);
        });
    }

    Non recutsive:

        static Color[] colors;
    static Map<Integer, Set<Integer>> nodeMap = new HashMap<>();
    static Tree[] tree;
    public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        values = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        colors = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .mapToObj(c -> c == 0 ? Color.RED : Color.GREEN).toArray(Color[]::new);
        tree = new Tree[n];
        
        for (int i = 0; i < n - 1; ++i) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            
            Set<Integer> linkedNodes = nodeMap.get(u);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(v);
            nodeMap.put(u, linkedNodes);
            
            linkedNodes = nodeMap.get(v);
            if (linkedNodes == null) {
                linkedNodes = new HashSet<>();
            }
            linkedNodes.add(u);
            nodeMap.put(v, linkedNodes);
        }
        
        tree[0] = new TreeNode(values[0], colors[0], 0);
        
        Set<Integer> levelSet = new HashSet<>();
        levelSet.add(0);
        Set<Integer> nextLevelSet = new HashSet<>();
        while (!levelSet.isEmpty()) {
            for (int u : levelSet) {
                Set<Integer> uLinkedNodes = nodeMap.get(u);
                uLinkedNodes.forEach(v -> {
                    Set<Integer> vLinkedNodes = nodeMap.get(v);
                    vLinkedNodes.remove(u);
                    if (vLinkedNodes.isEmpty()) {
                        tree[v] = new TreeLeaf(values[v], colors[v], tree[u].getDepth() + 1);
                    } else {
                        tree[v] = new TreeNode(values[v], colors[v], tree[u].getDepth() + 1);
                    }
                    ((TreeNode) tree[u]).addChild(tree[v]);
                    nextLevelSet.add(v);
                });
            }
            levelSet.clear();
            levelSet.addAll(nextLevelSet);
            nextLevelSet.clear();
        }

        sc.close();
        return tree[0];
    }

  • KCarot
     + 0 comments

    I have to say that before you submit, you probably won't know that the edge is not pointing from the parent node to the descendant node, and you won't know that the order in which nodes appear is not top-down...

    It seems that several exercises have encountered similar problems in my memory, which has lowered the impression of this website in my mind。

    In the end, it took a lot of time to improve and perfect, and a non recursive tree building process was implemented.Only posted the process of building the tree, by the way, it uses Java8.

    public static Tree solve() {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        int[] values = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        Color[] colors = Arrays.stream(sc.nextLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .mapToObj(c -> c == 0 ? Color.RED : Color.GREEN).toArray(Color[]::new);

        int[] edgeCount = new int[n];
        Arrays.fill(edgeCount, 0);
        edgeCount[0] = 1;
        int[] edges = new int[(n - 1) * 2];
        int x, y;
        for (int i = 0; i < edges.length - 1; i += 2) {
            x = sc.nextInt() - 1;
            y = sc.nextInt() - 1;
            edges[i] = x;
            edges[i + 1] = y;

            ++edgeCount[x];
            ++edgeCount[y];
        }

        Tree[] tree = new Tree[n];
        tree[0] = new TreeNode(values[0], colors[0], 0);

        Set<Integer> levelSet = new HashSet<>();
        Set<Integer> tmpSet = new HashSet<>();
        levelSet.add(0);
        while (!levelSet.isEmpty()) {
            for (int i = 0; i < edges.length - 1; i += 2) {
                x = edges[i];
                y = edges[i + 1];
                if (x == -1 || y == -1) {
                    continue;
                }
                if (levelSet.contains(x)) {
                    if (edgeCount[y] > 1) {
                        tree[y] = new TreeNode(values[y], colors[y], tree[x].getDepth() + 1);
                    } else if (edgeCount[y] == 1) {
                        tree[y] = new TreeLeaf(values[y], colors[y], tree[x].getDepth() + 1);
                    } else {
                        throw new RuntimeException("edgeCount error");
                    }
                    ((TreeNode) tree[x]).addChild(tree[y]);
                    tmpSet.add(y);
                    edges[i] = -1;
                    edges[i + 1] = -1;
                } else if (levelSet.contains(y)) {
                    if (edgeCount[x] > 1) {
                        tree[x] = new TreeNode(values[x], colors[x], tree[y].getDepth() + 1);
                    } else if (edgeCount[x] == 1) {
                        tree[x] = new TreeLeaf(values[x], colors[x], tree[y].getDepth() + 1);
                    } else {
                        throw new RuntimeException("edgeCount error");
                    }
                    ((TreeNode) tree[y]).addChild(tree[x]);
                    tmpSet.add(x);
                    edges[i] = -1;
                    edges[i + 1] = -1;
                }
            }
            levelSet.clear();
            levelSet.addAll(tmpSet);
            tmpSet.clear();
        }

        sc.close();
        return tree[0];
    }

  • pw_hackerrank
     + 0 comments

    The problem description is tricky and easily misleading. Specifically it says:

    ...Each of the subsequent lines contains two space-separated integers, *ui* and *vi* , describing an edge between nodes *u* and *v*.

    An edge input like this:

    3 4

    does not mean that 3 is the parent. The parent may as well be noted on the right side. The correct interpretation:

    There is just a link between 3 and 4, it's unspecified which one is tree node/leaf node.

  • paburnwal123
     + 0 comments

    Can anyone tell me what do we have to do in this module

  • nashruddinshaik
     + 1 comment

    This code works fine for me

    import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.util.Iterator;

    enum Color { RED, GREEN }

    abstract class Tree { private int value; private Color color; private int depth;

    public Tree(int value, Color color, int depth) {
    this.value = value;
    this.color = color;
    this.depth = depth;
}

public int getValue() {
    return value;
}

public Color getColor() {
    return color;
}

public int getDepth() {
    return depth;
}

public abstract void accept(TreeVis visitor);

    }

    class TreeNode extends Tree { private ArrayList children = new ArrayList<>();

    public TreeNode(int value, Color color, int depth) {
    super(value, color, depth);
}

public void accept(TreeVis visitor) {
    visitor.visitNode(this);
    for (Tree child : children) {
        child.accept(visitor);
    }
}

public void addChild(Tree child) {
    children.add(child);
}

    }

    class TreeLeaf extends Tree { public TreeLeaf(int value, Color color, int depth) { super(value, color, depth); }

    public void accept(TreeVis visitor) {
    visitor.visitLeaf(this);
}

    }

    abstract class TreeVis { public abstract int getResult(); public abstract void visitNode(TreeNode node); public abstract void visitLeaf(TreeLeaf leaf); }

    class SumInLeavesVisitor extends TreeVis { private int sumInLeaves = 0;

    public int getResult() {
    return sumInLeaves;
}

public void visitNode(TreeNode node) {
    // Do nothing for nodes
}

public void visitLeaf(TreeLeaf leaf) {
    sumInLeaves += leaf.getValue();
}

    }

    class ProductOfRedNodesVisitor extends TreeVis { private long productOfRedNodes = 1L; private static final int MOD = 1000000007;

    public int getResult() {
    return (int) productOfRedNodes;
}

private void multiply(Tree tree) {
    if (tree.getColor() == Color.RED) {
        productOfRedNodes = (productOfRedNodes * tree.getValue()) % MOD;
    }
}

public void visitNode(TreeNode node) {
    multiply(node);
}

public void visitLeaf(TreeLeaf leaf) {
    multiply(leaf);
}

    }

    class FancyVisitor extends TreeVis { private int sumOfValuesNonLeafEvenDepth = 0; private int sumOfValuesGreenLeaf = 0;

    public int getResult() {
    return Math.abs(sumOfValuesNonLeafEvenDepth - sumOfValuesGreenLeaf);
}

public void visitNode(TreeNode node) {
    if (node.getDepth() % 2 == 0) {
        sumOfValuesNonLeafEvenDepth += node.getValue();
    }
}

public void visitLeaf(TreeLeaf leaf) {
    if (leaf.getColor() == Color.GREEN) {
        sumOfValuesGreenLeaf += leaf.getValue();
    }
}

    }

    public class Solution { static Map tree = new HashMap<>();

    public static Tree solve() {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Map<Integer, Object[]> nodeAtts = new HashMap<>();

    // Read node values
    for (int i = 0; i < n; i++) {
        nodeAtts.put(i + 1, new Object[]{sc.nextInt(), null});
    }

    // Read node colors
    for (int i = 0; i < n; i++) {
        nodeAtts.get(i + 1)[1] = sc.nextInt() == 0 ? Color.RED : Color.GREEN;
    }

    // Read edges
    Map<Integer, ArrayList<Integer>> edges = new HashMap<>();
    for (int i = 1; i <= n; i++) {
        edges.put(i, new ArrayList<>());
    }

    for (int i = 1; i < n; i++) {
        int u = sc.nextInt();
        int v = sc.nextInt();
        edges.get(u).add(v);
        edges.get(v).add(u);
    }

    // Create root node
    Tree root = new TreeNode((Integer) nodeAtts.get(1)[0], (Color) nodeAtts.get(1)[1], 0);
    tree.put(1, root);

    // Perform DFS to build tree
    DFS(n, edges, nodeAtts);
    return tree.get(1);
}

private static void DFS(int n, Map<Integer, ArrayList<Integer>> edges, Map<Integer, Object[]> nodeAtts) {
    boolean[] visited = new boolean[n + 1];
    TreeNode parent = (TreeNode) tree.get(1);
    DFSUtil(parent, 1, visited, edges, nodeAtts);
}

private static void DFSUtil(TreeNode parent, int v, boolean[] visited, Map<Integer, ArrayList<Integer>> edges, Map<Integer, Object[]> nodeAtts) {
    visited[v] = true;

    if (v != 1 && edges.get(v).size() == 1) {
        TreeLeaf treeLeaf = new TreeLeaf((Integer) nodeAtts.get(v)[0], (Color) nodeAtts.get(v)[1], parent.getDepth() + 1);
        parent.addChild(treeLeaf);
        tree.put(v, treeLeaf);
        return;
    }

    TreeNode treeNode = (v != 1) ? new TreeNode((Integer) nodeAtts.get(v)[0], (Color) nodeAtts.get(v)[1], parent.getDepth() + 1) : (TreeNode) tree.get(1);

    if (v != 1) {
        parent.addChild(treeNode);
        tree.put(v, treeNode);
    }

    for (int n : edges.get(v)) {
        if (!visited[n]) {
            DFSUtil(treeNode, n, visited, edges, nodeAtts);
        }
    }
}

public static void main(String[] args) {
    Tree root = solve();
    SumInLeavesVisitor vis1 = new SumInLeavesVisitor();
    ProductOfRedNodesVisitor vis2 = new ProductOfRedNodesVisitor();
    FancyVisitor vis3 = new FancyVisitor();

    root.accept(vis1);
    root.accept(vis2);
    root.accept(vis3);

    System.out.println(vis1.getResult());
    System.out.println(vis2.getResult());
    System.out.println(vis3.getResult());
}

    }