1.最长递增子序列（LIS问题）
这道题提供提供了一种时间复杂度为O(NlogN) 的方法求解最长递增子序列的长度
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
| public int minOperations(int[] target, int[] arr) {
int m = target.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < m; i++) {
map.put(target[i], i);
}
List<Integer> list = new ArrayList<>();
for (int num : arr) {
if (map.containsKey(num)) list.add(map.get(num));
}
int n = list.size(), max = 0;
int[] f = new int[n], minTail = new int[n + 1];
Arrays.fill(minTail, 0x3f3f3f3f);
for (int i = 0; i < n; i++) {
int t = list.get(i);
int l = 0, r = i;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (minTail[mid] < t) {
l = mid;
} else {
r = mid - 1;
}
}
f[i] = l + 1;
max = Math.max(max, f[i]);
minTail[f[i]] = Math.min(minTail[f[i]], t);
}
return m - max;
}
|
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
| public int lengthOfLIS(int[] nums) {
int n = nums.length, max = 1;
int[] minTail = new int[n + 1];
Arrays.fill(minTail, 0x3f3f3f3f);
for (int i = 0; i < n; i++) {
int l = 0, r = i;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (minTail[mid] < nums[i]) {
l = mid;
} else {
r = mid - 1;
}
}
int cur = l + 1;
max = Math.max(max, cur);
minTail[cur] = Math.min(minTail[cur], nums[i]);
}
return max;
}
|
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
| public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int[] tails = new int[n];
tails[0] = envelopes[0][1];
int end = 0;
for (int i = 1; i < n; i++) {
int num = envelopes[i][1];
if (num > tails[end]) {
tails[++end] = num;
} else {
int l = 0, r = end;
while (l < r) {
int mid = l + (r - l) / 2;
if (tails[mid] < num) {
l = mid + 1;
} else {
r = mid;
}
}
tails[l] = num;
}
}
return end + 1;
}
|
LIS的O(NlogN)解法压缩至求3元递增子序列
LC334. 递增的三元子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
for (int num : nums) {
if (num > second) return true;
if (num < first) {
first = num;
} else if (first < num && num < second) {
second = num;
}
}
return false;
}
}
|
2.最长公共子序列（LCS问题）
最常规的DP转移方程就不说了，我们由此引出常见的问题模型：判断是否s1是否为s2子串
方法1：双指针->O(max(m,n))
写法1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
private boolean check(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
int p1 = 0, p2 = 0;
while (p1 <= len1 - 1 && p2 <= len2 - 1) {
while (p2 <= len2 - 1 && s1.charAt(p1) != s2.charAt(p2)) {
p2++;
}
if (p2 == len2) break;
p1++;
p2++;
}
return p1 == len1;
}
|
写法2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
private boolean match(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
int p1 = 0, p2 = 0;
while (p1 < len1 && p2 < len2) {
while (p2 < len2 && s2.charAt(p2) != s1.charAt(p1)) p2++;
if (p2 < len2) {
p1++;
p2++;
}
}
return p1 == len1;
}
|
方法2：DP->O(m*n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
private boolean check(String s1, String s2) {
int len1 = s1.length(), len2 = s2.length();
int[][] f = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
return f[len1][len2] == len1;
}
|
3.回文子串、子序列问题
最长回文子序列问题(非连续)
LC1312. 让字符串成为回文串的最少插入次数
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 minInsertions(String s) {
int n = s.length();
int[][] f = new int[n][n];
for (int i = 0; i < n; i++) {
f[i][i] = 1;
}
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1] + 2;
} else {
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
}
}
}
return n - f[0][n - 1];
}
}
|
最长回文子串问题(连续)
LC647. 回文子串
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
| class Solution {
public int countSubstrings(String s) {
int len = s.length();
int res = 0;
boolean[][] dp = new boolean[len][len];
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j <= len - 1; j++) {
if (s.charAt(i) != s.charAt(j)) {
continue;
}
if (j - i <= 2) {
dp[i][j] = true;
res++;
continue;
}
if (dp[i + 1][j - 1]) {
dp[i][j] = true;
res++;
}
}
}
return res;
}
}
|
LC5. 最长回文子串
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 String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxLen = 1;
int[] range = new int[]{0, 0};
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i <= 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
if (j - i + 1 > maxLen) {
maxLen = j - i + 1;
range = new int[]{i, j};
}
}
}
}
}
return s.substring(range[0], range[1] + 1);
}
}
|
