企业官网建设流程全解析

东莞中小型网站建设,ps软件官方下载,淮安市建设工程安全监督站网站,免费网站建设翻译841. 钥匙和房间 问题描述 有 n 个房间#xff0c;编号从 0 到 n-1。每个房间都有一些钥匙#xff0c;可以打开其他房间。 给定一个数组 rooms#xff0c;其中 rooms[i] 是一个列表#xff0c;表示你进入房间 i 后可以拿到的所有钥匙#xff08;钥匙对应房间的编号#x…841. 钥匙和房间问题描述有n个房间编号从0到n-1。每个房间都有一些钥匙可以打开其他房间。给定一个数组rooms其中rooms[i]是一个列表表示你进入房间i后可以拿到的所有钥匙钥匙对应房间的编号。你从房间0开始初始时可以进入房间0。返回true如果你可以进入所有房间否则返回false。示例输入:rooms[[1],[2],[3],[]]输出:true解释:-从房间0开始拿到钥匙1-用钥匙1进入房间1拿到钥匙2-用钥匙2进入房间2拿到钥匙3-用钥匙3进入房间3-所有房间都已访问输入:rooms[[1,3],[3,0,1],[2],[0]]输出:false解释:-从房间0开始拿到钥匙1和3-可以进入房间1和3但无法进入房间2-房间2中有钥匙2但无法获得算法思路图的遍历DFS/BFS建模将房间看作图的节点钥匙看作有向边问题转化为从节点0出发能否访问所有节点遍历DFS深度优先搜索递归或栈实现BFS广度优先搜索队列实现代码实现方法一DFS递归importjava.util.*;classSolution{/** * 判断是否能进入所有房间 * 使用DFS递归遍历从房间0开始 * * param rooms 房间钥匙信息rooms[i]表示房间i中的钥匙列表 * return 如果能进入所有房间返回true否则返回false */publicbooleancanVisitAllRooms(ListListIntegerrooms){intnrooms.size();boolean[]visitednewboolean[n];// 记录房间访问状态// 从房间0开始DFSdfs(rooms,0,visited);// 检查是否所有房间都被访问for(booleanroomVisited:visited){if(!roomVisited){returnfalse;}}returntrue;}/** * 深度优先搜索遍历房间 * * param rooms 房间钥匙信息 * param room 当前房间编号 * param visited 访问状态数组 */privatevoiddfs(ListListIntegerrooms,introom,boolean[]visited){// 标记当前房间为已访问visited[room]true;// 遍历当前房间中的所有钥匙for(intkey:rooms.get(room)){// 如果对应的房间未访问过递归访问if(!visited[key]){dfs(rooms,key,visited);}}}}方法二DFS栈实现importjava.util.*;classSolution{/** * 使用栈实现DFS遍历 */publicbooleancanVisitAllRooms(ListListIntegerrooms){intnrooms.size();boolean[]visitednewboolean[n];StackIntegerstacknewStack();// 从房间0开始stack.push(0);visited[0]true;intvisitedCount1;// 已访问房间数while(!stack.isEmpty()){intcurrentRoomstack.pop();// 遍历当前房间的所有钥匙for(intkey:rooms.get(currentRoom)){if(!visited[key]){visited[key]true;stack.push(key);visitedCount;// 如果已经访问了所有房间提前结束if(visitedCountn){returntrue;}}}}returnvisitedCountn;}}方法三BFS队列实现importjava.util.*;classSolution{/** * 使用BFS队列实现遍历 */publicbooleancanVisitAllRooms(ListListIntegerrooms){intnrooms.size();boolean[]visitednewboolean[n];QueueIntegerqueuenewLinkedList();// 从房间0开始queue.offer(0);visited[0]true;intvisitedCount1;while(!queue.isEmpty()){intcurrentRoomqueue.poll();// 遍历当前房间的所有钥匙for(intkey:rooms.get(currentRoom)){if(!visited[key]){visited[key]true;queue.offer(key);visitedCount;// 提前结束if(visitedCountn){returntrue;}}}}returnvisitedCountn;}}方法四使用Set记录访问状态importjava.util.*;classSolution{/** * 使用Set记录已访问房间 */publicbooleancanVisitAllRooms(ListListIntegerrooms){SetIntegervisitednewHashSet();StackIntegerstacknewStack();stack.push(0);while(!stack.isEmpty()){introomstack.pop();visited.add(room);for(intkey:rooms.get(room)){if(!visited.contains(key)){stack.push(key);}}}returnvisited.size()rooms.size();}}算法分析时间复杂度O(N K)N 是房间数量K 是所有钥匙的总数图中边的数量每个房间和每把钥匙最多被访问一次空间复杂度O(N)visited数组O(N)递归栈/显式栈/队列最坏情况下 O(N)总体空间复杂度为 O(N)算法过程1rooms [[1],[2],[3],[]]DFS递归过程访问房间0visited [true, false, false, false]钥匙[1]递归访问房间1访问房间1visited [true, true, false, false]钥匙[2]递归访问房间2访问房间2visited [true, true, true, false]钥匙[3]递归访问房间3访问房间3visited [true, true, true, true]钥匙[]返回检查结果所有房间都已访问 →true2rooms [[1,3],[3,0,1],[2],[0]]DFS递归过程访问房间0visited [true, false, false, false]钥匙[1, 3]先递归访问房间1访问房间1visited [true, true, false, false]钥匙[3, 0, 1]房间3未访问递归访问房间3房间0和1已访问跳过访问房间3visited [true, true, false, true]钥匙[0]房间0已访问跳过返回到房间1再返回到房间0回到房间0处理钥匙3已访问结束检查结果visited [true, true, false, true]房间2未访问 →false测试用例importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1可以访问所有房间ListListIntegerrooms1Arrays.asList(Arrays.asList(1),Arrays.asList(2),Arrays.asList(3),Arrays.asList());System.out.println(Test 1: solution.canVisitAllRooms(rooms1));// true// 测试用例2无法访问所有房间ListListIntegerrooms2Arrays.asList(Arrays.asList(1,3),Arrays.asList(3,0,1),Arrays.asList(2),Arrays.asList(0));System.out.println(Test 2: solution.canVisitAllRooms(rooms2));// false// 测试用例3只有一个房间ListListIntegerrooms3Arrays.asList(Arrays.asList());System.out.println(Test 3: solution.canVisitAllRooms(rooms3));// true// 测试用例4两个房间互相有钥匙ListListIntegerrooms4Arrays.asList(Arrays.asList(1),Arrays.asList(0));System.out.println(Test 4: solution.canVisitAllRooms(rooms4));// true// 测试用例5两个房间单向有钥匙ListListIntegerrooms5Arrays.asList(Arrays.asList(1),Arrays.asList());System.out.println(Test 5: solution.canVisitAllRooms(rooms5));// true// 测试用例6两个房间没有钥匙ListListIntegerrooms6Arrays.asList(Arrays.asList(),Arrays.asList());System.out.println(Test 6: solution.canVisitAllRooms(rooms6));// false// 测试用例7复杂情况ListListIntegerrooms7Arrays.asList(Arrays.asList(1,2,3),Arrays.asList(2,3),Arrays.asList(3),Arrays.asList());System.out.println(Test 7: solution.canVisitAllRooms(rooms7));// true// 测试用例8环形结构ListListIntegerrooms8Arrays.asList(Arrays.asList(1),Arrays.asList(2),Arrays.asList(0));System.out.println(Test 8: solution.canVisitAllRooms(rooms8));// true// 测试用例9多个分支ListListIntegerrooms9Arrays.asList(Arrays.asList(1,2),Arrays.asList(3),Arrays.asList(4),Arrays.asList(),Arrays.asList());System.out.println(Test 9: solution.canVisitAllRooms(rooms9));// true}}关键点图遍历房间是节点钥匙是有向边问题等价于判断从节点0出发是否能到达所有节点起始条件保证可以从房间0开始不需要钥匙这是连通性判断的起点访问标记避免重复访问和无限循环环形结构如房间0→1→2→0需要正确处理常见问题为什么不需要考虑钥匙的使用顺序能否访问所有房间而不是访问的顺序。只要存在一条路径能到达某个房间就认为可以访问。DFS和BFS有什么区别在这个问题中两种方法的结果完全相同。DFS可能会更快到达某些房间BFS按层次访问最终的可达性判断是一样的。