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

进修社 人气:1.35W

题目描述:

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这样的路径开始,每次都从最后一个路站开始往前寻找当前路径可修改的地方,直到当前路径变得无法修改为止。