Description: Given a undirected graph, a node and a target, return the nearest node to given node which value of it is target, return NULL if you can’t find.
There is a mapping store the nodes’ values in the given parameters.
Notice
It’s guaranteed there is only one available solution
Have you met this question in a real interview? Yes Example 2——3 5 / | | / | | / | | / | | 1 –4 Give a node 1, target is 50
there a hash named values which is [3,4,10,50,50], rePResent: Value of node 1 is 3 Value of node 2 is 4 Value of node 3 is 10 Value of node 4 is 50 Value of node 5 is 50
Return node 4
題目不難，直接食用正常的思路求解就可以
/** * Definition for graph node. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { * label = x; neighbors = new ArrayList<UndirectedGraphNode>(); * } * }; */public class Solution { /** * @params graph a list of Undirected graph node * @param values a hash mapping, <UndirectedGraphNode, (int)value> * @param node an Undirected graph node * @param target an integer * @return the a node */ public UndirectedGraphNode searchNode(ArrayList<UndirectedGraphNode> graph, Map<UndirectedGraphNode, Integer> values, UndirectedGraphNode node, int target) { // Write your code here if (node == null) { return null; } Queue<UndirectedGraphNode> queue = new LinkedList<>(); Set<UndirectedGraphNode> set =new HashSet<>(); queue.offer(node); set.add(node); while (!queue.isEmpty()) { UndirectedGraphNode gnode = queue.poll(); if (values.get(gnode) == target) { return gnode; } for (UndirectedGraphNode root : gnode.neighbors) { if (set.contains(root)) { continue; } queue.offer(root); set.add(root); } } return null; }}新聞熱點
疑難解答
