尋夢新聞LINE@每日推播熱門推薦文章,趣聞不漏接❤️
前言
這篇文章承接了之前的文章,都是關於面試的內容。作者是我的一個學弟,目前是大三,所以他的文章偏重於實習/校招。因此有相關經歷的小夥伴如果想認識他,可以後台私信我。
這是他的其他一些文章:
面試被問到Spring IOC、AOP和動態代理,用這篇文章懟過去
正文
題目要求:
現在我們擁有全國的省、市、縣、鎮的行政信息,比如 浙江省 -> 杭州市 -> 西湖區 –> xx街道,請將這些信息構建成一棵樹,根節點為全國,葉子節點為鎮。
我的誤解:
剛開始我並沒有明白題意,走了彎路,只是簡單的構建了一個多叉樹。代碼如下:
import java.util.ArrayList; import java.util.List; public class SiteTree { public final static String COUNTRY = "國"; public final static String PROVINCE = "省"; public final static String CITY = "市"; private static class Node { private String level; //國》省》市》縣》鎮 private String name; //例如:山東省、濟南市等具體地名 private List<Node> child; //下一級節點列表 private Node(String level, String name) { this.level = level; this.name = name; } //Getter Setter } public static void main(String[] args) { //聲明一個根節點 Node GUO = new Node(SiteTree.COUNTRY, "中國"); //山東省下的市級單位 Node JINAN = new Node(SiteTree.CITY, "濟南市"); Node JINING = new Node(SiteTree.CITY, "濟寧市"); //將市級節點放入山東省級節點下 Node QLU = new Node(SiteTree.PROVINCE, "山東省"); SiteTree.add(QLU, JINAN, JINING); //將省級節點放入國級節點下 Node ZJS = new Node(SiteTree.PROVINCE, "浙江省"); SiteTree.add(GUO, QLU, ZJS); //不再舉例... System.out.println(GUO); } public static void add(Node parent, Node... child) { List<Node> childs = new ArrayList<>(); for (int i = 0; i < child.length; i++) { childs.add(child[i]); } parent.setChild(childs); } }
當面試官看到代碼後,提示我:你需要做到一個通用的方法。我沒太明白,面試官又說:主要考察你對遞歸的使用。
看到這里,我忽然明白了面試官的意圖:使用遞歸去構建N叉樹。
擺在我面前的一個問題是,我該如何去讀取數據源,數據源儲存的形式是什麼?是文本文件還是數據庫?
文本文件說實話,不太好做到,而且不規範,正常邏輯數據應該儲存在數據庫。
但是我現在總不能去裝個數據庫吧?再寫DAO層查詢接口?這不現實。
沒辦法,只能自己簡單模擬下數據庫操作了!
表結構都是一行一行的數據,那就用List。每行數據(節點)不能只有主鍵,還要有父節點的外鍵,因為題目要求也給出了數據是具有指向關係的 。
如何做到數據的查詢呢?當然是用Stream,最簡單。
分析到這里,完整的代碼已經呼之欲出,請看大螢幕 ↘
import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; public class SiteTree { public final static String COUNTRY = "國"; public final static String PROVINCE = "省"; public final static String CITY = "市"; private static List<Node> list = initData(); //結合數據庫比較好做到,所以簡單做到下! private static class Node{ private int cid; //節點ID private int pid; //父節點ID private String level; //國》省》市》縣》鎮 private String name; //例如:山東省、濟南市等具體地名 private List<Node> child = new ArrayList<>(); //下一級節點列表 public Node(int cid, int pid, String level, String name) { this.cid = cid; this.pid = pid; this.level = level; this.name = name; } public int getCid() { return cid; } public int getPid() { return pid; } public String getName() { return name; } public List<Node> getChild() { return child; } @Override public String toString() { return "Node{" + "cid=" + cid + ", pid=" + pid + ", level='" + level + '\'' + ", name='" + name + '\'' + ", child=" + child + '}'; } } /** * 初始化數據庫 * @return */ private static List<Node> initData() { //聲明一個根節點 Node GUO = new Node(1,0,SiteTree.COUNTRY,"中國"); //將市級節點放入山東省級節點下 Node QLU = new Node(4,1,SiteTree.PROVINCE, "山東省"); //將省級節點放入國級節點下 Node ZJS = new Node(5,1,SiteTree.PROVINCE,"浙江省"); //山東省下的市級單位 Node JINAN = new Node(2,4,SiteTree.CITY,"濟南市"); Node JINING = new Node(3,4,SiteTree.CITY,"濟寧市"); //簡單數據庫做到 List<Node> list = new ArrayList<>(); list.add(GUO); list.add(JINAN); list.add(JINING); list.add(QLU); list.add(ZJS); return list; } public static void main(String[] args){ System.out.println(child(1)); } private static Node child(int cid) { //獲取節點 Node node = getTreeNode(cid); //獲取子節點 List<Node> childNodes = getChildNode(cid); //遍歷子節點 for (Node child : childNodes){ Node n = child(child.getCid());//遞歸 node.getChild().add(n); } return node; } private static Node getTreeNode(int cid) { return list.stream().filter(node -> { if (node.getCid() == cid) { return true; } return false; }).findFirst().get(); } private static List<Node> getChildNode(int pid) { return list.stream().filter(node -> { if (node.getPid() == pid) { return true; } return false; }).collect(Collectors.toList()); } }
列印輸出:
Node{cid=1, pid=0, level='國', name='中國', child=[ Node{cid=4, pid=1, level='省', name='山東省', child=[ Node{cid=2, pid=4, level='市', name='濟南市', child=[]}, Node{cid=3, pid=4, level='市', name='濟寧市', child=[]}]}, Node{cid=5, pid=1, level='省', name='浙江省', child=[]}]}
這是我的解答,如果你有更好的解答,歡迎評論分享!