参考：
CyC2018
Carl
leetcode cookbook
1、岛屿的最大面积
// 经典DFS，关键在于dfs函数
class Solution {
private int[][] directs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int area = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
area = Math.max(area, dfs(grid, i, j));
}
}
return area;
}
public int dfs(int[][] grid, int x, int y) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
return 0;
}
int res = 1;
grid[x][y] = 0;
for (int[] direct : directs) {
int nx = x + direct[0];
int ny = y + direct[1];
res += dfs(grid, nx, ny);
}
return res;
}
}
2、岛屿数量
// dfs效率比bfs快
class Solution {
private int[][] directs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '0')
continue;
dfs(grid, i, j);
res++;
}
}
return res;
}
private void dfs(char[][] grid, int x, int y) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0') {
return;
}
grid[x][y] = '0';
for (int[] direct : directs) {
int nx = x + direct[0];
int ny = y + direct[1];
dfs(grid, nx, ny);
}
}
}
3、省份数量
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
int ans = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(isConnected, visited, i);
ans++;
}
}
return ans;
}
public void dfs(int[][] isConnected, boolean[] visited, int x) {
int n = isConnected.length;
for (int j = 0; j < n; j++) {
if (!visited[j] && isConnected[x][j] == 1) {
visited[j] = true;
dfs(isConnected, visited, j);
}
}
}
}
4、被围绕的区域
// bfs，先判断与不被包围的'O'，使其变为A。然后在统一刷一遍。
class Solution {
public void solve(char[][] board) {
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int j = 1; j < n - 1; j++) {
dfs(board, 0, j);
dfs(board, m - 1, j);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int x, int y) {
int m = board.length;
int n = board[0].length;
if (x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O') {
return;
}
board[x][y] = 'A';
dfs(board, x + 1, y);
dfs(board, x - 1, y);
dfs(board, x, y + 1);
dfs(board, x, y - 1);
}
}
// heights
class Solution {
private int[][] directs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
private int m;
private int n;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
m = heights.length;
n = heights[0].length;
List<List<Integer>> res = new ArrayList<>();
int[][] P = new int[m][n];
int[][] A = new int[m][n];
for (int i = 0; i < n; i++) {
dfs(heights, P, 0, i);
dfs(heights, A, m - 1, i);
}
for (int j = 0; j < m; j++) { // m, n 不要搞反了
dfs(heights, P, j, 0);
dfs(heights, A, j, n - 1);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (A[i][j] == 2 && P[i][j] == 2) {
List<Integer> tmp = Arrays.asList(i, j);
res.add(tmp);
}
}
}
return res;
}
public void dfs(int[][] heights, int[][] flag, int x, int y) {
if (flag[x][y] == 2) {
return;
}
flag[x][y] = 2; // 在这里更新
for (int[] direct : directs) {
int nx = x + direct[0];
int ny = y + direct[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && flag[nx][ny] == 0 && heights[x][y] <= heights[nx][ny]) {
dfs(heights, flag, nx, ny);
}
}
}
}
// 记忆矩阵叫memo比较好
class Solution {
int[][] directs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int longestIncreasingPath(int[][] matrix) {
int M = matrix.length;
int N = matrix[0].length;
int res = 0;
int[][] maxRes = new int[M][N];
int maxVal = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
maxVal = Math.max(maxVal, dfs(matrix, maxRes, i, j));
}
}
return maxVal;
}
public int dfs(int[][] matrix, int[][] maxRes, int x, int y) {
int M = matrix.length;
int N = matrix[0].length;
if (maxRes[x][y] != 0) {
return maxRes[x][y];
}
int res = 1;
for (int[] direct : directs) {
int cx = x + direct[0];
int cy = y + direct[1];
if (cx >= 0 && cy >= 0 && cx < M && cy < N && matrix[x][y] < matrix[cx][cy]) {
res = Math.max(res, 1 + dfs(matrix, maxRes, cx, cy)); // 这里注意加1的位置
}
}
maxRes[x][y] = res;
return res;
}
}
8、验证二叉搜索树
9、恢复二叉搜索树
10、路径总和 II
11、二叉树展开为链表
12、二叉树中的最大路径和
13、求根节点到叶节点数字之和
14、二叉树的右视图
15、课程表
16、课程表 II
17、添加与搜索单词 - 数据结构设计
18、完全二叉树的节点个数
19、二叉搜索树中第K小的元素
20、二叉树的最近公共祖先
21、二叉树的序列化与反序列化
22、矩阵中的最长递增路径
23、打家劫舍 III
24、迷你语法分析器
25、字典序排数
26、除法求值
27、 路径总和 III
28、出现次数最多的子树元素和
29、找树左下角的值
30、在每个树行中找最大值
31、扫雷游戏
32、把二叉搜索树转换为累加树
33、在二叉树中增加一行
34、二叉树最大宽度
35、修剪二叉搜索树
36、冗余连接
37、冗余连接 II
38、账户合并
39、破解保险箱
40、金字塔转换矩阵
41、情侣牵手
42、水位上升的泳池中游泳
43、判断二分图
44、找到最终的安全状态
45、树中距离之和
46、相似字符串组
47、钥匙和房间
48、喧闹和富有
49、二叉树中所有距离为 K 的结点
