专业网站建设市场/你就知道

题目一：迷宫中离⼊⼝最近的出⼝

1. 题⽬链接：

https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/

2. 题⽬描述：

给你⼀个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格⼦（⽤ ‘.’ 表⽰）和墙（⽤ ‘+’ 表
⽰）。同时给你迷宫的⼊⼝ entrance ，⽤ entrance = [entrancerow, entrancecol] 表⽰你⼀开始所在格⼦的⾏和列。 每⼀步操作，你可以往 上，下，左 或者 右 移动⼀个格⼦。你不能进⼊墙所在的格⼦，你也不能离开 迷宫。你的⽬标是找到离 entrance 最近 的出⼝。出⼝ 的含义是 maze 边界 上的 空格⼦。 entrance 格⼦ 不算 出⼝。 请你返回从 entrance 到最近出⼝的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

3.算法思路：

利⽤层序遍历来解决迷宫问题，是最经典的做法。 我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的
时候，得到起点到出⼝的最短距离。

4.代码

class Solution 
{int[] dx = {0, 0, -1, 1};int[] dy = {1, -1, 0, 0};public int nearestExit(char[][] maze, int[] e) {int m = maze.length, n = maze[0].length;boolean[][] vis = new boolean[m][n];Queue<int[]> q = new LinkedList<>();q.add(new int[]{e[0], e[1]});vis[e[0]][e[1]] = true;int step = 0;while(!q.isEmpty()){step++;int sz = q.size();for(int i = 0; i < sz; i++){int[] t = q.poll();int a = t[0], b = t[1];for(int j = 0; j < 4; j++){int x = a + dx[j], y = b + dy[j];if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' 
&& !vis[x][y]){// 判断是否已经到出⼝ if(x == 0 || x == m - 1 || y == 0 || y == n - 1) returnstep;vis[x][y] = true;q.add(new int[]{x, y});}}}}return -1;}
}

题目二. 最⼩基因变化

1. 题⽬链接：

https://leetcode.cn/problems/minimum-genetic-mutation/description/

2. 题⽬描述：

基因序列可以表⽰为⼀条由 8 个字符组成的字符串，其中每个字符都是 ‘A’ 、 ‘C’ 、 ‘G’ 和 ‘T’ 之⼀。
假设我们需要调查从基因序列 start 变为 end 所发⽣的基因变化。⼀次基因变化就意味着这个 基因序列中的⼀个字符发⽣了变化。

• 例如， “AACCGGTT” --> “AACCGGTA” 就是⼀次基因变化。 另有⼀个基因库 bank
记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中） 给你两个基因序列 start
和 end ，以及⼀个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果⽆法完成此基因变化，返回
-1 。 注意：起始基因序列 start 默认是有效的，但是它并不⼀定会出现在基因库中。

3.算法思路：

如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为 1 的最短路问题」。
因此，从起始的字符串开始，来⼀次 bfs 即可。
每一次转换相当于经过一层，有这么多的情况：可以转换任意一个位置，每个位置可以转换为’A’ 、 ‘C’ 、 ‘G’ 和’T’ 之⼀的任意字符。

4.代码

class Solution 
{public int minMutation(String startGene, String endGene, String[] bank) {Set<String> vis = new HashSet<>(); // ⽤来标记已经搜索过的状态 Set<String> hash = new HashSet<>(); // ⽤来统计基因库⾥⾯的字符串 for(String s : bank) hash.add(s);char[] change = {'A', 'C', 'G', 'T'};if(startGene.equals(endGene)) return 0;if(!hash.contains(endGene)) return -1;Queue<String> q = new LinkedList<>();q.add(startGene);vis.add(startGene);int step = 0;while(!q.isEmpty()){step++;int sz = q.size();while(sz-- != 0){String t = q.poll();for(int i = 0; i < 8; i++){char[] tmp = t.toCharArray();for(int j = 0; j < 4; j++){tmp[i] = change[j];String next = new String(tmp);if(hash.contains(next) && !vis.contains(next)){if(next.equals(endGene)) return step;q.add(next);vis.add(next);}}}}}return -1;}}

题目三：单词接⻰

1. 题⽬链接：

https://leetcode.cn/problems/word-ladder/description/

2. 题⽬描述：

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是⼀个按下述规格形成的序 列 beginWord
-> s(1) -> s(2) -> … -> s(k) ：

• 每⼀对相邻的单词只差⼀个字⺟。

• 对于 1 <= i <= k 时，每个 s(i) 都在 wordList 中。注意， beginWord 不需要 在 wordList 中。

• s(k) == endWord 给你两个单词 beginWord 和 endWord 和⼀个字典 wordList ，返回 从beginWord 到 endWord 的 最短转换序列 中的 单词数⽬ 。如果不存在这样的转换序列，返回 0

3.算法思路：

和上一题一样，如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为 1 的最短路问题」。
因此，从起始的字符串开始，要经过多少层才能转变为目标字符来⼀次 bfs 即可。
每一次转换相当于经过一层，有这么多的情况：可以转换任意一个位置，每个位置可以转换位为’a’到’z’的任意字符。

4.代码

class Solution 
{public int ladderLength(String beginWord, String endWord, List<String> 
wordList) {Set<String> hash = new HashSet<>();for(String s : wordList) hash.add(s);Set<String> vis = new HashSet<>(); // 标记已经搜索过的单词 if(!hash.contains(endWord)) return 0;Queue<String> q = new LinkedList<>();q.add(beginWord);vis.add(beginWord);int ret = 1;while(!q.isEmpty()){ret++;int sz = q.size();while(sz-- != 0){String t = q.poll();for(int i = 0; i < t.length(); i++){char[] tmp = t.toCharArray();for(char ch = 'a'; ch <= 'z'; ch++){tmp[i] = ch;String next = new String(tmp);if(hash.contains(next) && !vis.contains(next)){if(next.equals(endWord)) return ret;q.add(next);vis.add(next);}}}}}return 0;}}