九月八日的携程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) 回帖