最长递增子序列,交错字符串

server/2024/9/24 0:17:27/

第一题:

代码如下:


int lengthOfLIS(vector<int>& nums)
{//dp[i]表示以第i个元素为结尾的最长子序列的长度int n = nums.size();int res = 1;vector<int> dp(n, 1);for (int i = 1; i < n; ++i){for (int j = 0; j < i; ++j){if (nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}return res;
}

思路整理:

使用动态规划,线性dp就可以解决。

具体状态表示:dp[i]表示以第i个位置为结尾的最长子序列的长度。

初始化:因为最长递增子序列的长度至少为1,所以不妨将所有位置的长度都初始化为1。

填写过程以及逻辑:因为第一个位置为结尾的子序列长度为1,所以i从1下标开始,以该位置元素为结尾的序列有两种情况。

<1>该元素跟在其前面的任意一个元素后组成一个递增子序列。

<2>该元素比前面任意一个元素都小,所以只能自己成为单独的一个递增子序列。

因为在初始化时,已经将第二种情况考虑到了,所以每个位置都为1,若是第二种情况,就不必更新了,只考虑第一种情况就行。即

if (nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);

        表示i位置的元素大于j位置的元素时,dp[i]取dp[i]和dp[j] + 1两者之间的最大值。结合状态表示来理解。每当dp[i]更新完之后,可以更新一下最终结果,走完之后,就可以返回最终结果res了。

时空复杂度:时间复杂度O(n * n),空间复杂度O(n)

第二题:

代码如下:

bool isInterleave(string s1, string s2, string s3) 
{//dp[i][j]表示s1的[0,i]部分和s2的[0,j]能否构成s3的[i,j]部分int m = s1.size();int n = s2.size();if (m + n != s3.size())return false;s1 = " " + s1;s2 = " " + s2;s3 = " " + s3;vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));for (int i = 1; i <= n; ++i)//s1为空{if (s2[i] == s3[i]) dp[0][i] = true;elsebreak;}for (int i = 1; i <= m; ++i)//s2为空{if (s1[i] == s3[i]) dp[i][0] = true;elsebreak;}dp[0][0] = true;for (int i = 1; i <= m; ++i){for (int j = 1; j <= n; ++j){dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]|| s2[j] == s3[i + j] && dp[i][j - 1]);}}return dp[m][n];
}

思路整理:

动态规划,用到二维dp。在此之前,需要进行一个问题的转化,其实就是判断字符串s1能否由s2和s3组成。

具体状态表示:dp[i][j]表示s1的[0,i]部分和s2的[0,j]能否构成s3的[i,j]部分。

初始化:dp数组多开一行一列,便于结合状态定义来解决该问题,为了使得字符串位置一一对应,可以选择在字符串前加上空格符来进行占位,不表示额外含义,只是为了好进行对应。默认开辟的空间内都是false,结合状态定义,初始化第一行,即dp[0][i],当s1为空,就只有s2来组成s3,当s2[i] == s3[i]时,dp[0][i] = true,否则就是false,同理初始化第一列,即dp[i][0],当s2为空,只有s1来组成s3,当s1[i] == s3[i]时,dp[i][0] = true,否则就是false。dp[0][0]为true,确保后面的结果正确。

填写过程以及逻辑:如果s1的长度加上s2的长度和s3的长度不一致,那么就说明一定不能组成s3,返回false,否则dp[i][j]为真的情况有两种:

<1>s1[i] == s3[i + j] && dp[i - 1][j] == true,即s1的i位置和s3的i + j位置相同,并且s1的0~i-1位置和s2的0~j位置能构成s3的当前位置的其余部分。

<2>s2[j] == s3[i + j] && dp[i][j - 1] == true,即s2的i位置和s3的i + j位置相同,并且s1的0~i位置和s2的0~j - 1位置能构成s3的当前位置的其余部分。

最终返回dp[m][n]表示s1和s2能否构成s3。

水平有限,欢迎指正。


http://www.ppmy.cn/server/45159.html

相关文章

Kubectl 的使用——k8s陈述式资源管理

一、kebuctl简介: kubectl 是官方的CLI命令行工具&#xff0c;用于与 apiserver 进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为 apiserver 能识别的信息&#xff0c;进而实现管理 k8s 各种资源的一种有效途径。 对资源的增、删、查操作比较方便&…

长安链使用Golang编写智能合约教程(一)

长安链是分2.1.和2.3.两个版本&#xff0c;本节面说的是2.1.的版本 需要2.3.版本的合约&#xff0c;请看教程&#xff08;二&#xff09;&#xff01; 教程&#xff08;二&#xff09;我会写如何查历史数据 教程二&#xff1a;&#xff08;长安链2.3.的版本的智能合约编写&…

代码随想录算法训练营第22天(py)| 二叉树 | 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树 力扣链接 给定一个二叉搜索树&#xff0c;同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树&#xff0c;使得所有节点的值在[L, R]中 (R>L) 思路 如果当前节点元素小于low&#xff0c;递归右子树&#xff0c;返回符合条件的头节点 如果当前节点元…

6.S081的Lab学习——Lab5: xv6 lazy page allocation

文章目录 前言一、Eliminate allocation from sbrk() (easy)解析&#xff1a; 二、Lazy allocation (moderate)解析&#xff1a; 三、Lazytests and Usertests (moderate)解析&#xff1a; 总结 前言 一个本硕双非的小菜鸡&#xff0c;备战24年秋招。打算尝试6.S081&#xff0…

C++模拟实现stack容器适配器

源代码&#xff08;CSTL库中的stack容器适配器是通过deque实现的&#xff0c;这里使用vector容器实现&#xff09; #include <iostream> #include <vector> #include <list> using namespace std;namespace mystack {//栈的设计采用适配器模式&#xff1a;即…

dubbo复习:(4) 和springboot 整合时,客户端负载均衡的配置

需要在DubboReference注解指定loadbalance属性。示例如下&#xff1a; package cn.edu.tju.service;import org.apache.dubbo.config.annotation.DubboReference; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.stereotype.Ser…

uniapp-自定义navigationBar

封装导航栏自定义组件 创建 nav-bar.vue <script setup>import {onReady} from dcloudio/uni-appimport {ref} from vue;const propsdefineProps([navBackgroundColor])const statusBarHeight ref()const navHeight ref()onReady(() > {uni.getSystemInfo({success…

帝国CMS跳过选择会员类型直接注册方法

国CMS因允许多用户组注册&#xff0c;所以在注册页面会有一个选择注册用户组的界面&#xff0c;即使网站只用了一个用户组也会出现。 如果想去掉这个页面&#xff0c;直接进入注册页面&#xff0c;那么可按以下办法修改 打开 e/class/user.php 文件 查找&#xff1a; $chan…