JAVA面试算法题

标题：服务循环依赖检测
描述信息
在微服务的架构下，公司内部会有非常多的独立服务。
服务之间可以相互调用，往往大型应用调用链条很长，如果出现循环依赖将出现非常恶劣的影响。
对于一个具体应用，已知各个服务的调用关系（即依赖关系），请判断是否存在循环调用。
输入：
一组服务依赖关系list，('A', 'B') 表示 A 会调用 B 服务
service_relations = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('D', 'A')]
输出：
由于存在 A - B - D - A 故存在循环依赖，返回True；反之如果不存在，返回False
Follow up：

1. 如果有多个环，请都检测出来
2. 返回每个环中的服务名

我的思路：
初始输入的service_relations看作一个字符串碎片的集合。
我们用这些碎片尝试互相拼接，把拼接好的字符串放入一个新的字符串集合（allStr）中，并从中选出构成环的字符串，存放在结果集合（result）中。
初始的字符串集合（allStr）就等于字符串碎片集合，一旦拼接成功产生新的字符串，就把新字符串加入到allStr中，然后尝试继续拼接。

需要注意的地方是：从allStr中取出一个新的字符串时，要先判断这个字符串是否已经构成了环，或者局部构成了环，如果有，则不再尝试找碎片去拼接这个字符串。

public class CircleTest3 {

    public static String testCircle(List<StringBuilder> charsList) {//输入的字符串碎片集合
        //所有拼接好的字符串集合，初始时等于输入的字符串碎片集合
        List<StringBuilder> allStr = new ArrayList<>(charsList);
        StringBuilder result = new StringBuilder();
        int len = charsList.size();
        boolean circleExist = false;
        for(int i=0;i<allStr.size();i++){
            StringBuilder temp = allStr.get(i);

            if(temp.charAt(temp.length()-1)==temp.charAt(0)){//如果首尾相同，则构成环，不再继续拼接
                result.append(",");
                result.append(temp);
                continue;
            }

            for(int k=0;k<temp.length();k=k+2){//说明有内部环，不再继续拼接
                if(temp.charAt(k)==temp.charAt(temp.length()-1)){
                    circleExist = true;
                }
            }
            if(circleExist){
                continue;
            }
            //从字符串碎片集合中取碎片，尝试拼接
            for(int j=0;j<len;j++){
                StringBuilder chars = charsList.get(j);
                if(chars.charAt(0)==temp.charAt(temp.length()-1)){//头尾相连，可以拼接
                    StringBuilder newStr = new StringBuilder(temp);
                    newStr.append(chars);
                    allStr.add(newStr);
                }
            }
        }

        //输出result
        if(result.length()==0){
            return result.toString();
        }else{
            return result.deleteCharAt(0).toString();
        }
    }

    public static void main(String[] args) {
        List<StringBuilder> list = new ArrayList<>();

        list.add(new StringBuilder("ac"));
//        list.add(new StringBuilder("cb"));
//        list.add(new StringBuilder("bd"));
//        list.add(new StringBuilder("ba"));
//        list.add(new StringBuilder("vr"));

        list.add(new StringBuilder("cf"));
        list.add(new StringBuilder("fd"));
        list.add(new StringBuilder("fa"));
        list.add(new StringBuilder("vr"));
        list.add(new StringBuilder("df"));


        System.out.println(testCircle(list));
    }
}