1. 题目
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/#/descriptionhttps://leetcode-cn.com/problems/minimum-genetic-mutation/#/descriptionhttps://leetcode-cn.com/problems/generate-parentheses/#/descriptionhttps://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/#/descriptionhttps://leetcode-cn.com/problems/word-ladder/description/https://leetcode-cn.com/problems/word-ladder-ii/description/https://leetcode-cn.com/problems/number-of-islands/https://leetcode-cn.com/problems/minesweeper/description/
2. 题解
2.1 二叉树的层序遍历#102（中等）
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/#/description
// 法一：时间复杂度O(n),空间复杂度O(n)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int currentSize = queue.size();
for (int i = 0; i < currentSize; i++) {
TreeNode currentNode = queue.poll();
level.add(currentNode.val);
if (currentNode.left != null) {
queue.add(currentNode.left);
}
if (currentNode.right != null) {
queue.add(currentNode.right);
}
}
ans.add(level);
}
return ans;
}
}
2.2 最小基因变化#433（中等）
https://leetcode-cn.com/problems/minimum-genetic-mutation/#/description
class Solution {
// 法一：BFS.时间复杂度O(4*m*n),空间复杂度O(n),
// 4是4中基因变化，m是给定基因序列的长度，n是元素个数
public int minMutation(String start, String end, String[] bank) {
// 先把所有的有效基因放到set里面，方便后面调用contains方法
HashSet<String> bankSet = new HashSet<>(Arrays.asList(bank));
// 基因种类，后面用来做替换
String[] gen = {"A", "C", "G", "T"};
// BFS的初始队列，先加入起始基因
Deque<String> queue = new LinkedList<>();
queue.add(start);
// 曾经变异过的基因组要记录下来
Set<String> visited = new HashSet<>();
visited.add(start);
// 变化次数
int step = 0;
while (!queue.isEmpty()) {
// 当前层的个数，每下探一层的时候，
// 都会要执行一次这个，所以对应代码末尾会有一个step++的操作
int size = queue.size();
for (int i = 0; i < size; i++) {
String current = queue.poll();
// 如果是目标基因，就直接返回step
if (Objects.equals(current, end)) {
return step;
}
// 如果不是目标基因，则开始变异，对当前基因组的每一位都逐位变异
for (int j = 0; j < current.length(); j++) {
StringBuilder sb = new StringBuilder(current);
// 每一位基因都有四种变异可能，
for (int k = 0; k < gen.length; k++) {
// sb.replace(x,y,str).其中范围是[x,y),也就是左闭右开的
String replaced = sb.replace(j, j + 1, gen[k]).toString();
// 变异后的结果，如果没有访问过，并且是有效集合中的，那就允许执行下一次变异，加入到queue中
if (!visited.contains(replaced) && bankSet.contains(replaced)) {
queue.add(replaced);
// 并且标记当前变异已经访问过
visited.add(replaced);
}
}
}
}
// 和上文所说的对应的step++
step++;
}
// 如果没找到就返回-1
return -1;
}
}
2.3 括号生成#22（中等）
https://leetcode-cn.com/problems/generate-parentheses/#/description
class Solution {
public List<String> generateParenthesis(int n) {
//法三:回溯.时间复杂度和空间复杂度见官方题解
List<String> ans = new LinkedList<>();
StringBuilder path = new StringBuilder();
dfs(path, n, n, ans);
return ans;
}
private void dfs(StringBuilder path, int left, int right, List<String> ans) {
if (left == 0 && right == 0) {
ans.add(path.toString());
return;
}
//剪枝, 右括号剩余个数 > 左括号剩余个数时，才可以使用右括号
//那么相反的情况就得剪枝。
if (right < left) {
return;
}
//注意观察回溯和dfs的区别
if (left > 0) {
path.append("(");
dfs(path, left - 1, right, ans);
path.deleteCharAt(path.length() - 1);
}
if (right > 0) {
path.append(")");
dfs(path, left, right - 1, ans);
path.deleteCharAt(path.length() - 1);
}
}
}
2.4 在每个树行中找最大值#515（中等）
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/#/description
class Solution {
public List<Integer> largestValues(TreeNode root) {
//法一：BFS.时间复杂度O(n),空间复杂度O(n)
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
int layerMax = queue.peek().val;
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
layerMax = current.val > layerMax ? current.val : layerMax;
}
ans.add(layerMax);
}
return ans;
}
}
2.5 单词接龙#127（困难）
2.6 单词接龙Ⅱ#126（困难）
https://leetcode-cn.com/problems/word-ladder-ii/description/
2.7 岛屿数量#200（中等）
class Solution {
private void dfs(char[][] grid, int row, int column) {
int totalRow = grid.length;
int totalColumn = grid[0].length;
if (row < 0 || column < 0 || row >= totalRow || column >= totalColumn || grid[row][column] == '0') {
return;
}
//因为是深度遍历，我们要把当前岛屿中连着的陆地都变成海洋就好了，这样可以保证遍历完一个矩阵之后，不会重复遍历。且多个连着的陆地都只计算成一个岛屿。
grid[row][column] = '0';
// 遍历顺序无所谓，自己选一个上下左右。
dfs(grid, row - 1, column);
dfs(grid, row + 1, column);
dfs(grid, row, column - 1);
dfs(grid, row, column + 1);
}
public int numIslands(char[][] grid) {
//法一:DFS,时间复杂度O(MN),感觉每个元素至多被遍历一次。空间复杂度O(MN),如果每个元素都是陆地,最多就是MN层的栈。
if (grid == null || grid.length == 0) {
return 0;
}
int totalRow = grid.length;
int totalColumn = grid[0].length;
int ans = 0;
for (int row = 0; row < totalRow; row++) {
for (int column = 0; column < totalColumn; column++) {
if (grid[row][column] == '1') {
++ans;
dfs(grid, row, column);
}
}
}
return ans;
}
}
2.8 扫雷游戏#529（中等）
class Solution {
int[] dirX = {0, 1, 0, -1, 1, 1, -1, -1};
int[] dirY = {1, 0, -1, 0, 1, -1, 1, -1};
int totalRow;
int totalColumn;
char[][] board;
public char[][] updateBoard(char[][] board, int[] click) {
// 法一：dfs+模拟。时间复杂度O(mn),空间复杂度O(mn).
this.totalRow = board.length;
this.totalColumn = board[0].length;
this.board = board;
int row = click[0], column = click[1];
if (board[row][column] == 'M') {
board[row][column] = 'X';
} else {
dfs(row, column);
}
return board;
}
private void dfs(int row, int column) {
int count = countM(row, column);
if (count > 0) {
// 规则3
board[row][column] = (char) (count + '0');
} else {
// 规则2
board[row][column] = 'B';
for (int i = 0; i < 8; ++i) {
int tx = row + dirX[i];
int ty = column + dirY[i];
// 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length || board[tx][ty] != 'E') {
continue;
}
dfs(tx, ty);
}
}
}
private int countM(int row, int column) {
int cnt = 0;
for (int i = 0; i < 8; i++) {
int x = row + dirX[i];
int y = column + dirY[i];
if (x < 0 || x >= totalRow || y < 0 || y >= totalColumn) {
continue;
}
if (board[x][y] == 'M') {
cnt++;
}
}
return cnt;
}
}
若有收获，就点个赞吧
0 人点赞
