1. 有向图 找所有start node到end node之间的路径 输入是一个txt 形式如下： A E A : B C D. B : C C : E D : B. 输出一个List是从A到E所有的path
题不难，主要是注意STDIN
1 package pocketGems; 2 3 import java.io.*; 4 import java.util.ArrayList; 5 import java.util.List; 6 import java.util.HashMap; 7 import java.util.HashSet; 8 import java.util.Set; 9 10 public class PathFinder2 {11 public static void main(String[] args)12 throws FileNotFoundException, IOException {13 String filename = "C:/Users/yang liu/workspace/Interview2017/src/pocketGems/input_1.txt";14 if (args.length > 0) {15 filename = args[0];16 }17 18 19 List answer = parseFile(filename);20 System.out.println(answer); 21 }22 23 static List parseFile(String filename)24 throws FileNotFoundException, IOException {25 /*26 * Don't modify this function27 */28 BufferedReader input = new BufferedReader(new FileReader(filename));29 List allLines = new ArrayList ();30 String line;31 while ((line = input.readLine()) != null) {32 allLines.add(line);33 }34 input.close();35 36 37 return parseLines(allLines); 38 }39 40 static List parseLines(List allLines) {41 HashMap > graph = new HashMap >();42 Set visited = new HashSet ();43 String src = allLines.get(0).split(" ")[0];44 String dst = allLines.get(0).split(" ")[1];45 for (int i=1; i ());50 for (String nb : neibors) {51 if (nb.length() != 0) graph.get(node).add(nb);52 }53 }54 55 List res = new ArrayList ();56 visited.add(src);57 helper(res, src, src, dst, visited, graph);58 return res;59 }60 61 static void helper(List res, String path, String cur, String dst, Set visited, HashMap > graph) {62 if (cur.equals(dst)) {63 res.add(path);64 return;65 }66 HashSet neibors = graph.get(cur); 67 if (neibors != null) {68 for (String each : neibors) {69 if (visited.contains(each)) continue;70 visited.add(each);71 helper(res, path+each, each, dst, visited, graph);72 visited.remove(each);73 }74 }75 }76 }