338.比特位计数

✒解题思路：

  1. DP

  2. DP

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
//方法1
class Solution {
	public int[] countBits(int num) {
		int[] dp = new int[num + 1];
		dp[0] = 0;
        if (num == 0) {
			return dp;
		}
		dp[1] = 1;
		for (int i = 2; i <= num; i++) {
			dp[i] = dp[i / 2] + dp[i % 2];
		}
		return dp;
	}
}
//方法2
class Solution {
    public int[] countBits(int num) {
		int[] dp = new int[num + 1];
		dp[0] = 0;
		for (int i = 1; i <= num; i++) {
			if ((i & 1) == 1) {
				dp[i] = dp[i - 1] + 1;
			} else {
				dp[i] = dp[i / 2];
			}
		}
		return dp;
	}
}

999.车的可用的捕获量

✒解题思路：

  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
class Solution {
	public int numRookCaptures(char[][] board) {
		int m = board.length;
		int n = board[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 'R') {
					return dfs(i, j, board);
				}
			}
		}
		return 0;
	}

	private int dfs(int i, int j, char[][] board) {
		int result = 0;
		//同一行
		for (int l = j + 1; l < board[0].length; l++) {
			if (board[i][l] == 'B') {
				break;
			} else if (board[i][l] == '.') {
				continue;
			} else {
				result++;
				break;
			}
		}
		for (int l = j - 1; l >= 0; l--) {
			if (board[i][l] == 'B') {
				break;
			} else if (board[i][l] == '.') {
				continue;
			} else {
				result++;
				break;
			}
		}
		for (int l = i + 1; l < board[0].length; l++) {
			if (board[l][j] == 'B') {
				break;
			} else if (board[l][j] == '.') {
				continue;
			} else {
				result++;
				break;
			}
		}
		for (int l = i - 1; l >= 0; l--) {
			if (board[l][j] == 'B') {
				break;
			} else if (board[l][j] == '.') {
				continue;
			} else {
				result++;
				break;
			}
		}
		return result;
	}
}

221.最大正方形

✒解题思路：

  1. DP
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
class Solution {
	public int maximalSquare(char[][] matrix) {
		int m = matrix.length;
		if (m == 0) {
			return 0;
		}
		int n = matrix[0].length;
		if (n == 0) {
			return 0;
		}
		int result = 0;
		int[][] dp = new int[m + 1][n + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (matrix[i - 1][j - 1] == '1') {
					dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
				}
				if (dp[i][j] > result) {
					result = dp[i][j];
				}
			}
		}
		return result * result;
	}
}

1277.统计全为1的正方形子矩阵

✒解题思路：

  1. DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
	public int countSquares(int[][] matrix) {
		int m = matrix.length;
		int n = matrix[0].length;
		int result = 0;
		int[][] dp = new int[m + 1][n + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (matrix[i - 1][j - 1] == 1) {
					dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
				}
				result += dp[i][j];
			}
		}
		return result;
	}
}

47.礼物的最大价值

✒解题思路：

  1. 自底向上DP

  2. 优化DP

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
//DP
class Solution {
	public int maxValue(int[][] grid) {
		int m = grid.length;
		if (m == 0) {
			return 0;
		}
		int n = grid[0].length;
		if (n == 0) {
			return 0;
		}
		int[][] dp = new int[m][n];
		dp[0][0] = grid[0][0];
		for (int i = 1; i < m; i++) {
			dp[i][0] = dp[i - 1][0] + grid[i][0];
		}
		for (int i = 1; i < n; i++) {
			dp[0][i] = dp[0][i - 1] + grid[0][i];
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
			}
		}
		return dp[m - 1][n - 1];
	}
}
//优化
class Solution {
    public int maxValue(int[][] grid) {
		int m = grid.length;
		if (m == 0) {
			return 0;
		}
		int n = grid[0].length;
		if (n == 0) {
			return 0;
		}
		int[] dp = new int[n];
        dp[0] = grid[0][0];
		for (int i = 1; i < n; i++) {
			dp[i] = grid[0][i] + dp[i - 1];
		}
		for (int i = 1; i < m; i++) {
			dp[0] = grid[i][0] + dp[0];
			for (int j = 1; j < n; j++) {
				dp[j] = Math.max(dp[j - 1], dp[j]) + grid[i][j];
			}
		}
		return dp[n - 1];
	}
}