- LeetCode2145:统计隐藏数组的数目
- 时间:2022-01-22
- 力扣难度:Meduim
- 个人难度:Meduim
- 数据结构:数组
- 算法:前缀和、差分、区间求和
LeetCode2145.统计隐藏数组的数目:「前缀和 & 区间夹逼」&「前缀和 & 空间优化」
|
技术博客 研发小白
每日一题:LeetCode:1332.删除回文子序列
每日一题:LeetCode:1246.删除回文子数组
题目:原题链接
1 <= s.length <= 1000
s
仅包含字母 'a'
和 'b'
输入输出规范
输入:字符串
输出:整型,表示删除所需的次数
输入输出示例
思路
题解
1
2
3
4
5
6
7
8
9 public int removePalindromeSub(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
for(int i = 0; i < n/2; i++) {
if(s.charAt(i) != s.charAt(n - i - 1)) return 2;
}
return 1;
}
复杂度分析:n 是字符串的大小
扩展:删除回文子串、子数组
题目:原题链接:LeetCode1246.删除回文子数组
1 <= arr.length <= 100
1 <= arr[i] <= 20
输入输出规范
输入:数组
输出:整型,表示删除所需的次数
输入输出示例
思路
memo[left][right]
就表示索引从 left 到 right 的子数组的最少删除次数left + 1 == i
时,即这两个相同元素相邻,此时因为只能拆分出一个子数组,另一个是空的(left + 1, i - 1),所以此时次数还需要加1,表示删除 left 和 i 元素的操作题解
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 // 记忆化搜索
int[][] memo;
public int minimumMoves(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int n = arr.length;
if (n == 1) return 1;
memo = new int[n][n];
return dfs(arr, 0, n - 1);
}
private int dfs(int[] arr, int left, int right) {
if (left > right) return 0;
if(memo[left][right] != 0) return memo[left][right];
int count = 0;
// 第一种情况,单独删除
count = dfs(arr, left + 1, right) + 1;
// 第二种情况,构成回文串删除
for (int i = left + 1; i <= right; i++) {
if (arr[i] == arr[left]) {
// 取两种情况中的最小值,且第二种情况是将数组拆分开来分别计算的
count = Math.min(count, dfs(arr, left + 1, i - 1) + dfs(arr, i + 1, right));
// 第二种情况中的特殊情况:两个相同元素相邻
count += left == i - 1 ? 1 : 0;
}
}
memo[left][right] = count;
return count;
}
复杂度分析:n 是数组的大小
思路
dp[i][j]
表示区间[i, j]构成的子数组的最少删除次数j - i + 1
,即对应单独删除的情况,或者将dp[i][i]
初始化为 1 状态转移方程分析
dp[i][j] = Math.min(dp[i][j],dp[i+1][j-1])
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j])
图解
题解
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 public int minimumMovesDP(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int n = arr.length;
if (n == 1) return 1;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[i][i] = 1; // i == j
}
for (int j = 1; j < n; j++) {
for (int i = j - 1; i >= 0; i--) {
// 元素相邻的情况
if (i == j - 1) {
dp[i][j] = arr[i] == arr[j] ? 1 : 2;
continue;
}
// 两端元素相等的情况
if (arr[i] == arr[j]) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
}
//
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
return dp[0][n - 1];
}
复杂度分析:n 是数组的大小
=LeetCode1332:删除回文子序列
LeetCode1246:删除回文子数组
题目:原题链接
1 <= s.length <= 1000
s
仅包含字母 'a'
和 'b'
输入输出规范
输入:字符串
输出:整型,表示删除所需的次数
输入输出示例
思路
题解
1
2
3
4
5
6
7
8
9 public int removePalindromeSub(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
for(int i = 0; i < n/2; i++) {
if(s.charAt(i) != s.charAt(n - i - 1)) return 2;
}
return 1;
}
复杂度分析:n 是字符串的大小
扩展:删除回文子串、子数组
题目:原题链接:LeetCode1246.删除回文子数组
1 <= arr.length <= 100
1 <= arr[i] <= 20
输入输出规范
输入:数组
输出:整型,表示删除所需的次数
输入输出示例
思路
memo[left][right]
就表示索引从 left 到 right 的子数组的最少删除次数left + 1 == i
时,即这两个相同元素相邻,此时因为只能拆分出一个子数组,另一个是空的(left + 1, i - 1),所以此时次数还需要加1,表示删除 left 和 i 元素的操作题解
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 // 记忆化搜索
int[][] memo;
public int minimumMoves(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int n = arr.length;
if (n == 1) return 1;
memo = new int[n][n];
return dfs(arr, 0, n - 1);
}
private int dfs(int[] arr, int left, int right) {
if (left > right) return 0;
if(memo[left][right] != 0) return memo[left][right];
int count = 0;
// 第一种情况,单独删除
count = dfs(arr, left + 1, right) + 1;
// 第二种情况,构成回文串删除
for (int i = left + 1; i <= right; i++) {
if (arr[i] == arr[left]) {
// 取两种情况中的最小值,且第二种情况是将数组拆分开来分别计算的
count = Math.min(count, dfs(arr, left + 1, i - 1) + dfs(arr, i + 1, right));
// 第二种情况中的特殊情况:两个相同元素相邻
count += left == i - 1 ? 1 : 0;
}
}
memo[left][right] = count;
return count;
}
复杂度分析:n 是数组的大小
思路
dp[i][j]
表示区间[i, j]构成的子数组的最少删除次数j - i + 1
,即对应单独删除的情况,或者将dp[i][i]
初始化为 1 状态转移方程分析
dp[i][j] = Math.min(dp[i][j],dp[i+1][j-1])
dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j])
图解
题解
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 public int minimumMovesDP(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int n = arr.length;
if (n == 1) return 1;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[i][i] = 1; // i == j
}
for (int j = 1; j < n; j++) {
for (int i = j - 1; i >= 0; i--) {
// 元素相邻的情况
if (i == j - 1) {
dp[i][j] = arr[i] == arr[j] ? 1 : 2;
continue;
}
// 两端元素相等的情况
if (arr[i] == arr[j]) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
}
//
for (int k = i; k < j; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
return dp[0][n - 1];
}
复杂度分析:n 是数组的大小