java算法

Question

题目如下：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范围内共有过少条路径？

Answer 1

题目没有给出数据范围，如果数据比较小的话，在每个点上挂一张表，表示从C到该点有哪些路径长度可行，然后从C开始做一遍BFS即可，最后统计C点上表的大小即可。如果数据比较大可以考虑Tarjan缩环啥的……

Answer 2

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"}));

}