892.三维形体的表面积

✒解题思路：

  1. 每个立方体提供6个面，垂直方向，行方向，列方向每重叠一次减去两个面。
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
class Solution {
	public int surfaceArea(int[][] grid) {
		int m = grid.length;
		if (m == 0) {
			return 0;
		}
		int n = grid[0].length;
		if (n == 0) {
			return 0;
		}
		int result = 0;
		int vertical = 0;
		int row = 0;
		int col = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				result += grid[i][j];
				if (grid[i][j] > 1) {
					vertical += grid[i][j] - 1;
				}
				if (j > 0) {
					row += Math.min(grid[i][j], grid[i][j - 1]);
				}
				if (i > 0) {
					col += Math.min(grid[i][j], grid[i - 1][j]);
				}
			}
		}
		return result * 6 - (vertical + row + col) * 2;
	}
}

91.解码方法

✒解题思路：

  1. 当首字母为’0’返回0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	public int numDecodings(String s) {
		int len = s.length();
		if (len == 0 || s.charAt(0) == '0') {
			return 0;
		}
		int[] dp = new int[len + 1];
		dp[0] = dp[1] = 1;
		for (int i = 2; i <= len; i++) {
			if (s.charAt(i - 1) != '0') {
				dp[i] += dp[i - 1];
			}
			if (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) < '7')) {
				dp[i] += dp[i - 2];
			}
		}
		return dp[len];
	}
}

96.不同的二叉搜索树

✒解题思路：

  1. 卡塔兰公式:
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	public int numTrees(int n) {
		int[] dp = new int[n + 1];
		dp[0] = dp[1] = 1;
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				dp[i] += dp[j - 1] * dp[i - j];
			}
		}
		return dp[n];
	}
}

95.不同的二叉搜索树II

✒解题思路：

  1. emmm
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public List<TreeNode> generateTrees(int n) {
		if (n == 0) {
			return new ArrayList<>();
		}
		return helper(1, n);
	}

	private List<TreeNode> helper(int start, int end) {
		List<TreeNode> result = new ArrayList<>();
		if (start > end) {
			result.add(null);
		}
		for (int i = start; i <= end; i++) {
			List<TreeNode> leftList = helper(start, i - 1);
			List<TreeNode> rightList = helper(i + 1, end);

			for (TreeNode left : leftList) {
				for (TreeNode right : rightList) {
					TreeNode root = new TreeNode(i);
					root.left = left;
					root.right = right;
					result.add(root);
				}
			}
		}
		return result;
	}
}

120.三角形最小路径和

✒解题思路：

  1. 自底向上DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	public int minimumTotal(List<List<Integer>> triangle) {
		int m = triangle.size();
		if (m == 0) {
			return 0;
		}
		int[] dp = new int[m];
		List<Integer> list = triangle.get(m - 1);
		for (int i = 0; i < m; i++) {
			dp[i] = list.get(i);
		}
		for (int i = 0; i < m - 1; i++) {
			for (int j = 0; j < m - i - 1; j++) {
				dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(m - i - 2).get(j);
			}
		}
		return dp[0];
	}
}