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

冷不防 2023-01-11 12:00 113阅读 0赞

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

### 文章目录 ###

*   *  【LeetCode】（动态规划ி）力扣之最
     *   *  最长和谐子序列★
         *  最长连续递增序列★
         *  最长递增子序列（LIS）★★
         *  最长公共子序列（LCS）★★
         *  最长回文子序列★★
         *  最长定差子序列★★
         *  最长重复子数组★★
         *  最长湍流子数组★★

--------------------

### 最长和谐子序列★ ###

[LeetCode 594. 最长和谐子序列][LeetCode 594.]

【**题目**】和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

【**示例**】

输入: [1,3,2,2,5,2,3,7]
    输出: 5
    原因: 最长的和谐数组是：[3,2,2,2,3].

【**解题思路**】

**方法一**：HashMap

使用字典保存每个数的个数，若当前数字为`x`:

*  若字典中存在`x-1`，结果`res`取x与`x-1`个数和与`res`中的较大值
 *  若字典中存在`x+1`，结果`res`取x与`x+1`个数和与`res`中的较大值

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

**方法二**：排序+（“双指针”）

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

--------------------

### 最长连续递增序列★ ###

[LeetCode 674. 最长连续递增序列][LeetCode 674.]

【**题目**】给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 `l` 和 `r`（`l < r`）确定，如果对于每个 `l <= i < r`，都有 `nums[i] < nums[i + 1]` ，那么子序列 `[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]` 就是连续递增子序列。

【**示例**】

输入：nums = [1,3,5,4,7]
    输出：3
    解释：最长连续递增序列是 [1,3,5], 长度为3。
    尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

【**解题思路**】

class Solution {
        
        public int findLengthOfLCIS(int[] nums) {
        
            if(nums == null || nums.length == 0){
        
                return 0;
            }
            int max = 1, t = 1;
            for(int i = 1; i < nums.length; i++){
        
                if(nums[i] > nums[i - 1]){
        
                    t++;
                }else{
        
                    max = Math.max(max, t);
                    t = 1;
                }
            }
            //避免遗漏结尾
            max = Math.max(max, t);
            return max;
        }
    }

--------------------

### 最长递增子序列（LIS）★★ ###

[LeetCode 300. 最长递增子序列][LeetCode 300.]

【**题目**】给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。

【**示例**】

输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

【**解题思路**】

**方法一**：动态规划

时间复杂度`O(n²)`

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

**方法二**：动态规划+二分查找

时间复杂度`O(nlogn)`

维护一个升序排列的列表`list`，若当前值大于列表尾元素，直接加入；若小于等于最大元素，使用二分查找寻找替换位置并替换。最后返回列表`list`的大小即可。

对于数组`nums = {10, 9, 2, 5, 3, 7, 101, 18}`列表相应内容如下：

nums = {
        10, 9, 2, 5, 3, 7, 101, 18}
    -----------------------------------------------------
    nums[0] = 10   list = [10]            | 列表为空，直接加入
    nums[1] = 9    list = [9]             | 替换10
    nums[2] = 2    list = [2]             | 替换9
    nums[3] = 5    list = [2, 5]          | 大于2，直接加入
    nums[4] = 3    list = [2, 3]          | 替换5
    nums[5] = 7    list = [2, 3, 7]       | 大于3，直接加入
    nums[6] = 101  list = [2, 3, 7, 101]  | 大于7，直接加入
    nums[7] = 18   list = [2, 3, 7, 18]   | 替换101

二分查找返回的位置为第一个等于或者大于它的值

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            int n = nums.length;
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++) {
        
                if(list.size() == 0 || nums[i] > list.get(list.size() - 1)) {
        
                    list.add(nums[i]);
                }else {
        
                    int l = 0, r = list.size() - 1;
                    //返回第一个等于或者大于它的下标
                    while(l <= r) {
        
                        int mid = l + ((r - l) >> 1);
                        if(nums[i] > list.get(mid)) {
        
                            l = mid + 1;
                        }else if(nums[i] < list.get(mid)){
        
                            r = mid - 1;
                        }else {
        
                            l = mid;
                            break;
                        }
                    }
                    list.set(l, nums[i]);
                }
            }
            return list.size();
        }
    }

调用Collections的二分查找版

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            int n = nums.length;
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++) {
        
                if(list.size() == 0 || nums[i] > list.get(list.size() - 1)) {
        
                    list.add(nums[i]);
                }else {
        
                    //返回下标的结果有兴趣的可以自己输出看看（特别是不存在的元素）
                    int index = Collections.binarySearch(list, nums[i]);
                    if(index < 0) {
        
                        list.set(-index - 1 , nums[i]);
                    }
                }
            }
            return list.size();
        }
    }

--------------------

### 最长公共子序列（LCS）★★ ###

[LeetCode 1143. 最长公共子序列][LeetCode 1143.]

【**题目**】给定两个字符串 `text1` 和 `text2`，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。  
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

**提示:**

*  `1 <= text1.length <= 1000`
 *  `1 <= text2.length <= 1000`
 *  输入的字符串只含有小写英文字符。

【**示例**】

输入：text1 = "abcde", text2 = "ace" 
    输出：3  
    解释：最长公共子序列是 "ace"，它的长度为 3。

【**解题思路**】

`dp[i][j]`的含义是`text1[0...i]`与`text2[0...j]`的最长公共子序列的长度。从左到右，从上到下计算矩阵`dp`

详细过程如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

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++) {
        
                for(int j = 0; j < n; j++) {
        
                    if(text1.charAt(i) == text2.charAt(j)) {
        
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                    }else {
        
                        dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                    }
                }
            }
            return dp[m][n];
        }
    }

空间优化使用一维数组

class Solution {
        
        public int longestCommonSubsequence(String text1, String text2) {
        
            int m = text1.length(), n = text2.length();
            int[] dp = new int[n + 1];
            for(int i = 0; i < m; i++) {
        
                int preLeftTop = 0;
                for(int j = 0; j < n; j++) {
        
                    int curLeftTop = dp[j + 1];
                    if(text1.charAt(i) == text2.charAt(j)) {
        
                        dp[j + 1] = preLeftTop + 1;
                    }else {
        
                        dp[j + 1] = Math.max(dp[j], dp[j + 1]);
                    }
                    preLeftTop = curLeftTop;
                }
            }
            return dp[n];
        }
    }

--------------------

### 最长回文子序列★★ ###

[LeetCode 516. 最长回文子序列][LeetCode 516.]

【**题目**】给定一个字符串 `s` ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 `s` 的最大长度为 `1000` 。

**提示：**

*  `1 <= s.length <= 1000`
 *  `s` 只包含小写英文字母

【**示例**】

输入："bbbab"
    输出：4
    解释：一个可能的最长回文子序列为 "bbbb"。

【**解题思路**】

转化为求字符串`s`与`s`的逆序列的最长公共子序列

class Solution {
        
        public int longestPalindromeSubseq(String s) {
        
            int n = s.length();
            int[][] dp = new int[n + 1][n + 1];
            for(int i = 0; i < n; i++) {
        
                for(int j = n - 1; j >= 0; j--) {
        
                    if(s.charAt(i) == s.charAt(j)) {
        
                        dp[i + 1][n - j] = dp[i][n - j - 1] + 1;
                    }else {
        
                        dp[i + 1][n - j] = Math.max(dp[i][n - j], dp[i + 1][n - j - 1]);
                    }
                }
            }
            return dp[n][n];
        }
    }

--------------------

### 最长定差子序列★★ ###

[LeetCode 1218. 最长定差子序列][LeetCode 1218.]

【**题目**】

给你一个整数数组 `arr` 和一个整数 `difference`，请你找出并返回 `arr` 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 `difference` 。

**提示：**

*  `1 <= arr.length <= 10^5`
 *  `-10^4 <= arr[i], difference <= 10^4`

【**示例**】

输入：arr = [1,2,3,4], difference = 1
    输出：4
    解释：最长的等差子序列是 [1,2,3,4]。

【**解题思路**】

使用`map`保存已经计算过的定差子序列值，`res`取`dp[i]`最大值即可。

class Solution {
        
        public int longestSubsequence(int[] arr, int difference) {
        
            int n = arr.length, res = 0;
            int[] dp = new int[n];
            Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < n; i++) {
        
                dp[i] = 1;
                if(map.containsKey(arr[i] - difference)) {
        
                    dp[i] = map.get(arr[i] - difference) + 1;
                }
                map.put(arr[i], dp[i]);
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }

--------------------

### 最长重复子数组★★ ###

[LeetCode 718. 最长重复子数组][LeetCode 718.]

【**题目**】给两个整数数组 `A` 和 `B` ，返回两个数组中公共的、长度最长的子数组的长度。

**提示：**

*  `1 <= len(A), len(B) <= 1000`
 *  `0 <= A[i], B[i] < 100`

【**示例**】

输入：
    A: [1,2,3,2,1]
    B: [3,2,1,4,7]
    输出：3
    解释：
    长度最长的公共子数组是 [3, 2, 1] 。

【**解题思路**】

注意子数组要求是连续的，而子序列可以不连续。同最长公共子序列类似，只是动态规划转移方程只在数组元素取相同值时更新，此时使用一个变量`res`取最大值即可。图解如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

class Solution {
        
        public int findLength(int[] A, int[] B) {
        
            int res = 0;
            int[][] dp = new int[A.length + 1][B.length + 1];
            for(int i =0; i < A.length; i++) {
        
                for(int j = 0; j < B.length; j++) {
        
                    if(A[i] == B[j]) {
        
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                        res = Math.max(res, dp[i + 1][j + 1]);
                    }
                }
            }
            return res;
        }
    }

--------------------

### 最长湍流子数组★★ ###

[LeetCode 978. 最长湍流子数组][LeetCode 978.]

【**题目**】当 `A` 的子数组 `A[i], A[i+1], ..., A[j]` 满足下列条件时，我们称其为湍流子数组：

*  若 `i <= k < j`，当 `k` 为奇数时， `A[k] > A[k+1]`，且当 `k` 为偶数时，`A[k] < A[k+1]`；
 *  或 若 `i <= k < j`，当 `k` 为偶数时，`A[k] > A[k+1]` ，且当 `k` 为奇数时， `A[k] < A[k+1]`。

也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。

返回 `A` 的最大湍流子数组的长度。

**提示：**

1.  `1 <= A.length <= 40000`
2.  `0 <= A[i] <= 10^9`

【**示例**】

输入：[9,4,2,10,7,8,8,1,9]
    输出：5
    解释：(A[1] > A[2] < A[3] > A[4] < A[5])

【**解题思路**】

**方法一**：

使用一个数组`f[]`标记`arr[i] - arr[i +1]`符号，

*  若小于0，记为-1
 *  若大于0，记为1
 *  若等于0，记为0

答案就是求连续 `···， 1， -1， 1， -1，···`的最大长度

示例转化如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]

class Solution {
        
        public int maxTurbulenceSize(int[] arr) {
        
            if(arr.length < 2) return arr.length;
            int n = arr.length;
            int[] f = new int[n - 1];
            for(int i = 0; i < n - 1; i++) {
        
                if(arr[i] < arr[i + 1]) {
        
                    f[i] = -1;
                }else if(arr[i] == arr[i + 1]){
        
                    f[i] = 0;
                }else {
        
                    f[i] = 1;
                }
            }
            int res = 1;
            int count = f[0] == 0 ? 0 : 1;
            for(int i = 0; i < n - 1; i++) {
        
                if(i > 0 && f[i] != 0 && f[i] != f[i - 1]) {
        
                    count++;
                }else {
        
                    res = Math.max(res, count + 1);
                    count = f[i] == 0 ? 0 : 1;
                }
            }
            return Math.max(res, count + 1);
        }
    }

**方法二**：

使用两个变量`up`和`down`分别表示上升和下降序列，初始化均为1，相应变量更新见代码

arr = [9,4,2,10,7,8,8,1,9]
    arr[1] = 4   up = 1  down = 2  res = 2
    arr[2] = 2   up = 1  down = 2  res = 2
    arr[3] = 10  up = 3  down = 1  res = 3
    arr[4] = 7   up = 1  down = 4  res = 4
    arr[5] = 8   up = 5  down = 1  res = 5
    arr[6] = 8   up = 1  down = 1  res = 5
    arr[7] = 1   up = 1  down = 2  res = 5
    arr[8] = 9   up = 3  down = 1  res = 5

class Solution {
        
        public int maxTurbulenceSize(int[] arr) {
        
            int up = 1, down = 1;
            int res = 1;
            for(int i = 1; i < arr.length; i++) {
        
                if(arr[i - 1] < arr[i] ) {
        
                    up = down + 1;
                    down = 1;
                }else if(arr[i - 1] > arr[i]) {
        
                    down = up + 1;
                    up = 1;
                }else {
        
                    up = down = 1;
                }
                res = Math.max(res, Math.max(up, down));
            }
            return res;
        }
    }

[LeetCode 594.]: https://leetcode-cn.com/problems/longest-harmonious-subsequence/
[LeetCode 674.]: https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
[LeetCode 300.]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[LeetCode 1143.]: https://leetcode-cn.com/problems/longest-common-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/3177dad1668b495d860e341a52dbefad.png
[LeetCode 516.]: https://leetcode-cn.com/problems/longest-palindromic-subsequence/
[LeetCode 1218.]: https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/
[LeetCode 718.]: https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210126222348828.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode 978.]: https://leetcode-cn.com/problems/longest-turbulent-subarray/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210126222412492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw==,size_16,color_FFFFFF,t_70#pic_center