836.矩阵重叠

✒解题思路：

  1. 判断两个矩形的四个角落
1
2
3
4
5
class Solution {
	public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
		return !(rec1[3] <= rec2[1] || rec1[2] <= rec2[0] || rec1[1] >= rec2[3] || rec1[0] >= rec2[2]);
	}
}

46.全排列

✒解题思路：

  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
class Solution {
	public List<List<Integer>> permute(int[] nums) {
		int len = nums.length;
		List<List<Integer>> result = new ArrayList<>();
		if (len < 1) {
			return result;
		}
		boolean[] used = new boolean[len];
		List<Integer> path = new ArrayList<>();
		dfs(nums, result, path, used, 0);
		return result;
	}

	private void dfs(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used, int depth) {
		if (depth == nums.length) {
			result.add(new ArrayList<>(path));
		}
		for (int i = 0; i < nums.length; i++) {
			if (!used[i]) {
				path.add(nums[i]);
				used[i] = true;
				dfs(nums, result, path, used, depth + 1);
				used[i] = false;
				path.remove(path.size() - 1);
			}
		}
	}
}

47.全排列II

✒解题思路：

  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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
		List<List<Integer>> result = new ArrayList<>();
		if (len < 1) {
			return result;
		}
		boolean[] used = new boolean[len];
		List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
		dfs(nums, result, path, used, 0);
		return result;
    }
	private void dfs(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used, int depth) {
		if (depth == nums.length) {
			result.add(new ArrayList<>(path));
		}
		for (int i = 0; i < nums.length; i++) {
			if (used[i]) {
				continue;
			}
			if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
				continue;
			}
			path.add(nums[i]);
			used[i] = true;
			dfs(nums, result, path, used, depth + 1);
			used[i] = false;
			path.remove(path.size() - 1);
		}
	}
}

784.字母大小写全排列

✒解题思路：

  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
class Solution {
	public List<String> letterCasePermutation(String S) {
		int len = S.length();
		List<String> result = new ArrayList<>();
		if (len == 0) {
			return result;
		}
		char[] chars = new char[len];
		dfs(S, 0, len, result, chars);
		return result;
	}

	private void dfs(String s, int start, int len, List<String> result, char[] chars) {
		if (start == len) {
			result.add(new String(chars));
            return ;
		}
		chars[start] = s.charAt(start);
		dfs(s, start + 1, len, result, chars);
		if (Character.isLetter(s.charAt(start))) {
			chars[start] = (char) (s.charAt(start) ^ (1 << 5));
			dfs(s, start + 1, len, result, chars);
		}
	}
}

213.打家劫舍II

✒解题思路：

  1. 分解成[0…n-1]和[1…n]两种情况即可
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
class Solution {
	public int rob(int[] nums) {
        int len = nums.length;
		if (len == 0) {
			return 0;
		}
		if (len == 1) {
			return nums[0];
		}
		if (len == 2) {
			return Math.max(nums[0], nums[1]);
		}
		return Math.max(helper(Arrays.copyOfRange(nums, 0, nums.length - 1)),
				helper(Arrays.copyOfRange(nums, 1, nums.length)));
	}

	private int helper(int[] nums) {
		int len = nums.length;
		if (len == 0) {
			return 0;
		}
		if (len == 1) {
			return nums[0];
		}
		if (len == 2) {
			return Math.max(nums[0], nums[1]);
		}
		int[] dp = new int[len];
		dp[0] = nums[0];
		dp[1] = Math.max(nums[0], nums[1]);
		for (int i = 2; i < len; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
		}
		return dp[len - 1];
	}
}

63.不同路径II

✒解题思路：

  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
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length;
		if (m == 0) {
			return 0;
		}
		int n = obstacleGrid[0].length;
		int[][] dp = new int[m][n];
		if (obstacleGrid[0][0] == 1) {
			return 0;
		}
		dp[0][0] = 1;
		for (int i = 1; i < m; i++) {
			if (obstacleGrid[i][0] == 0) {
				dp[i][0] = 1;
			} else {
				break;
			}
		}
		for (int i = 1; i < n; i++) {
			if (obstacleGrid[0][i] == 0) {
				dp[0][i] = 1;
			} else {
				break;
			}
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (obstacleGrid[i][j] == 1) {
					dp[i][j] = 0;
				} else {
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
			}
		}
		return dp[m - 1][n - 1];
	}
}

15.最长回文子串

✒解题思路：

  1. 暴力法

  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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//暴力法
class Solution {
	public String longestPalindrome(String s) {
		int len = s.length();
		if (len < 2) {
			return s;
		}
		String result = s.substring(0, 1);
		int maxLen = 1;
		for (int i = 0; i < len - 1; i++) {
			for (int j = i + 1; j < len; j++) {
				if (j - i + 1 > maxLen && valid(s, i, j)) {
					maxLen = j - i + 1;
					result = s.substring(i, j + 1);
				}
			}
		}
		return result;
	}

	private boolean valid(String s, int left, int right) {
		while (left < right) {
			if (s.charAt(left) != s.charAt(right)) {
				return false;
			}
			left++;
			right--;
		}
		return true;
	}
}
//DP
class Solution {
	public String longestPalindrome(String s) {
		int len = s.length();
		if (len < 2) {
			return s;
		}
		boolean[][] dp = new boolean[len][len];
		for (int i = 0; i < len; i++) {
			dp[i][i] = true;
		}
		int maxLen = 1;
		int start = 0;
		for (int j = 1; j < len; j++) {
			for (int i = 0; i < j; i++) {
				if (s.charAt(j) == s.charAt(i)) {
					if (j - i < 3) {
						dp[i][j] = true;
					} else {
						dp[i][j] = dp[i + 1][j - 1];
					}
				} else {
					dp[i][j] = false;
				}
				if (dp[i][j]) {
					if (j - i + 1 > maxLen) {
						maxLen = j - i + 1;
						start = i;
					}
				}
			}
		}
		return s.substring(start, start + maxLen);
	}
}

322.零钱兑换

✒解题思路：

  1. DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
	public int coinChange(int[] coins, int amount) {
		if (coins.length < 1) {
			return -1;
		}
		int[] dp = new int[amount + 1];
		Arrays.fill(dp, amount + 1);
		dp[0] = 0;
		for (int i = 1; i <= amount; i++) {
			for (int j = 0; j < coins.length; j++) {
				if (i >= coins[j]) {
					dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
				}
			}
		}
		return dp[amount] == amount + 1 ? -1 : dp[amount];
	}
}

121.买卖股票的最佳时机（DP）

✒解题思路：

  1. DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public int maxProfit(int[] prices) {
		int len = prices.length;
		if (len < 2) {
			return 0;
		}
		int[][] dp = new int[len][2];
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
		}
		return dp[len - 1][0];
	}
}

122.买卖股票的最佳时机II

✒解题思路：

  1. DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
	public int maxProfit(int[] prices) {
		int len = prices.length;
		if (len < 2) {
			return 0;
		}
		int[][] dp = new int[len][2];
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1],dp[i-1][0] - prices[i]);
		}
		return dp[len - 1][0];
	}
}

309.最佳买卖股票时机含冷冻期

✒解题思路：

  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 maxProfit(int[] prices) {
		int len = prices.length;
		if (len < 2) {
			return 0;
		}
		int[][] dp = new int[len][2];
		dp[0][0] = 0;
		dp[0][1] = -prices[0]; 
        dp[1][0] = Math.max(dp[0][0],dp[0][1]+prices[1]);
        dp[1][1] = Math.max(dp[0][1],-prices[1]);

		for (int i = 2; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1],dp[i-2][0] - prices[i]);
		}
		return dp[len - 1][0];
	}
}