9-8日 携程 开发岗第二题 代码详解

import java.util.*;

public class demo2 {
    static StringBuilder res = new StringBuilder();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String str = scanner.nextLine(); //输入
            String strs[] = str.split(" ");  //根据空格截取每一段
            List<List<String>> lists = new ArrayList<>();
            for (int i = 0; i < strs.length; i++) {
                lists.add(Arrays.asList(strs[i].split("")));
            }
            Stack<String> stack = new Stack<>();
            List<List<String>> result = new ArrayList<>();
            fun(lists,0,stack,result);
//  假设数据为 [[a,b,c],[d,c,f]]  ,那么sets[0] 所存储的就是 a,b,c，  sets[1] 所存储的就是 a,b,c,d,f
//            作用是为了判断流程中是否包含重复流程
//                采用这种结构是为了降低复杂度，如果在两层循环中再嵌套一个 for循环去判断是否有重复流，那时间复杂度一下子就上去了。但是借助了set之后，就可以把第三层循环干掉
            ArrayList<HashSet<String>> sets = new ArrayList<>();
            HashSet<String> set = new HashSet<>();
            for (int i = 0; i < lists.size(); i++) {
                for (int j = 0; j < lists.get(i).size(); j++) {
                    set.add(lists.get(i).get(j));
                }
                sets.add(new HashSet<>(set));
            }
            Boolean flag = false; //判断是否出现重复
            for (int i = 0; i < result.size(); i++) {
                flag = false;
                for (int j = 0; j < result.get(i).size(); j++) {
                    String s=  result.get(i).get(j);
                    if(j!=0&&sets.get(j-1).contains(s)){ //判断是否出现重复
                        flag = true;
                    }
                    System.out.print(s);
                }
                if (flag){
                    System.out.print("--重复流程");
                }
                System.out.println();
            }
        }
    }

    /**
     *
     * @param originLists   原始的一个二维数组
     * @param index    遍历二维数组的一位数组的位置   [[a,b,c],[d,e,f]]   index == 0 表示 [a,b,c]
     * @param stack    用于存储每次得到的结果 ，[a,d] 就是其中一个，
     *                 先将a入栈，d再入栈，然后d出栈，e入栈，e出栈，f入栈，f出栈，
     *                 此时，def都遍历完了，那么此时就应该是a出栈，b入栈 ，重复上面的操作
     * @param result  存储得到的结果集
     * @param <T>     泛型
     */
    public static <T> void fun(List<List<T>> originLists,int index,Stack<T> stack,List<List<T>> result){
        List<T> list = originLists.get(index);  //获得原始数组中的其中一个数组元素
        for (int i = 0; i < list.size(); i++) { //遍历list中的每个元素
            stack.push(list.get(i));   //遍历得到的元素压入栈中
            if(index == originLists.size()-1){//表明已经到达了原始数组的最后一个元素，也表明了，当前stack为其中一个子集
                List<T> res = new ArrayList<>(stack);  //生成新的数组，存入结果集中
                result.add(res);  //将结果存入result集合中
                stack.pop();  //出栈栈顶元素
                continue;
            }
            fun(originLists,index+1,stack,result); //递归调用
            stack.pop();  //出栈栈顶元素
        }
    }
}