子序列

本文主要是介绍子序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 最长不含重复字符的子字符串（动态规划+哈希表）
• 最长递增子序列（常考!!!!!不连续，动态规划+哈希表）
• 最长连续递增子序列（连续，动态规划）
• 最长重复子数组（连续，动态规划）
• 最长公共子序列（不连续，动态规划）
• 最大子序和（字节常考!!!!!动态规划）

子序列问题：dp数组长度+1是考虑了空数组的情况，遍历从1开始

最长不含重复字符的子字符串（动态规划+哈希表）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 选择特定条件子串问题：滑动窗口左右指针（）+哈希表
        // 哈希表，key：字符；value：该字符出现次数
        // 右指针先前进，前进过程判断新加入的字符是否在哈希表内，不在的话继续前进并且将该字符作为键加入哈希表；如果新加入的字符在哈希表中已有，则不断移动左指针直到窗口内重复字符消失
        unordered_map<char, int> window;
        int left=0, right=0;
        // 记录不含有重复字符的最长子串的长度
        int len = 0;
        while(right < s.size()){
            // 不断向前移动右指针直到窗口内出现重复字符
            // 将移入窗口的字符
            char c = s[right];
            // 右移窗口
            right++;
            // 加入字符后对哈希表的影响
            window[c]++;
            // 判断新加入的字符是否是重复字符，是则开始移动左指针
            while(window[c]>1){
                // 存在重复字符了，不断移动左指针直到窗口内重复字符消失
                // 将移出窗口的字符
                char d = s[left];
                left++;
                // 移出窗口的字符后对哈希表的影响
                window[d]--;
            }
            // 在不重复字符范围更新不含有重复字符的最长子串的长度
            if(right-left > len){
                len = right-left;
            }
        }
        return len;
    }
};

最长递增子序列（常考!!!!!不连续，动态规划+哈希表）

最长上升子序列是动规的经典题目

dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度

所以先遍历数组中的每个元素nums[i]

然后遍历这个元素前面的元素，当找到比nums[i]小的元素nums[j]时：

• 由于以nums[j]这个数结尾的最长递增子序列的长度为已知的dp[j]（因为是从前往后遍历，所以dp[j]肯定已知）

• 则dp[j]+1表示以nums[j]这个数结尾的最长递增子序列加上nums[i]组成一个新的序列

第一层遍历实际上是在取nums[i]前面所有比nums[i]小的元素的最长递增子序列加上nums[i]后的最大值

即为以nums[i]这个数结尾的最长递增子序列的长度dp[i]

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 动态规划：（自底向上）循环迭代+状态转移表
        // （1）明确数组dp含义：dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度
        // （2）运用数学归纳思想：假设dp[0]...dp[i-1]已知，推导出dp[i]
        //      求dp[i]：既然是递增序列，只要找到前面那些结尾比nums[i]小的子序列，然后把nums[i]接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加1
        // （3）dp数组的最大值为所求
        // 时间复杂度为O(n^2)
        int length = nums.size();
        vector<int> dp(length, 1);
        // 记录最长递增子序列长度
        int maxlength = 0;
        for (int i=0; i<length; ++i){
            for (int j=0; j<i; ++j){
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);  // 注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。
            }
            maxlength = max(maxlength,dp[i]);
        }
        return maxlength;
    }
};

最长连续递增子序列（连续，动态规划）

• 贪心算法：O(n) O(1)

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int result = 1; // 连续子序列最少也是1
        int count = 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i + 1] > nums[i]) { // 连续记录
                count++;
            } else { // 不连续，count从头开始
                count = 1;
            }
            if (count > result) result = count;
        }
        return result;
    }
};

• 动态规划：O(n) O(n)

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int maxLength = 1;  // // 记录最长递增子序列长度
        // dp数组初始化
        vector<int> dp(nums.size(), 1);
        for(int i = 0; i < nums.size()-1; ++i){
            if(nums[i+1] > nums[i]){
                dp[i+1] = dp[i] + 1;
            }
            maxLength = max(maxLength, dp[i+1]);
        }
        return maxLength;
    }
};

最长重复子数组（连续，动态规划）

class Solution {
public:
/*
1 确定dp数组（dp table）以及下标的含义
    dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
    在遍历dp[i][j]的时候i 和 j都要从1开始
*/
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1,0));
        int maxLength = 0;
        for(int i = 1; i <= nums1.size(); ++i){
            for(int j = 1; j <= nums2.size(); ++j){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                maxLength = max(maxLength, dp[i][j]);
            }
        }
        return maxLength;
    }
};

最长公共子序列（不连续，动态规划）

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

最大子序和（字节常考!!!!!动态规划）

• 贪心算法：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
            if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count;
            }
            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
};

• 动态规划1

  • dp[i]表示以nums[i]这个数为结尾的最大连续子数组和

  • dp[i]只有两个方向可以推出来：

    • dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和

    • nums[i]，即：nums[i]另起一个序列

  • 一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //(2)最长递增子序列：动态规划
        // 动态规划：（自底向上）循环迭代+状态转移表
        // 1）明确数组dp含义：dp[i]表示以nums[i]这个数为结尾的最大连续子数组和
        // 2）运用数学归纳思想：假设dp[0]...dp[i-1]已知，推导出dp[i]
        //   dp[i]有两种选择，要么与前面的相邻子数组连接形成一个更大的子数组，要么自己一个人作为子数组
        //   求dp[i]：dp[i]只与dp[i-1]有关，dp[i-1]已知，则dp[i]为max(num[i],num[i]+dp[i-1]),即如果nums[i]与前面数组连接后的与自己单独一人作比较
        // 3）dp数组的最大值为所求
        int length = nums.size();
        if (length==0) return 0;
        // base case
        // 第一个数组前面没有子数组
        int dp_0 = nums[0];
        int dp_1 = 0;
        int maxSum = dp_0;
        for (int i=1; i<length; ++i){
            dp_1 = max(nums[i], nums[i]+dp_0);
            dp_0 = dp_1;
            maxSum = max(maxSum, dp_1);
        }
        return maxSum;
    }
};

• 动态规划2

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size());  // dp[i]表示包括i之前的最大连续子序列和
        dp[0] = nums[0];
        int result = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
        }
        return result;
    }
};

这篇关于子序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！