題目如下：The number of different path from C to C with duration of less than 30. In the sample data, the paths are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7題目意思大致是求出 C to C 在 長度在不超過30范圍內共有過少條路徑？
2 回答
慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
題目沒有給出數據范圍，如果數據比較小的話，在每個點上掛一張表，表示從C到該點有哪些路徑長度可行，然后從C開始做一遍BFS即可，最后統計C點上表的大小即可。如果數據比較大可以考慮Tarjan縮環啥的……
波斯汪
TA貢獻1811條經驗 獲得超4個贊
private static class Pair{
char c;
int duration;
public Pair(char c, int duration) {
this.c = c;
this.duration = duration;
}
}
public int search(String[] input){
Map<Character, Set<Pair>> map = new HashMap<>();
for(String s: input){
char c1 = s.charAt(0), c2 = s.charAt(1);
int duration = s.charAt(2) - '0';
if(!map.containsKey(c1))
map.put(c1, new HashSet<>());
map.get(c1).add(new Pair(c2, duration));
}
int count = 0;
Queue<Pair> q = new LinkedList<Pair>();
q.offer(new Pair('C', 0));
while(!q.isEmpty()){
int size = q.size();
while(size-- > 0){
Pair cur = q.poll();
for(Pair p: map.get(cur.c)){
if(cur.duration + p.duration >= 30)
continue;
if(p.c == 'C')
count++;
q.offer(new Pair(p.c, cur.duration + p.duration));
}
}
}
return count;
}
@Test
public void test(){
assertEquals(7, search(new String[]{"AB5", "BC4", "CD8", "DC8", "DE6",
"AD5", "CE2", "EB3", "AE7"}));
}
添加回答
舉報
0/150
提交
取消