1. 最长公共子序列
题目
给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。
测试案例
输入：字符串1：BDCABA，字符串2：ABCBDAB
输出：最长公共子序列长度为4，最长公共子序列是：BCBA
代码如下
class Solution{
public void LCS(String s1, String s2){
int n1 = s1.length(), n2 = s2.length();
if(n1 == 0 || n2 == 0){
return;
}
int[][] record = new int[n1 + 1][n2 + 1];
for(int i = 1; i <= n1; i++){
for(int j = 1; j <= n2; j++){
if(s1.charAt(i - 1) == s2.charAt(j - 1)){
record[i][j] = record[i - 1][j - 1] + 1;
}
else{
record[i][j] = record[i][j - 1];
if(record[i][j] < record[i - 1][j]){
record[i][j] = record[i - 1][j];
}
}
}
}
print(s1, s2, record, n1, n2);
}
void print(String s1, String s2, int[][] record, int n1, int n2){
if(record[n1][n2] == 0){
return;
}
if(record[n1][n2] == record[n1][n2 - 1]){
print(s1, s2, record, n1, n2 - 1);
}
else if(record[n1][n2] == record[n1 - 1][n2]){
print(s1, s2, record, n1 - 1, n2);
}
else{
print(s1, s2, record, n1 - 1, n2 - 1);
System.out.print(s1.charAt(n1 - 1));
}
}
}
2. 最长公共子串
题目
两个字符串（可能包含空格）,牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度
测试案例
输入："abcde", "abgde"
输出："ab"
代码如下
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if(n < 2){
return s;
}
StringBuilder sb = new StringBuilder(s);
sb.reverse();
String rs = sb.toString();
int max = 0, end = 0;
int[][] record = new int[n + 1][n + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(s.charAt(i - 1) == rs.charAt(j - 1)){
if((record[i][j] = record[i - 1][j - 1] + 1) > max){
max = record[i][j];
end = i;
}
}
}
}
return s.substring(end - max, end);
}
}
3. [LeetCode 5]最长回文子串
题目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
测试案例
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
代码如下
class Solution {
public String longestPalindrome(String s) {
int n = s.length(), max = 0, start = 0;
if(n < 2){
return s;
}
//边界情况，只有一个元素，只有两个元素
boolean[][] record = new int[n][n];
for(int i = 0; i < n; i++){
record[i][i] = true;
}
for(int step = 1; step < n; step++){
for(int i = 0 ; i + step < n; i++){
int j = i + step;
if(s.charAt(i) == s.charAt(j)){
if(step == 1){
record[i][j] = true;
}
else{
record[i][j] = record[i + 1][j - 1];
}
if(record[i][j] && max < step){
max = step;
start = i;
}
}
}
}
return s.substring(start, start + step + 1);
}
}
4. 最长递增子序列
题目
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin = <aK1,ak2,…,akm>，其中k1 < k2 < … < km且 aK1 < ak2 < … < akm。求最大的m值。
测试案例
arr[] = {3,1,4,1,5,9,2,6,5}的最长递增子序列长度为4。即为：1,4,5,9
思路1
- 将数组排序，得到一个新的有序数组。
- 原输入数组的最长递增子序列必定为两个数组的最长公共子序列。
思路2
- 从左至右遍历每个元素，依次记录下前 i 个元素的串中构成的长度为 1 ~ k 的递增子序列中末尾元素的最小值。
- 遍历结束后得到的最大长度就是最长递增自列的长度。
代码如下
class Solution{
int LIS(int[] nums){
int n = nums.length;
if(n == 0){
return 0;
}
int[] record = new int[n + 1];
int index = 1;
record[0] = nums[0];
for(int i = 1; i < n; i++){
int pos = Arrays.binarySearch(record, 0, index, nums[i]);
if(pos < 0){
pos = -(pos + 1);
}
if(pos == index){
index++;
}
record[pos] = nums[i];
}
return index;
}
}
思路2 只能返回最大长度。
思路3
用数组记录以当前元素为末尾的最长递增序列的长度。同时用另个一个数组记录当前元素的前继。采用动态规划算法求解。
代码如下
class Solution{
void LIS(int[] nums){
int n = nums.length;
if(n == 0){
return;
}
int[] length = new int[n + 1], pre = new int[n + 1];
length[1] = 1;
int max = 1, pos = 1;
for(int i = 2; i <= n; i++){
int temp = 1, index = 0;
for(int j = 1; j < i; j++){
if(nums[i - 1] >= nums[j - 1] && temp < length[j] + 1){
temp = length[j] + 1;
index = j;
}
if((length[i] = temp) > max){
max = temp;
pos = i;
}
pre[i] = index;
}
}
//输出路径
while(pos > 0){
System.out.print(nums[pos - 1] + " ");
pos = pre[pos];
}
}
}
返回最长递增子序列的个数
要求：递增子序列中不存在相等元素
代码如下
class Solution{
int LIS(int[] nums){
int n = nums.length;
if(n == 0){
return 0;
}
int[] length = new int[n + 1], count = new int[n + 1];
length[1] = 1;
count[1] = 1;
for(int i = 2; i <= n; i++){
int temp = 1, tcount = 1;
for(int j = 1; j < i; j++){
if(nums[i - 1] > nums[j - 1] && temp <= length[j] + 1){
if(temp == length[j] + 1){
tcount += count[j];
}
else{
temp = length[j] + 1;
tcount = count[j];
}
}
length[i] = temp;
count[i] = tcount;
}
}
int max = 1, maxcount = 0;
for(int i = 1; i <= n; i++){
if(max < length[i]){
max = length[i];
maxcount = count[i];
}
else if(max == length[i]){
maxcount += count[i];
}
}
return maxcount;
}
}
[LeetCode 97] Interleaving String
题目
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
测试案例
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
代码如下
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
if(n1 + n2 != n3){
return false;
}
if(n3 == 0){
return true;
}
if(n1 == 0){
return s2.equals(s3);
}
if(n2 == 0){
return s1.equals(s3);
}
//三者均不为0
boolean[][] record = new boolean[n1 + 1][n2 + 1];
record[0][0] = true;
for(int i = 1; i <= n1; i++){
record[i][0] = s1.substring(0, i).equals(s3.substring(0, i));
}
for(int j = 1; j <= n2; j++){
record[0][j] = s2.substring(0, j).equals(s3.substring(0, j));
}
boolean temp;
//i,j 分别表示 s1,s2的长度为i,j的前缀
for(int i = 1; i <= n1; i++){
for(int j = 1; j <= n2; j++){
temp = false;
int length = i + j;
if(s1.charAt(i - 1) == s3.charAt(length - 1)){
temp |= record[i - 1][j];
}
if(!temp && s2.charAt(j - 1) == s3.charAt(length - 1)){
temp |= record[i][j - 1];
}
record[i][j] = temp;
}
}
return record[n1][n2];
}
}