动态规划-子序列

字数统计: 5.1k字   |   阅读时长: 26分

回文子串子序列

回文子串

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

https://leetcode.cn/problems/palindromic-substrings/

如果是把字符串分割成子串，需要对这种分割方案进行逻辑判断，只能用回溯或背包

如果只是找到字符串的所有子串，可以使用循环暴力搜索

  • 循环暴力搜索
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public int countSubstrings(String s) {
        int result = 0;
        // 遍历不同起点与终点暴力搜索
        for (int i=0; i<s.length(); i++) {
            for (int j=i+1; j<=s.length(); j++) {
                String str = s.substring(i, j);
                if (this.isSame(str)) {
                    result++;
                }
            }
        }
        return result;
    }

    private boolean isSame(String s) {
        int mid = (s.length() - 1) / 2;
        for (int i=0; i<=mid; i++) {
            if (s.charAt(i) != s.charAt(s.length()-1-i)) {
                return false;
            }
        }
        return true;
    }
  • 动态规划
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    1. dp[i][j] [i, j]是否是回文子串
    2. s[i] != s[j] dp[i][j] = false
       s[i] == s[j] 
            if (i==j || j-i==1) dp[i][j] = true
            else dp[i][j] = dp[i+1][j-1]
    3. dp[i][j] = false
    4. dp[i][j] 需要依赖dp[i+1][j-1]
       i+1 在i的下方 j-1在j的左侧
       所以遍历顺序是先下后上，先左后右 
    5. "abc"
        j=0    j=1    j=2
    i=0 true   false  false
    i=1 flase  true   false  
    i=2 false  false  true
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
public int countSubstrings(String s) {
    int length = s.length();
    boolean[][] dp = new boolean[length][length];
    for (int i=length-1; i>=0; i--) {
        for (int j=i; j<length; j++) {
            // 如果首尾字符相等，根据下标差值分情况判断
            if (s.charAt(i) == s.charAt(j)) {
                // 下标差值小于等于1，直接为true
                if (j-i <= 1) {
                    dp[i][j] = true;
                }
                // 大于1，需要根据dp[i+1][j-1]判断， 首尾内部的字符串
                else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            // 首尾字符不相等，肯定不是回文
            else {
                dp[i][j] = false;
            }
        }
    }

    int result = 0;
    for (boolean[] row : dp) {
        for (boolean value : row) {
            if (value) {
                result++;
            }
        }
    }
    return result;
}

最长回文子序列

https://leetcode.cn/problems/longest-palindromic-subsequence/

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

  • 动态规划
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    1. dp[i][j] [i, j]区间子序列的最大长度
    2. s[i] == s[j] dp[i][j] = dp[i+1][j-1] + 2
       s[i] != s[j] dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
    3. i==j 时，dp[i][j] 不能使用dp[i+1][j-1] + 2递推得到，必须单独初始化为1 其他初始化为0
    4. dp[i][j] 依赖 dp[i+1][j-1] 左下方 dp[i+1][j]下方 dp[i][j-1]左侧
       从下到上，从左到右的计算
    5. s = "bbbab"
        b   b   b   a   b
    b   1   2   3   3   4
    b       1   2   2   3
    b           1   1   3
    a               1   1
    b                   1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int longestPalindromeSubseq(String s) {
    int length = s.length();
    int[][] dp = new int[length][length];
    // 初始化主对角线
    for (int i=0; i<length; i++) {
        dp[i][i] = 1;
    }
    for (int i=length-1; i>=0; i--) {
        // j=i+1 保证至少两个字符串，才能使用dp[i+1][j-1]+2
        for (int j=i+1; j<length; j++) {
            // 首尾相等，数量+2
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else { // 首尾不等 取最大的
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][length-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
    private int maxLength;
        public int longestPalindromeSubseq(String s) {
            this.backtrack(s, 0, "");
            return this.maxLength;
        }

        // 子序列问题，与子集问题一致，组合问题的升级版
        // 组合问题只收集叶子节点，子集问题收集所有节点
        // 子集问题与子序列问题的回溯参数与返回值一致，添加path参数自动回溯
        private void backtrack(String s, int startIndex, String path) {
            // 保存结果
            if (this.isSame(path)) {
                this.maxLength = Math.max(this.maxLength, path.length());
            }
            // 利用for循环条件结束递归
            for (int i=startIndex; i<s.length(); i++) {
                // 从下一个字符开始遍历
                backtrack(s, i+1, path+s.charAt(i));
            }
        }

        private boolean isSame(String s) {
            if (s.length() == 0) {
                return false;
            }
            int mid = (s.length() - 1) / 2;
            for (int i=0; i<=mid; i++) {
                if (s.charAt(i) != s.charAt(s.length()-1-i)) {
                    return false;
                }
            }
            return true;
        }

最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/

  • 暴力 超时

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public String longestPalindrome(String s) {
        String result = "";
        for (int i=0; i<s.length(); i++) {
            for (int j=i+1; j<=s.length(); j++) {
                String str = s.substring(i, j);
                if (this.isSame(str) && str.length()>result.length()) {
                    result = str;
                }
            }
        }
        return result;
    }

    private boolean isSame(String s) {
        int mid = (s.length() - 1) / 2;
        for (int i=0; i<=mid; i++) {
            if (s.charAt(i) != s.charAt(s.length()-1-i)) {
                return false;
            }
        }
        return true;
    }

  • 动态规划

    1
    2
    3
    4
    5
    dp[i][j] [i, j]是否是回文子串
    s[i] != s[j] dp[i][j] = false
    s[i] == s[j] 
        j-i<=1 true
        j-i>1 dp[i+1][j-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
public String longestPalindrome(String s) {
    int length = s.length();
    boolean[][] dp = new boolean[length][length];
    for (int i=length-1; i>=0; i--) {
        for (int j=i; j<length; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j-i <= 1) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i+1][j-1];
                }
            } else {
                dp[i][j] = false;
            }
        }
    }
    // 遍历找最长的
    int start = 0, end = 0;
    for (int i=0; i<length; i++) {
        for (int j=i+1; j<length; j++) {
            if (dp[i][j] && j-i > end-start) {
                start = i;
                end = j;
            }
        }
    }
    return s.substring(start, end+1);
}

编辑距离

判断子序列

https://leetcode.cn/problems/is-subsequence/

  • 回溯搜索 超时
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    private Set<String> set = new HashSet<>();
    public boolean isSubsequence(String s, String t) {
        this.backtrack(t, 0, "");
        return this.set.contains(s);
    }

    // 不同的深度含有的元素个数不同，可以看到，不同个数的元素都包含进来了，找到了所有的子集，即子序列
    private void backtrack(String s, int startIndex, String path) {
        this.set.add(path);
        for (int i=startIndex; i<s.length(); i++) {
            backtrack(s, i+1, path+s.charAt(i));
        }
    }
  • dp
    下面的递推公式是为了删除操作，其实可以当作公共子序列长度问题做
1
2
3
4
5
6
7
8
9
10
11
12
13
1. dp[i][j] 含义以s[i-1]结尾的字符串 与 以 t[j-1]结尾的字符串含有的相同子序列长度
感觉这个定义不准确，比如下面的例子i=c j=d时是零，但是应该有两个相同的，只能说中间的状态意义是不对的，但是最终的状态 在含有全部子序列的情况下意义是对的
2. s[i-1] == t[j-1] dp[i][j] = dp[i-1][j-1] + 1
   s[i-1] != t[j-1] dp[i]][j] = dp[i][j-1] // 删除t[j-1]
3. dp[0][j]=0 s为空 相同子序列为空
   dp[i][0]=0 t为空 相同子序列为空
4. dp[i][j] 依赖左侧元素 以及左上方元素 从左向右 从上至下
5. s = "abc", t = "ahbgdc"
        a   h   b   g   d   c
    0   0   0   0   0   0   0
a   0   1   1   1   1   1   1
b   0   0   0   2   2   2   2
c   0   0   0   0   0   0   3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isSubsequence(String s, String t) {
    int lengthS = s.length();
    int lengthT = t.length();
    int[][] dp = new int[lengthS+1][lengthT+1];
    for (int i=1; i<=lengthS; i++) {
        for (int j=1; j<=lengthT; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = dp[i][j-1];
            }
        }
    }
    
    return dp[lengthS][lengthT] == lengthS;
}
  • 纠正dp的含义
    上面的方法递推公式只删除 t的字符，导致有些时候dp含义无效，如果递推公式改为

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) 两个都可能删除，dp意义就正确了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isSubsequence(String s, String t) {
    int length1 = s.length();
    int length2 = t.length();

    int[][] dp = new int[length1+1][length2+1];
    for (int i=1; i<=length1; i++) {
        for (int j=1; j<=length2; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);                
            }
        }
    }
    return dp[length1][length2] == s.length();
}
  • 双指针，更好理解
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public boolean isSubsequence(String s, String t) {
        // 双指针，遍历s，在t中逐个寻找
        int indexS=0, indexT=0;
        while (indexS<s.length() && indexT<t.length()) {
            if (s.charAt(indexS) == t.charAt(indexT)) {
                indexS++;
                indexT++;
            } else {
                indexT++;
            }
        }
        return indexS == s.length();
    }

不同的子序列

https://leetcode.cn/problems/distinct-subsequences/

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
1. dp[i][j] 以s[i-1]结尾的字符串的子串中 t的[0, j-1]字符串出现的次数
2. s[i-1] == t[j-1]
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 不太理解dp[i-1][j]的含义
        bagg 与 bag 以第二个g结尾的子序列，等于bag的个数 以第一个g为结尾的子序列，等于bag的个数，两种情况相加
   s[i-1] != t[j-1]
        dp[i][j] = dp[i-1][j] 匹配不上，就不用s[i-1]匹配了，仍然使用s[i-2]结尾的子序列等于的个数

    再来看看s[i-1] == t[j-1]时，
    分成了两部分，s[i-2]结尾的子序列等于t[0, j-1]的个数，这部分并不考虑匹配上了
    bagt bag    t与g没有匹配上，但是bag的子序列中仍然有bag
    bagg bag    第二个g与g匹配上了，除了不包括第二个g的bag子序列中有bag次数，
    还要包括bag子序列中等于ba的次数，因为些相等的子序列再添加一个新匹配的g，就是新的子序列
3. dp[0][0] = 1 空串s子序列中等于空串t的个数
   dp[0][j] = 0 空串s子序列等于非空字符t的个数，肯定为0
   dp[i][0] = 1 非空串s子序列等于空串t的个数，肯定为1，即非空串s的空子序列
4. dp[i][j] 依赖上方与左上方的元素 左至右 上至下
5. "babgbag", t = "bag"
        b   a   g
    1   0   0   0
b   1   1   0   0
a   1   1   1   0
b   1   2   1   0
g   1   2   1   1
b   1   3   1   1
a   1   3   4   1
g   1   3   4   5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int numDistinct(String s, String t) {
    int lengthS = s.length();
    int lengthT = t.length();

    int[][] dp = new int[lengthS+1][lengthT+1];
    for (int i=0; i<=lengthS; i++) {
        dp[i][0] = 1;
    }

    for (int i=1; i<=lengthS; i++) {
        // 添加了小优化，j<=i，因为j>i时，t[0, j-1]比s[0, i-1]长，s的子序列中不包括t
        for (int j=1; j<=lengthT && j<=i; j++) {
            if (s.charAt(i-1) == t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; 
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[lengthS][lengthT];
}

两个字符的删除操作

https://leetcode.cn/problems/delete-operation-for-two-strings/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1. dp[i][j] word1[0, i-1] word2[0, j-1] 相等时需要的最少删除次数
2. word1[i-1] == word2[j-1] 相等时与之前的删除次数相等
    dp[i][j] = dp[i-1][j-1]
   word1[i-1] != word2[j-1] 
    dp[i][j] = Math.min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 2)
3. dp[0][0] = 0
   dp[0][j] = j 删除j次变成空串
   dp[i][0] = i 删除i次变成空串
4. 左至右 上至下
5. word1 = "sea", word2 = "eat"
        e   a   t
    0   1   2   3
s   1   2   3   4
e   2   1   2   3
a   3   2   1   2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    int[][] dp = new int[n1+1][n2+2];
    for (int i=1; i<=n1; i++) {
        dp[i][0] = i;
    }
    for (int j=1; j<=n2; j++) {
        dp[0][j] = j;
    }

    for (int i=1; i<=n1; i++) {
        for (int j=1; j<=n2; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i][j-1] + 1, Math.min(dp[i-1][j] + 1, dp[i-1][j-1] + 2));
            }
        }
    }
    return dp[n1][n2];
}

编辑距离

https://leetcode.cn/problems/edit-distance/

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
1. dp[i][j] word1[0, i-1] 与 子串word2[0, j-1]最短的编辑距离
2. word1[i-1] == word2[j-1]
    dp[i][j] = dp[i-1][j-1] 不用操作
   
   word1[i-1] != word2[j-1]
        1. 删除word1末尾字符 dp[i-1][j] 
        以abbd 与 abc为例
        d 与 c不一样，考虑使用删除d的操作，使abbd 与 abc相同
        总体操作可以分为两部分，第一部分 使abb与abc相同，第二部分 删除末尾的d
        dp[i][j] = dp[i-1][j] + 1 
        
        2. 在word1末尾插入字符
        以abb 与 abcd为例
        b与d不一样，考虑使用插入d字符的操作，使abb与abcd相同
        同样分为两部分，第一部分， abb 与 abc相同，第二部分 末尾添加d
        (只是记录一下会添加，并不是真的添加，不然后续字符的索引就变了)
        dp[i][j] = dp[i][j-1] + 1
        
        3. 替换word1末尾字符
        acd 与 abc
        第一部分 ac 与 ab相同 第二部分替换d为c
        dp[i][j] = dp[i-1][j-1] + 1
3. 初始化 
    dp[0][0] = 0
    dp[i][0] = i
    dp[0][j] = j
4. dp[i][j] 依赖左侧 dp[i][j-1] 上侧dp[i-1][j] 左上侧dp[i-1][j-1]
所以左至右 上至下遍历
5. "horse", word2 = "ros"
        r   o   s
    0   1   2   3
h   1   1   2   3
o   2   2   1   2
r   3   2   2   2
s   4   3   3   2
e   5   4   4   3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minDistance(String word1, String word2) {
    int n1 = word1.length();
    int n2 = word2.length();
    int[][] dp = new int[n1+1][n2+1];
    for (int i=1; i<=n1; i++) {
        dp[i][0] = i;
    }
    for (int j=1; j<=n2; j++) {
        dp[0][j] = j;
    }
    for (int i=1; i<=n1; i++) {
        for (int j=1; j<=n2; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = Math.min(dp[i-1][j] + 1, Math.min(dp[i][j-1] + 1, dp[i-1][j-1] + 1));
            }
        }
    }
    return dp[n1][n2];
}

子序列(不连续)

最长上升子序列

https://leetcode.cn/problems/longest-increasing-subsequence/

注意dp数组的含义，必须以nums[i]结尾，也就是序列中必须包含nums[i]，且以它结尾

1
2
3
4
5
6
7
8
1. dp[i] 以nums[i]结尾的子序列最长长度
2. if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j]+1)
3. dp[i] = 1
4. 前至后
5. [10, 9,  2,  5,  3,  7,  101,  18]

    1   1   1   2   2   3   4      1   
返回dp中最大的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLIS(int[] nums) {
    int length = nums.length;
    int[] dp = new int[length];
    for (int i=0; i<length; i++) {
        dp[i] = 1;
    }
    int result = 1;
    for (int i=1; i<length; i++) {
        for (int j=0; j<i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        if (dp[i] > result) {
            result = dp[i];
        }
    }
    return result;
}

最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1. dp[i][j] text1[0, i-1] text2[0, j-1] 最长公共子序列的长度，没有限制必须以text1[i-1] text2[j-1]结尾
2. text1[i-1] == text2[j-1]
    dp[i][j] = dp[i-1][j-1] + 1;
text1[i-1] != text2[j-1]
    text1 = abc text2 = abcd
    c != d
    就看 ab abc 与 abc abc 哪个子序列长

    text1 = abcd text2 = abc
    c != d
    就看 abc abc 与 abcd ab 哪个子序列长
    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]) 
3. dp[0][0] = 0 dp[i][0] = 0 dp[0][j] = 0
4. 左右上下
5. "abcde", text2 = "ace" 
        a   c   e
    0   0   0   0
a   0   1   1   1
b   0   1   1   1
c   0   1   2   2
d   0   1   2   2
e   0   1   2   3
根据含义返回dp末尾元素即可  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int longestCommonSubsequence(String text1, String text2) {
    int length1 = text1.length();
    int length2 = text2.length();

    int[][] dp = new int[length1+1][length2+1];
    for (int i=1; i<=length1; i++) {
        for (int j=1; j<=length2; j++) {
            if (text1.charAt(i-1) == text2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);                
            }
        }
    }
    return dp[length1][length2];
}

不相交的线

https://leetcode.cn/problems/uncrossed-lines/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
其实就是求最长公共子序列的长度
1. dp[i][j] nums1[0, i-1] nums2[0, j-1]最长公共子序列的长度
2. nums1[i-1] == nums2[j-1]
    dp[i][j] = dp[i-1][j-1]
   nums1[i-1] != nums2[j-1]
    dp[i-1] = Math.max(dp[i-1][j], dp[i][j-1])
3. dp[0][0] = 0 dp[i][0] = 0 dp[0][j] = 0
4. 左至右 上至下
5. nums1 = [1,4,2], nums2 = [1,2,4]
        1   2   4
    0   0   0   0
1   0   1   1   1
4   0   1   1   2
2   0   1   2   2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxUncrossedLines(int[] nums1, int[] nums2) {
    int length1 = nums1.length;
    int length2 = nums2.length;
    int[][] dp = new int[length1+1][length2+1];
    for (int i=1; i<=length1; i++) {
        for (int j=1; j<=length2; j++) {
            if (nums1[i-1] == nums2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[length1][length2];
}

子序列(连续)

最长连续递增子序列

https://leetcode.cn/problems/longest-continuous-increasing-subsequence/

  • dp
    注意dp数组的含义，必须以nums[i]结尾，也就是序列中必须包含nums[i]，且以它结尾
1
2
3
4
5
6
1. dp[i] 以i为结尾的最长连续子序列长度
2. if (nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1
3. dp[i] = 1
4. 前后
5. [1,  3,  5,  4,  7]
    1   2   3   1   2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findLengthOfLCIS(int[] nums) {
    int length = nums.length;
    int[] dp = new int[length];
    
    for (int i=0; i<length; i++) {
        dp[i] = 1;
    }
    int result = 1;
    for (int i=1; i<length; i++) {
        if (nums[i] > nums[i-1]) {
            dp[i] = dp[i-1] + 1;
        }
        result = Math.max(dp[i], result);
    }
    return result;
}
  • 普通遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int findLengthOfLCIS(int[] nums) {
        int length = nums.length;
        int result = 1;
        int temp = 1;
        for (int i=1; i<length; i++) {
            if (nums[i] > nums[i-1]) {
                temp++;
            } else {
                result = Math.max(temp, result);
                temp = 1;
            }
        }
        return Math.max(temp, result);
    }
  • 如果需要输出最长的子序列
    使用left 与 right 保存临时长度与最初的长度
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
public int findLengthOfLCIS(int[] nums) {
    int length = nums.length;
    int tempLeft = 0;
    int tempRight = 0;
    int left = 0;
    int right = 0;
    for (int i=1; i<length; i++) {
        if (nums[i] > nums[i-1]) {
            tempRight++;
        } else {
            if (tempRight-tempLeft > right-left) {
                right = tempRight;
                left = tempLeft;
            }
            tempLeft = i;
            tempRight = i;
        }
    }
    if (tempRight-tempLeft > right-left) {
        right = tempRight;
        left = tempLeft;
    }
    System.out.println(Arrays.toString(Arrays.copyOfRange(nums, left, right+1)));
    return right - left + 1;
}

最长重复子数组

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

包括nums1[i-1]，且以nums1[i-1]结尾的子数组

包括nums2[j-1]，且以nums2[j-1]结尾的子数组

这两个子数组如果相同，dp[i][j]就是相同子数组最大的长度

如果不相同，就是dp[i][j]就是0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
连续数组
1. dp[i][j] 包括nums1[i-1]，且以nums1[i-1]结尾的子数组
            包括nums2[j-1]，且以nums2[j-1]结尾的子数组
            这两个子数组如果相同，dp[i][j]就是相同子数组最大的长度
            如果不相同，就是dp[i][j]就是0
2. if (nums[i-1] == nums[j-1]) dp[i][j] = dp[i-1][j-1] + 1
3. dp[0][0] = 0 dp[i][0] = 0 dp[0][j] = 0
4. 左至右 上至下
5. [1,2,3,2,1] [3,2,1,4,7]
        3   2   1   4   7
    0   0   0   0   0   0
1   0   0   0   1   0   0
2   0   0   1   0   0   0
3   0   1   0   0   0   0
2   0   0   2   0   0   0
1   0   0   0   3   0   0
注意dp[i][j]的含义，限制了子数组必须以nums1[i-1] 与 nums2[j-1]结尾，所以
dp[n1][n2]不一定是最大的，需要遍历，找最大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findLength(int[] nums1, int[] nums2) {
    int n1 = nums1.length;
    int n2 = nums2.length;
    int[][] dp = new int[n1+1][n2+1];
    int result = 0;
    for (int i=1; i<=n1; i++) {
        for (int j=1; j<=n2; j++) {
            if (nums1[i-1] == nums2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                result = Math.max(result, dp[i][j]);
            }
        }
    }
    return result;
}

最大子数组和

https://leetcode.cn/problems/maximum-subarray/

  • dp
    1
    2
    3
    4
    5
    6
    7
    8
    1. dp[i] 以nums[i] 结尾的连续数组，最大和
    2. dp[i] = Math.max(dp[i-1]+nums[i], nums[i])
    nums[i] 结尾子数组的和，只有两种情况，包括前面的，还有不包括前面的
    3. dp[0] = nums[0]
    4. 左右
    5. [-2, 1,  -3, 4,  -1, 2,  1,  -5, 4]
        -2  1   -2  4   3   5   6   1   5
        遍历dp返回最大
1
2
3
4
5
6
7
8
9
10
11
public int maxSubArray(int[] nums) {
    int length = nums.length;
    int[] dp = new int[length];
    dp[0] = nums[0];
    int result = dp[0];
    for (int i=1; i<length; i++) {
        dp[i] = Math.max(nums[i], nums[i]+dp[i-1]);
        result = Math.max(result, dp[i]);
    }
    return result;
}
  • 贪心
    图片

自己写的屎代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 如果nums[i] 加上的前面连续序列和是负数，肯定还不如不加，
// 那么此时就重新从nums[i]重新计算子序列和
public int maxSubArray(int[] nums) {
    int result = nums[0];
    int sum = nums[0];
    for (int i=1; i<nums.length; i++) {
        result = Math.max(result, sum);
        if (sum < 0) {
            sum = 0;
        }
        sum += nums[i];
    }
    result = Math.max(result, sum);
    return result;
}

别人的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 如果nums[i] 加上的前面连续序列和是负数，肯定还不如不加，
// 那么此时就重新从nums[i]重新计算子序列和
public int maxSubArray(int[] nums) {
    int result = Integer.MIN_VALUE;
    int sum = 0;
    for (int num : nums) {
        // 累加
        sum += num;
        // 因为后续会改变sum的值，所引先保存以下sum
        result = Math.max(result, sum);
        // 如果sum是负数在本次循环就置零
        sum = Math.max(sum, 0);

    }
    return result;
}
赏

谢谢你请我喝杯可乐

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北科大计算机在读<br><br>爱好编程<br><br>热爱技术<br><br>喜欢折腾