目录
1. 迷宫中离入口最近的出口
1.1 算法原理
1.2 算法代码
2. 最小基因变化 ★★★
2.1 算法原理
2.2 算法代码
3. 单词接龙
3.1 算法原理
3.2 算法代码
4. 为高尔夫比赛砍树 (hard)
4.1 算法原理
4.2 算法代码
1. 迷宫中离入口最近的出口
. - 力扣（LeetCode）
1.1 算法原理
核心问题: 图论 => 边权为1/边权相同 的最短路径问题
解法: 从起点开始, 进行 BFS 扩展, 第一次到达终点时, 扩展的层数, 就是最短的路径.
如何记录 BFS 扩展的层数呢??
--- 借助每一层中节点的数量(queue.size()), 使用变量 ret 记录扩展的层数.
1.2 算法代码
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int[] dx = { 1, -1, 0, 0 };
int[] dy = { 0, 0, 1, -1 };
// 记录到达终点时, BFS 的层数
int ret = 0;
int m = maze.length, n = maze[0].length;
boolean[][] check = new boolean[m][n];
Queue<int[]> q = new LinkedList<>();
q.offer(entrance);
check[entrance[0]][entrance[1]] = true;
while (!q.isEmpty()) {
int size = q.size();
ret++;
while (size-- != 0) {
int[] tmp = q.poll();
int a = tmp[0], b = tmp[1];
for (int k = 0; k < 4; k++) {
int x = a + dx[k], y = b + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && maze[x][y] == '.') {
if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return ret;
q.offer(new int[] { x, y });
check[x][y] = true;
}
}
}
}
return -1;
}
}2. 最小基因变化 ★★★
. - 力扣（LeetCode）
2.1 算法原理
问题转化: 转化为 => 图论 边权为1的最短路问题
- 每变一个字符(基因的变化)看做一步, BFS 选出达到目标基因序列时的最短路.
- 注意: 不能重复搜索已经搜索过的状态
- 注意: 经过变化的字符串, 应该在 bank 基因库中存在
- 使用 哈希表 标记已经搜索过的状态
- 使用 哈希表 保存基因库中的字符(便于查找变化的字符串是否在基因库中)
2.2 算法代码
class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
Queue<String> q = new LinkedList<>();
// 判断是否重复转化
Set<String> check = new HashSet<>();
// 判断基因库中是否存在
Set<String> hash = new HashSet<>();
for(String s : bank) hash.add(s);
if(!hash.contains(endGene)) return -1;
if(startGene.equals(endGene)) return 0;
char[] change = {'A', 'C', 'G', 'T'};
int ret = 0;
q.offer(startGene);
check.add(startGene);
while(!q.isEmpty()) {
int size = q.size();
ret++;
while(size-- != 0) {
String s = q.poll();
for(int i = 0; i < 8; i++) {
char[] tmp = s.toCharArray();
for(int j = 0; j < 4; j++) {
tmp[i] = change[j];
String next = new String(tmp);
if(hash.contains(next) && !check.contains(next)) {
if(next.equals(endGene)) return ret;
check.add(next);
q.offer(next);
}
}
}
}
}
return -1;
}
}3. 单词接龙
. - 力扣（LeetCode）
3.1 算法原理
-
本题解法与上题解法完全一致.
-
只不过返回值略有差异. 本题返回达到目标字符串时, 所涉及到的最少的字符串的个数(最短路 +1)
3.2 算法代码
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// 把字典中的字符串, 放到哈希表中 => 查找效率 O(1)
Set<String> hash = new HashSet<>(wordList);
if(!hash.contains(endWord)) return 0;
int n = beginWord.length();
// 判断是否重复转化
Set<String> check = new HashSet<>();
Queue<String> q = new LinkedList<>();
int step = 0;
q.offer(beginWord);
check.add(beginWord);
while(!q.isEmpty()) {
int size = q.size();
step++;
while(size-- != 0) {
String s = q.poll();
for(int i = 0; i < n; i++) {
char[] tmp = s.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++) {
tmp[i] = ch;
String next = new String(tmp);
if(hash.contains(next) && !check.contains(next)) {
if(next.equals(endWord)) return step + 1;
q.offer(next);
check.add(next);
}
}
}
}
}
return 0;
}
}4. 为高尔夫比赛砍树 (hard)
. - 力扣（LeetCode）
4.1 算法原理
-
对砍树的顺序做好记录(所砍树的高度应从小到大), 并记录好每一颗树的位置.
-
从起点开始, 对这些位置依次进行 BFS, 找出到达这些位置的最短路.
-
返回到达所有位置所需最少步数之和
4.2 算法代码
class Solution {
int m, n;
int[] dx = new int[] { 1, -1, 0, 0 };
int[] dy = new int[] { 0, 0, 1, -1 };
public int cutOffTree(List<List<Integer>> forest) {
m = forest.size(); n = forest.get(0).size();
List<int[]> trees = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (forest.get(i).get(j) > 1) trees.add(new int[] {i, j});
}
}
// 依次需要砍的树(树的高度从小到大)
Collections.sort(trees, (a, b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));
int step = 0;
int curX = 0, curY = 0;
for (int[] t : trees) {
int x = t[0], y = t[1];
int ret = bfs(x, y, curX, curY, forest);
if (ret == -1) return -1;
step += ret;
curX = x;
curY = y;
}
return step;
}
public int bfs(int x, int y, int curX, int curY, List<List<Integer>> forest) {
int ret = 0;
if (curX == x && curY == y) return 0;
boolean[][] check = new boolean[m][n];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] { curX, curY });
check[curX][curY] = true;
while (!q.isEmpty()) {
int size = q.size();
ret++;
while (size-- != 0) {
int[] t = q.poll();
int a = t[0], b = t[1];
for (int k = 0; k < 4; k++) {
int i = a + dx[k], j = b + dy[k];
if (i >= 0 && i < m && j >= 0 && j < n && forest.get(i).get(j) != 0 && !check[i][j]) {
if (forest.get(i).get(j) == forest.get(x).get(y))
return ret;
q.offer(new int[] { i, j });
check[i][j] = true;
}
}
}
}
return -1;
}
}
END
