首页 > 9-8日 携程 开发岗第二题 代码详解
头像
刘先森202007272300471
编辑于 2020-09-09 19:29
+ 关注

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

九月八日的携程JAVA开发岗,真的太难了

当是只做出了AC 88%第一题,现在补充 第二题的代码。有错误的地方希望大家纠正,先看下题目
思想讲解:
这个题目其实主要考的是笛卡尔积,先使用笛卡尔积的算法,把所有的可能都得到,再去判断是否出现重复流程
有错误的地方请指正
别觉得代码多 ,重点代码只在 fun(), main方法里只是做了 输入 输出 ,判断是否为重复流
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();  //出栈栈顶元素
        }
    }
}



全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐