Java面试的面试题目与解题思路

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面试的面试题目与解题思路 】相关文章：

银行的精华面试题目及思路点拨08-09

青岛啤酒的面试题目及回答思路07-31

求助面试的题目08-08

面试解题思维技巧--联想法07-31

英语面试经典题目和答案08-09

微软面试题目07-31

面试题目及答案07-31

关于电话面试的题目分享08-09

经典销售面试题目08-09

经典面试试题及答题思路分析08-03