脸家实习一轮

oio14644 发表于 2016-12-7 09:08
请问lz, input 是ArrayList nodes 吗?

我是c++的，不过是他让你自己定义一下graph然后我也自己定义了一个graphnode

1. public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
   
2.         if (node == null) return null;
   
3.         Queue<UndirectedGraphNode> queue = new LinkedList<>();
   
4.         Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
   
5.         UndirectedGraphNode newRoot = new UndirectedGraphNode(node.label);
   
6.         queue.offer(node);
   
7.         map.put(node, newRoot);
   
8.         
   
9.         while (!queue.isEmpty()) {
   
10.             UndirectedGraphNode cur = queue.poll();
    
11.             for (UndirectedGraphNode neighbor : cur.neighbors) {
    
12.                 if (!map.containsKey(neighbor)) {
    
13.                     map.put(neighbor, new UndirectedGraphNode(neighbor.label));
    
14.                     queue.offer(neighbor);
    
15.                 }
    
16.                 map.get(cur).neighbors.add(map.get(neighbor));
    
17.             }
    
18.         }
    
19.         
    
20.         return newRoot;
    
21.     }

复制代码

可以这么写？

shijia8888 发表于 2016-12-13 03:43
可以这么写？

呃你这个还是只是copy了connect的图，不过我的做法其实就是用这个method走一遍图里的所有点就好了~

zty920317 发表于 2016-12-13 07:27
呃你这个还是只是copy了connect的图，不过我的做法其实就是用这个method走一遍图里的所有点就好了~

请问lz node点集给出来了么，否则怎么找出不相连的点的呀。谢谢，祝好！^_^

kiru 发表于 2016-12-13 20:28
请问lz node点集给出来了么，否则怎么找出不相连的点的呀。谢谢，祝好！^_^

对所以自己还要写一个Graph类包括了所有点的集合

用preorder＋min_vale 替换null？ －》
public static List<TreeNode> serialzeTree(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    public static void helper(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            TreeNode node = new TreeNode(Integer.MIN_VALUE);
            list.add(node);
            return;
        }
        TreeNode node = new TreeNode(root.val);
        list.add(node);
        helper(root.left, list);
        helper(root.right, list);
    }
    static int idx = 0;
    public static TreeNode deserilize(List<TreeNode> list) {
        if (list.get(idx).val == Integer.MIN_VALUE) {
            idx++;
            return null;
        }
        TreeNode node = new TreeNode(list.get(idx).val);
        idx++;
        node.left = deserilize(list);
        node.right = deserilize(list);
        return node;
    }

zty920317 发表于 2016-12-13 07:27
呃你这个还是只是copy了connect的图，不过我的做法其实就是用这个method走一遍图里的所有点就好了~

input可以是List<Node>吗？然后对于每个listNode，如果访问过了，就continue，要不然就调用上面的function。这是undirect graph吧