- 相關推薦
Java面試的面試題目與解題思路 2014
題目描述：
在A，B兩個城市之間設有N個路站(如下圖中的S1，且N<100)，城市與路站之間、路站和路站之間各有若干條路段(各路段數≤20，且每條路段上的距離均為一個整數)。
A，B的一條通路是指：從A出發，可經過任一路段到達S1，再從S1出發經過任一路段，…最后到達B。通路上路段距離之和稱為通路距離(最大距離≤1000)。當所有的路段距離給出之后，求出所有不同距離的通路個數(相同距離僅記一次)。
例如：下圖所示是當N=1時的情況：
從A到B的通路條數為6，但因其中通路5+5=4+6，所以滿足條件的不同距離的通路條數為5。
數據結構：
N記錄A，B間路站的個數
D[I][0]記錄第I-1到第I路站間路段的個數
D[I][1]，D[I][2]……記錄每個路段距離
G[X]標記長度為X的通路是否可能
B數組在窮舉過程中記錄當前路
B[I]表示第I-1到第I路站之間選擇哪一條路段
--------------------------------------------------------------------------------
算法提示：
本題采用窮舉算法，窮舉所有可能的路徑，求出它們的長度，并在一標記數組中標記該長度為可能，最后計算所有的可能標記個數。
窮舉時采用回溯法，最初從11……111這樣的路徑開始，每次都從最后一個路站開始往前尋找當前路徑可修改的地方，直到當前路徑變得無法修改為止。
【Java面試的面試題目與解題思路 】相關文章：
java面試的經驗11-20
java面試的測試11-20
廣西選調生面試備考：編故事題解題思路11-20
2014選調生面試備考 編故事題解題思路11-20
電話面試 題目11-20
面試經典考題回答思路11-07
海信面試英語題目06-15
JAVA面試筆試題11-15
小升初面試筆試及面試題目11-21