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