733.图像渲染

✒解题思路：

  1. 深度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
	public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		int color = image[sr][sc];
		if (color != newColor) {
			dfs(image, sr, sc, color, newColor);
		}
		return image;
	}

	private void dfs(int[][] image, int sr, int sc, int color, int newColor) {
		if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length) {
			return;
		}
		if (image[sr][sc] != color || image[sr][sc] == newColor) {
			return;
		}
		image[sr][sc] = newColor;
		dfs(image, sr - 1, sc, color, newColor);
		dfs(image, sr + 1, sc, color, newColor);
		dfs(image, sr, sc - 1, color, newColor);
		dfs(image, sr, sc + 1, color, newColor);
	}
}

690.员工的重要性

✒解题思路：

  1. 深度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {
	public int getImportance(List<Employee> employees, int id) {
		HashMap<Integer, Employee> map = new HashMap<>();
		for (Employee employee : employees) {
			map.put(employee.id, employee);
		}
		return dfs(id, map);
	}

	private int dfs(int id, HashMap<Integer, Employee> map) {
		Employee employee = map.get(id);
		int result = employee.importance;
		for (Integer i : employee.subordinates) {
			result += dfs(i, map);
		}
		return result;
	}
}

365.水壶问题

✒解题思路：

  1. 数学题……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
	public boolean canMeasureWater(int x, int y, int z) {
		if (x + y < z) {
			return false;
		}
		if (x == 0 || y == 0) {
			return z == 0 || x + y == z;
		}
		return z % gcd(x, y) == 0;
	}

	int gcd(int m, int n) {
		if (m < n) {
			int t = m;
			m = n;
			n = t;
		}
		if (m % n == 0) {
			return n;
		} else {
			return gcd(n, m % n);
		}
	}
}

129.求根到叶子节点数字之和

✒解题思路：

  1. 深度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//解法一
class Solution {
    	public int sumNumbers(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return root.val;
		}
		return dfs(root, 0);
	}

	private int dfs(TreeNode root, int result) {
		if (root == null) {
			return 0;
		}
		int sum = result * 10 + root.val;
		if (root.left == null && root.right == null) {
			return sum;
		}
		return dfs(root.left, sum) + dfs(root.right, sum);
	}
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//解法二
class Solution {
    private int result;
	public int sumNumbers(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return root.val;
		}
        result=0;
		dfs(root, 0);
		return result;
	}

	private void dfs(TreeNode root, int sum) {
		if (root == null) {
			return;
		}
		int k = sum * 10 + root.val;
		if (root.left == null && root.right == null) {
			result += k;
            return;
		}
		dfs(root.left, k);
		dfs(root.right, k);
	}
}

130.被围绕的区域

✒解题思路：

  1. 深度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
	public void solve(char[][] board) {
		int m = board.length;
		if (m < 1) {
			return;
		}
		int n = board[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 'O' && (i == 0 || j == 0 || i == m - 1 || j == n - 1)) {
					dfs(board, i, j);
				}
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O'){
				    board[i][j] = 'X';
				}
				if (board[i][j] == '#') {
					board[i][j] = 'O';
				}
			}
		}
	}

	private void dfs(char[][] board, int i, int j) {
		if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#' || board[i][j] == 'X') {
			return;
		}
		board[i][j] = '#';
		dfs(board, i + 1, j);
		dfs(board, i - 1, j);
		dfs(board, i, j + 1);
		dfs(board, i, j - 1);
	}
}