解决最短路径问题

1. 迷宫中离入口最近的出口（1926）

题目描述：

算法原理：
其实路径最短问题和前一篇博客说到的FloodFill问题我理解的最大区别就是，出队的时候前者需要一次性出完，也就是每次出队需要记录size然后要等size个元素出完队，后者则是一个一个出队。针对这一题逻辑上也是一样，元素出队要一层一层地去出，然后如果说当前出队的元素的上下左右其中一个元素坐标满足相应条件，并且没被遍历过不是墙，并且恰好来到了边缘那么就返回，如果入队的所有元素都出完了还没返回就说明在迷宫出不去了，此时返回-1，具体看代码。
代码如下：

class Solution {public int nearestExit(char[][] maze, int[] entrance) {int m = maze.length, n = maze[0].length;boolean[][] vis = new boolean[m][n];int ret = 0;int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{entrance[0], entrance[1]});vis[entrance[0]][entrance[1]]=true;while (!queue.isEmpty()) {ret++;int sz = queue.size();while (sz-- != 0) {int[] tmp = queue.poll();int a = tmp[0], b = tmp[1];for (int i = 0; i < 4; i++) {int x = a + dx[i];int y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && maze[x][y] == '.') {queue.add(new int[]{x, y});vis[x][y] = true;if (x == 0 || x == m - 1 || y == 0 || y == n - 1) {return ret;}}}}}return -1;}
}

题目链接

2. 最小基因变化（433）

题目描述：

算法原理：
题目要我们去将给定的start字符串去转化为end的字符串并且转化过程的字符串需要包含在bank数组之内并且改变的字符就只是ACGT，我们可以使用上题类似的思想将start放入一个队列，然后使用两层的循环，第一层去遍历字符串的位数，第二层去遍历ACGT，这两层循环就代表着去将start字符串的每一位都用ACGT的每一个字符轮流替换一下，如果变换出的新的字符串包含在bank中并且没有被访问过，那么就将其加入队列并且开始下一轮直至变换至end字符串。当然还有一种特殊情况就是bank当中不包含end，那么直接返回-1即可。
代码如下：

class Solution {public int minMutation(String startGene, String endGene, String[] bank) {Set<String> hash = new HashSet<>();Set<String> vis = new HashSet<>();char[] chs = { 'A', 'C', 'G', 'T' };for (String str : bank) {hash.add(str);}if (startGene.equals(endGene)) {return 0;}if (!hash.contains(endGene)) {return -1;}Queue<String> queue = new LinkedList<>();queue.add(startGene);vis.add(startGene);int ret = 0;while (!queue.isEmpty()) {ret++;int size = queue.size();while (size-- != 0) {String t = queue.poll();for (int i = 0; i < 8; i++) {char[] temp = t.toCharArray();for (int j = 0; j < 4; j++) {temp[i] = chs[j];String next = new String(temp);if (!vis.contains(next) && hash.contains(next)) {if (next.equals(endGene)) {return ret;}queue.add(next);vis.add(next);}}}}}return -1;}
}

题目链接

3. 单词接龙（127）

题目描述：

算法原理：
这一题和上一题的做法和思想类似，唯一的区别就是步数是上题步数加一。
代码如下：

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Set<String> hash = new HashSet<String>();for (String str : wordList) {hash.add(str);}Set<String> vis = new HashSet<String>();Queue<String> q = new LinkedList<>();int ret = 1;q.add(beginWord);vis.add(beginWord);while (!q.isEmpty()) {int sz = q.size();ret++;while(sz--!=0) {String s=q.poll();for(int i=0;i<s.length();i++) {char[] ss=s.toCharArray();for(char ch='a';ch<='z';ch++) {ss[i]=ch;String temp=new String(ss);if(hash.contains(temp)&&!vis.contains(temp)) {if(temp.equals(endWord)) {return ret;}q.add(temp);vis.add(temp);}}}}}return 0;}
}

题目链接

4. 为高尔夫比赛砍树（675）

题目描述：

算法原理：
根据题意我们可以简化问题，将每个树在矩阵中的坐标管理在队列中，并且根据树的高度进行降序排序。然后从（0，0）出发将出队的第一队坐标作为终点来计算需要多少步，后续就是类似起点就换成上一次的终点，终点就换成下一次出队的坐标。将每段过程的步数加起来就是最终的结果。
代码如下：

class Solution {int m, n;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) -> {return forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]);});int ret = 0;int bx = 0, by = 0;for (int[] tree : trees) {int x = tree[0], y = tree[1];int step = bfs(forest, bx, by, x, y);if (step == -1) {return -1;}ret += step;bx = x;by = y;}return ret;}int[] dx = { 1, -1, 0, 0 };int[] dy = { 0, 0, 1, -1 };public int bfs(List<List<Integer>> forest, int bx, int by, int ex, int ey) {if (ex == bx && ey == by) {return 0;}int step = 0;Queue<int[]> q = new LinkedList<>();boolean[][] vis = new boolean[m][n];q.add(new int[] { bx, by });vis[bx][by] = true;while (!q.isEmpty()) {int sz = q.size();step++;while (sz-- != 0) {int[] temp = q.poll();int a = temp[0], b = temp[1];for (int i = 0; i < 4; i++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && forest.get(x).get(y) != 0) {if (x == ex && y == ey) {return step;}q.add(new int[] { x, y });vis[x][y] = true;}}}}return -1;}
}

题目链接