【Leetcode】计算最长系列（动态规划）

文章目录

• • • 计算最长系列（动态规划）
    • • 594. 最长和谐子序列
      • 674. 最长连续递增序列
      • 300. 最长递增子序列
      • 1143. 最长公共子序列
      • 516. 最长回文子序列
      • 1218. 最长定差子序列
      • 718. 最长重复子数组
      • 978. 最长湍流子数组

计算最长系列（动态规划） 594. 最长和谐子序列

1.题目描述

leetcode链接：594. 最长和谐子序列

2.思路分析

方法一：排序+双指针

首先，堆数组进行从小到大排序，然后一个指针一次遍历，另一个指针判断之间的差值是否大于1。最大的长度就是两个指针之间的距离。

方法二：哈希计数

统计相邻两个数出现的次数的最大值。先统计每个数字出现的次数，然后判断相邻的下一个数字是否存在，存在则相加两个数出现的次数，更新最大值。

3.参考代码

方法一：排序+双指针

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0, j = 0; i < nums.length; i++) {
            while (nums[i] - nums[j] > 1) {
                j++;
            }
            if (nums[i] - nums[j] == 1) {
                res = Math.max(res, i - j + 1);
            }
        }
        return res;
    }
}

方法二：哈希计数

class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int key : map.keySet()) {
            int val = map.get(key);
            if (map.containsKey(key + 1)) {
                res = Math.max(res, val + map.get(key + 1));
            }
        }
        return res;
    }
}

674. 最长连续递增序列

1.题目描述

leetcode链接：674. 最长连续递增序列

2.思路分析

方法一：模拟判断

模拟，判断如果后一个元素大于前一个元素，则j++，否则记录最大值，j置为1。注意：最后再更新一下最大值，防止连续递增的情况。

方法二：动态规划

dp[i] 表示以i结尾的最大连续递增子序列长度。

3.参考代码

方法一：模拟判断

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int res = 1, j = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                j++;
            } else {
                res = Math.max(res, j);
                j = 1;
            }
        }
        res = Math.max(res, j);  // 连续递增
        return res;
    }
}

方法二：动态规划

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int res = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

300. 最长递增子序列

1.题目描述

leetcode链接：300. 最长递增子序列

2.思路分析

与上一题不同的地方在于最长连续递增序列是相邻的的递增序列，而最长递增子序列不要求相邻，是子序列。

方法一：动态规划

上一题的判断条件是，当前元素比上一个元素大，则dp[i] = dp[i - 1] + 1,与上一题不同的是当前元素比之前的元素大，dp[i] = Math.max(dp[i], dp[j] + 1);

方法二：贪心+二分查找

每次选择下一个递增元素的时候，都选择更小的结尾。使用二分查找，去找到这个更小的。

比如 {1, 5, 3, 4, 7} 5和3之间选择3作为当前递增序列的结尾元素。

dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数。

对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:

1. num > dp[res], 表示num比所有已知递增序列的尾数都大, 将num添加入dp数组尾部, 并将最长递增序列长度res加1

2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]

3.参考代码

方法一：动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 动态规划
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

方法二：贪心+二分查找

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int res = 0;
        for (int num : nums) {
            int i = 0, j = res;
            while (i < j) {
                int mid = (j - i) / 2 + i;
                if (dp[mid] < num) {
                    i = mid + 1;
                } else {
                    j = mid;
                }
            }
            dp[i] = num;
            if (res == j) res++;
        }
        return res;
    }
}

1143. 最长公共子序列

1.题目描述

leetcode链接：1143. 最长公共子序列

2.思路分析

动态规划解决，dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

转移方程：主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

1. 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

2. 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

**初始化：**先看看dp[i][0]应该是多少呢？

test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;

同理dp[0][j]也是0。

3.参考代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

516. 最长回文子序列

1.题目描述

leetcode链接：516. 最长回文子序列

2.思路分析

回文子序列与回文子串不同，回文子串是要连续的，回文子序列可不是连续的！ 回文子串，回文子序列都是动态规划经典题目。

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

转移方程：

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。

如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

初始化：

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。

所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

遍历顺序：

可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]，

也就是从矩阵的角度来说，dp[i][j] 下一行的数据。 所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。

3.参考代码

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; i--) {  // 从后往前
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                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][n - 1];
    }
}

1218. 最长定差子序列

1.题目描述

leetcode链接：1218. 最长定差子序列

2.思路分析

3.参考代码

718. 最长重复子数组

1.题目描述

leetcode链接：718. 最长重复子数组

2.思路分析

3.参考代码

978. 最长湍流子数组

1.题目描述

leetcode链接：978. 最长湍流子数组

2.思路分析

3.参考代码

参考：

• 【LeetCode】（动态规划ி）力扣之最