day45.动态规划

1035.不相交的线:

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足:

 nums1[i] == nums2[j]
且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。

以这种方法绘制线条,并返回可以绘制的最大连线数。

 

 思路:和最长公共子序列是一样的,由图可见1 4 就是两个数组的最长公共子序列。

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));//确认递推公式int res=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;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}return dp[nums1.size()][nums2.size()];}
};

53.最大子数组和

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组
是数组中的一个连续部分。

 思路:1.贪心法:局部最优推出全局最优,局部最优就是当前两个的和大于0,如果两个和小于0时,将sum重置为0。

class Solution {
public:int maxSubArray(vector<int>& nums) {//1.贪心做法//局部最优推出 全局最优vector<int> res(nums.size()+1);int j=1,i=0;int sum=0;int count=-INT_MAX;for(int i=0;i<nums.size();i++){sum+=nums[i];count=max(sum,count);if(sum<0){sum=0;}}return count;}
};

2.动态规划:

 思路:定义一个dp数组,这道题目的核心就在于推出递归公式,dp[i]意义在于包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]。dp[i]由什么可以推导出来呢,dp[i]取 当前数组的值或者加上当前数组的值 的最大值。定义一个res来取整个数组的最大值。

class Solution {
public:int maxSubArray(vector<int>& nums) {//2.动态规划if(nums.size()==0)return 0;vector<int> dp(nums.size()+1);//dp数组的含义是 dp[i] 代表 0-i 区间的 最大子数组和dp[0]=nums[0];int res=dp[0];//dp[i]=dp[i-1]+nums[i];for(int i=1;i<nums.size();i++){dp[i]=max(nums[i],dp[i-1]+nums[i]);res=max(res,dp[i]);}return res;}
};

392.判断子序列

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

进阶:

如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

致谢:

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

 思路:1.双指针做法,遇到相同的就移动指向字串的指针,当slow等于字串长度时,返回true,否则返回false。

class Solution {
public:bool isSubsequence(string s, string t) {if(s.size()==0){return true;}int slow=0;int fast=0;for(slow,fast;fast<t.size();fast++){if(s[slow]==t[fast]){slow++;if(slow==s.size()){return true;}}}return false;}
};

2.动态规划:

 思路: 和最长公共子序列也是蛮像的,不过else的语句里只有dp[i][j-1],没有dp[i-1][j],因为s是子串,不能用子串来判断。 注意 i和j可以等于是,s,size和t.size()  因为  让i可以等于s.size()是为了完整地检查s是否是t的子序列,确保考虑到了s的所有字符与t的不同部分进行匹配的情况。

class Solution {
public:bool isSubsequence(string s, string t) {vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));if (s.empty()) return true;if (t.empty()) return false;for(int i=1;i<=s.size();i++){for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=dp[i][j-1];}}}if(dp[s.size()][t.size()]==s.size()){return true;}return false;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/413319.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Python】家庭用电数据的时序分析

Household Electricity Consumption | Kaggle 目录 数据简介 探索分析 数据清洗 用电占比 趋势分析 序列分解 周期分析 周期分解 分析小结 数据简介 240000-household-electricity-consumption-records数据集包含了一个家庭6个月的用电数据&#xff0c;收集于2007年1…

安防监控/软硬一体/视频汇聚网关EasyCVR硬件启动崩溃是什么原因?

安防视频监控EasyCVR安防监控视频系统采用先进的网络传输技术&#xff0c;支持高清视频的接入和传输&#xff0c;能够满足大规模、高并发的远程监控需求。EasyCVR平台支持多种视频流的外部分发&#xff0c;如RTMP、RTSP、HTTP-FLV、WebSocket-FLV、HLS、WebRTC、WS-FMP4、HTTP-…

MySql【数据查询语言DQL】

DQL[非常重要] DQL 主要指查询语句,有查询单表数据,也有查多表数据表,单表查询 基本查询 条件查询 模糊查询 排序查询 聚合查询 去重查询 分组查询 限制查询 1、 数据准备 将发的stu.sql导入到MySql中 2、 基本查询 select 字段1,字段2,... from 表名; 查询返回的是一张…

C语言 ——— 文件读取结束的判定

目录 判定文件读取结束的方式 被错误使用的feof函数 判定文件结束的正确使用 判定文件读取结束的方式 判断文本文件是否读取结束&#xff1a; 利用 fgetc 判断返回值是否为 EOF 利用 fgets 判断返回值是否为 NULL 判断二进制文件是否读取结束&#xff1a; 利用 fread 判…

MAC环境导出项目的目录结构

一、安装Homebrew包管理工具 /bin/bash -c "$(curl -fsSL https://gitee.com/ineo6/homebrew-install/raw/master/install.sh)" 官网网址&#xff1a;https://brew.idayer.com/ 二、用brew包管理工具安装tree brew install tree 三、打开终端&#xff0c;导出项目…

axios响应

一.axios请求配置项(axios在调用时所接收的参数对象&#xff09; 以下是请求时可用的配置选项&#xff0c;只有url是必须的&#xff0c;如果没有指定method&#xff0c;请求将默认使用get方法 { // url 是用于请求的服务器 URL url: "/user", // method 是创建请…

【三维重建】三角网格中轴骨架线提取

三维网格中轴线提取 方法介绍实现提取 三维网格中轴线提取是计算机图形学和三维建模领域中的一个重要技术&#xff0c;它对于理解三维形状的拓扑结构和几何特性具有重要意义。 方法介绍 以下是几种常见的三维网格中轴线提取方法&#xff1a; 基于距离变换的方法 基本原理&…

大数据计算-SQL优化手段(CBO)-以Flink为例

文章目录 背景理论知识示例结果展示结果解释 背景 大数据计算中&#xff0c;SQL生成的执行计划第一轮会经过固定规则的优化&#xff0c;第二轮会根据原计划&#xff0c;生成多条结合成本的的执行计划&#xff0c;根据cost 进行排序&#xff0c;选出最优的执行计划。 理论知识…

【大数据算法】时间亚线性算法之:时间亚线性判定算法概述。

时间亚线性判定算法概述 1、引言2、空间亚线性算法2.1 定义2.2 实现方式2.3 应用场景2.3.1 大数据分析2.3.2 流数据处理2.3.3 近似计算2.3.4 稀疏数据操作 2.4 代码示例 3、总结 1、引言 小屌丝&#xff1a;鱼哥&#xff0c;最近看新闻没啊&#xff1f; 小鱼&#xff1a;我天天…

Upload-labs靶场通过攻略

pass-01 1.写一个一句话木马 2.上传php文件 当我们上传php文件时 提示文件类型不正确 3.修改php后缀 通过修改php后缀为jpg 抓包再次修改成php文件 4.查看是否上传成功 页面显示图片 表示上传成功 pass-02 1.上传一个php文件 页面显示文件类型不正确 2.抓包修改 可以看…

【化学方程式配平 / 3】

题目 代码 #include <bits/stdc.h> using namespace std; const double eps 1e-8; unordered_map<string, int> e; int eidx, midx; //eidx 元素数&#xff0c; midx 物质数 double matrix[45][45]; int q; bool check_alpha(char c) {if(c > a && c …

Android APK打包脚本

build.gradle版本 同目录创建config.gradle文件写入需要的信息入 config.gradle文件内容 ext { /*** 自定义APP运行环境* dev: 开发* test: 测试* pro: 生产*/ env "pro" /*** 动态参数配置&#xff0c;根据自己需要添加参数* APP_ID: 包名* VERSION_CODE: 版本号…

【TDesign】如何修改CSS变量

Tdesign的组件想通过style定义样式没效果, 可以通过组件api文档修改, 组件提供了下列 CSS 变量&#xff0c;可用于自定义样式。 比如Cell, https://tdesign.tencent.com/miniprogram/components/cell?tabapi 提供了&#xff1a; –td-cell-left-icon-color 图标颜色 –td-cell…

yolo训练策略--使用 Python 和 OpenCV 进行图像亮度增强与批量文件复制

简介 在计算机视觉和深度学习项目中&#xff0c;数据增强是一种常用的技术&#xff0c;通过对原始图像进行多种变换&#xff0c;可以增加数据集的多样性&#xff0c;从而提高模型的泛化能力。本文将介绍如何使用 Python 和 OpenCV 实现图像的亮度增强&#xff0c;并将增强后的…

Golang | Leetcode Golang题解之第383题赎金信

题目&#xff1a; 题解&#xff1a; func canConstruct(ransomNote, magazine string) bool {if len(ransomNote) > len(magazine) {return false}cnt : [26]int{}for _, ch : range magazine {cnt[ch-a]}for _, ch : range ransomNote {cnt[ch-a]--if cnt[ch-a] < 0 {r…

Vue(八) localStorage、组件的自定义事件、Todo案例修改

文章目录 一、浏览器本地存储1. 相关API2. Todo案例中的应用 二、组件的自定义事件1. 回顾props传值方式2. 绑定自定义事件&#xff08;1&#xff09;方式一&#xff1a;v-on或&#xff08;2&#xff09;方式二&#xff1a; ref 3. 解绑自定义事件4. 注意点总结 三、Todo案例采…

算法复盘——LeetCode hot100:哈希

文章目录 哈希表哈希表的基本概念哈希表的使用1. 插入操作2. 查找操作3. 删除操作 哈希表的优点和缺点1.两数之和复盘 242.有效的字母异位词复盘 49.字母异位词分组复盘 128. 最长连续序列复盘HashSet 哈希表 先来搞清楚什么是哈希表吧~ 概念不清楚方法不清楚怎么做题捏 哈希表…

c++习题28-计算2的N次方

目录 一&#xff0c;题目 二&#xff0c;思路 三&#xff0c;代码 一&#xff0c;题目 描述 任意给定一个正整数N(N<100)&#xff0c;计算2的n次方的值。 输入描述 输入一个正整数N。 输出描述 输出2的N次方的值。 用例输入 1 5 用例输出 1 32 二&#xff0…

【王树森】Transformer模型(2/2): 从Attention层到Transformer网络(个人向笔记)

Single Head Self-Attention 上节课讲到的属于单头注意力&#xff1a; Multi-Head Self-Attention 使用 l l l 个单头注意力层堆叠成一个多头注意力层&#xff0c;注意它们之间不共享参数一个单头注意力有 3 个参数矩阵&#xff0c;所以多头注意力有 3 l 3l 3l 个参数矩阵…

docker文档

一、docker概述 1、java项目通过docker打包成镜像&#xff08;包含了所有的环境&#xff09;放到docker仓库中&#xff0c;只需要下载发布的镜像直接运行即可&#xff1b; 2、虚拟机技术的缺点&#xff1a; 资源占用多、冗余步骤多、启动很慢 容器化技术&#xff1a; 比较do…