首页 > 其他分享 >最长递增子序列的个数 - 中等难度

最长递增子序列的个数 - 中等难度

时间:2024-11-29 13:57:32浏览次数:9  
标签:count nums int max 递增 个数 ++ 序列 dp

*************

C++

TOPIC:673. 最长递增子序列的个数 - 力扣(LeetCode)

*************

先看题目:

中等困难,之前做的是最长递增子序列,跟这个很像,先来复习一下找一下思路:

// 这个逻辑比较的简单
//就是说我直接定义dp数组,代表第i位最长递增数列的个数
//遍历每一个元素
//找到最大值

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(); // as before
        vector<int> dp(n, 1); // initialise the dp

        if (n == 0) return 0;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        int max_len = *max_element(dp.begin(), dp.end());
        return max_len;
    }
};

但是,这个题目是个数,复习的题目是长度。

我有一个天才的想法:

最长长度假设输出的 dp = [ 1, 2, 5, 5, 6, 3]

那我直接在dp里寻找最大元素的个数不就好了嘛。

那么问题就转移到如何在数组里面找到最大元素的个数了。

这个跟之前的某道题有点像,我想不起来了,但是方法我记得:

开始时,max设为数组的第一个元素,count设为1。然后从第二个元素开始遍历:

- 如果当前元素大于max,就更新max为当前元素,并重置count为1。

- 如果当前元素等于max,就count加1。

- 如果当前元素小于max,就跳过。

这部分的代码是:

int n = sizeofdp();
int max = dp[0];
int count = 0;

for (int i = 0; i < n; i++){
    if(dp[i] > max){
        max = dp[i];
        count = 1;
        } else if (dp[i] == max){
            count++;
}

        return count;

然后把这段代码加到上面去。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(); // as before
        vector<int> dp(n, 1); // initialise the dp

        if (n == 0) return 0;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        int n = sizeofdp();
        int max = dp[0];
        int count = 0;

for (int i = 0; i < n; i++){
    if(dp[i] > max){
        max = dp[i];
        count = 1;
        } else if (dp[i] == max){
            count++;
}

        return count;
    }
};

这个代码是报错的,直觉上就是不能简单的粘贴复制,因为运算逻辑是从上到下,如果有循环就直接循环,直至跳出循环再往下一行一行的运行,所以初始化以及对一些变量的命名时需要放在最开始,接下来第二个工作就是优化这个代码。

想一下,最开始就要对dp的长度和个数进行初始赋值,这两个都是我要知道的,要让他进行迭代。

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> lengths(n, 1);   // 记录以 nums[i] 结尾的最长递增子序列的长度
        vector<int> counts(n, 1);    // 记录以 nums[i] 结尾的最长递增子序列的个数
        
};

 最主要的记录最长严格递增子串的长度的方法是不变的,对于每一个i,检查从 0 ~ i 位的大小。还有一个冷知识,在同一段代码中,自定义的 i 应该是一致的。

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> dp(n, 1);
        vector<int> count(n, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) { // to order the numbers
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1; // to define the size of the son-string
                        count[i] = count[j]; //to told the nubmbers 
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }
        
       
    }
};

到这一步,保证在检查每一个i对应的dp[i]出现的次数,是同一个 i。

接下来就是找到 dp.start() dp.end()的最大值了。

最大值的方法也很简单,

初始化 max 为 dp[0]

遍历每一个 dp[i]

如果 dp[i] > max,

max = dp[i]

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> dp(n, 1);
        vector<int> count(n, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) { // to order the numbers
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1; // to define the size of the son-string
                        count[i] = count[j]; //to told the nubmbers 
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }
        
        // Find the maximum length in dp
        int max_len = dp[0];
        for (int i = 1; i < n; i++) {
            if (dp[i] > max_len) {
                max_len = dp[i];
            }
        }
        
       
    }
};

然后就是统计最大值出现的次数:

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> dp(n, 1);
        vector<int> count(n, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) { // to order the numbers
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1; // to define the size of the son-string
                        count[i] = count[j]; //to told the nubmbers 
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }
        
        // Find the maximum length in dp
        int max_len = dp[0];
        for (int i = 1; i < n; i++) {
            if (dp[i] > max_len) {
                max_len = dp[i];
            }
        }
        
        // Sum the counts where dp[i] == max_len
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == max_len) {
                result += count[i];
            }
        }
        return result;
    }
};

OK,完成。

标签:count,nums,int,max,递增,个数,++,序列,dp
From: https://blog.csdn.net/ElseWhereR/article/details/144131016

相关文章

  • MATLAB实现基于RF随机森林的时间序列预测-递归预测未来(多指标评价)
    目录MATLAB实现基于TF随机森林的时间序列预测-递归预测未来(多指标评价)1项目背景介绍...1项目目标与意义...2项目挑战...2项目特点与创新...2项目应用领域...3项目效果预测图程序设计...3项目模型架构...4项目模型描述...4项目模型算法流程图...6项目结......
  • 序列到序列的学习 (seq2seq - 词嵌入 - Embedding层 - mask掩码 - 后续会加入注意力机
    目录0.前言1.编码器 (encoder)补充1:词嵌入(WordEmbedding)补充2:嵌入层(EmbeddingLayer)2.解码器(decoder)3.损失函数4.训练5.预测6.预测序列的评估(BLEU)7.小结0.前言课程全部代码(pytorch版)已上传到附件本章节为原书第9章(现代循环网络),共分为8......
  • Java反序列化 - CC6链 (代码审计)
    一、漏洞简述:相比较于CC6链,CC1链对jdk版本有较多的限制。在jdk_8u71版本之后,AnnotationInvocationHandler类中的readObject方法代码被修改,移除了原有的setValue()方法,导致利用链断开。jdk_8u65:jdk_8u71:二、CC6链分析:1、利用逻辑:Hashmap.readObject()->Hashmap.hash()......
  • Day49 | 动态规划 :线性DP 判断子序列&&两个字符串的删除操作
    Day49|动态规划:线性DP判断子序列&&两个字符串的删除操作动态规划应该如何学习?-CSDN博客动态规划学习:1.思考回溯法(深度优先遍历)怎么写注意要画树形结构图2.转成记忆化搜索看哪些地方是重复计算的,怎么用记忆化搜索给顶替掉这些重复计算3.把记忆化搜索翻译成动态规......
  • C#反序列化XML时提示XML 文档(1, 1)中有错误
    最近在反序列化一个XML时,遇到了如下报错: XML文档(1,1)中有错误。内部异常XmlException:根级别上的数据无效。第1行,位置1。 看描述应该是XML格式的问题,我把XML复制到新建的控制台程序,反序列化又是可以的。代码如下:1internalclassProgram2{3stati......
  • 非子串的子序列
     #include<bits/stdc++.h>usingnamespacestd;intmain(){intn,q;cin>>n>>q;strings;cin>>s;boolflag[n]={true},flag2[n]={true};inta,b,p,num=0,c=0;while(q--){......
  • 代码随想录 -- 动态规划 -- 最长回文子序列
    516.最长回文子序列-力扣(LeetCode)思路:dp数组的含义:dp[i][j]:字符串s从i到j的最长回文子序列的长度为dp[i][j]递推公式:当s[i]=s[j]时:dp[i][j]=dp[i+1][j-1]+2当s[i]!=s[j]时:dp[i][j]=max(dp[i][j-1],dp[i+1][j])初始化:当i=j时:dp[i][j]=1遍历顺序:从下到上,从左到右最......
  • 什么是随机变量序列
    什么是随机变量序列?随机变量序列就是一列按某种规则排列的随机变量.这种规则可以随意,但强调的是一个次序.例如: 若Xi表示第i次抛硬币的结果,那么{Xi}这个序列就是若干次抛硬币的结果序列.X1指第一次跑的结果,Xn指第n次抛的结果.若Yi表示前i次抛硬币正面向上的次......
  • leetcode 2099. 找到和最大的长度为 K 的子序列
    2099.找到和最大的长度为K的子序列特别注意,题目要求不改变原来的元素顺序我的代码classSolution{public:vector<int>maxSubsequence(vector<int>&nums,intk){vector<int>temp(nums);sort(temp.begin(),temp.end());intsize=t......
  • H5-6 列表标签 有序列表
    1、有序标签有序列表是一列项目,列表项目使用数学进行标记。有序列表始于<ol>标签。每个列表始于<li>标签。  <ol>    <li></li>    <li></li>  </ol> 2、type属性:<ol>的属性type拥有的选项1表示列表项目用数字标号(1,2,3...)......