0.算法

1.迷宫中离⼊⼝最近的出⼝

. - 力扣（LeetCode）

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)return step;vis[x][y] = true;q.add(new int[] { x, y });}}}}return -1;}
}

 2.最小基因变化

433. 最小基因变化 - 力扣（LeetCode）

 

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;}
}

 3.单词接龙

127. 单词接龙 - 力扣（LeetCode）

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;}
}

4.为高尔夫比赛砍树

675. 为高尔夫比赛砍树 - 力扣（LeetCode）

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